ドイツ大学院生日記

問題を解いた際に自分の復習用として使ってます

エアランゲンでのVISA申請方法

こちらの記事では、エアランゲンでのVISA申請方法を解説していきます。

市役所

VISA申請は、こちらの市役所で行います。 Startseite - Erlangen - Portal der Stadt Erlangen

市役所のVISA関連の予約

VISA申請に関しては、予約が必須なので、こちらのページから予約を取ります。 Ausländerangelegenheiten und Einbürgerungen - Ämter A-Z - Erlangen - Portal der Stadt Erlangen

予約を取る方法はいくつかあります。 私の名前はTから始まるので、Temporary staysのLetter group SZの方にメールを送信しました。

※ online appointment management こちらで、予約を取ることはできますが、私が取ろうと思ったときは全て埋まっており、申請できませんでした。

必要書類

エアランゲンでの住民登録方法

この記事では、エアランゲンでの住民登録の方法を解説していきます。

市役所

https://www.erlangen.de/
エアランゲンでは、こちらの市役所で住民登録ができます。 移住後2週間以内に申請を行う必要があるので、時間が出来次第、早めに出向きましょう。 午前10時前には行った方が待ち時間が少なくて良いです。

市役所の住民登録ページ

こちらのページで、エアランゲンでの住民登録の方法が解説されています。 www.erlangen.de

必要な書類

まずは、書類を整えます。 申請には、2つの書類が必要です。 登録は、スタッフとのやり取りを通して行われるので、特に申請フォームはありません

  • パスポート
  • Wohnungsgeberbestätigung

Wohnungsgeberbestätigung

こちらは、住民登録ページの右上からダウンロードできます。 https://www.erlangen.de/PortalData/1/Resources/080_stadtverwaltung/dokumente/formulare/331_f_Wohnungsgeberbestaetigung_2017.pdf

大家さんに、記入してもらいましょう。

申請

予約は必要ないので、直接市役所に出向きましょう。 Arcadenの通りを、南に行くと左手にあります。英語も通じるので、ドイツ語ができなくても必要ありません。

まずは、入り口で警備員に「Registration」または「Anmeldung」というと整理券を発行してくれると思います。 不在だったら、入って左手にあるタッチパネルの1番上を押すと、整理券を発行できます。

発券できたら、自分の番号が表示されるまで待ちましょう。 自分の番号が呼ばれたら、Platzの番号を覚えて、入り口の左手にある部屋に進んでいき、番号と同じ窓口にいきましょう。

そこで再び、「Registration」または「Anmeldung」というと申請を受け付けてもらえます。

AGC018 A問題

問題

agc018.contest.atcoder.jp

解説

この問題はユークリッドの互除法を用います。ではなぜユークリッドの互除法と言う考え方が出てくるのか解説します。 まずユークリッドの互除法に関して以下のページを読んでください。

math.nakaken88.com

a(modG)が0, b(modG)が0,ならば a-b(modG)も0になることが理解できたかと思います。すると任意の二つの数に関する最大公約数 が書かれたボールを入れることができるため、それらの最大公約数が書かれたボールに対して再び上記の捜査を繰り返すとすべての数の最大公約数が書かれたボールを入れることができます。その最大公約数をGとし、K-G、 K-2G, K-3G,....2G, Gのボールを入れることができるためKがGで割り切れる時、K=x*GであるKのボールも入れることができます。 したがってKがGで割り切れるかどうかを判定すれば良いです。

コード

include

include

include

using namespace std;

int gcd(int a, int b){ if(a%b == 0){ return b; }else{ return gcd(b,a%b); } } int main(void){ int n, k, a[100005]; cin >> n >> k; for(int i=0;i<n;i++){ cin >> a[i]; if(a[i] == k){ cout << "POSSIBLE" << endl; return 0; } } sort(a,a+n); if(a[n-1] < k){ cout << "IMPOSSIBLE" << endl; return 0; } int G = gcd(a[0], a[1]); for(int i=2; i<n; i++){ G = gcd(a[i], G); } if(k%G == 0){ cout << "POSSIBLE" << endl; }else{ cout << "IMPOSSIBLE" << endl; }

return 0;

}

ABC051 D問題 Candidates of No Shortest Paths

問題

abc051.contest.atcoder.jp

解説

まずNが少ないのでワーシャルフロイドを使いそうだなと考えられ、実際に使用します。
まず頂点間の最小距離を求めておきます。 そしてある辺が最小距離のパスに使われているかどうかは以下の式を満たしているs, tが存在するかで判断します。

dist(s, t) = dist(s, i) + edge(i, j) + dist(j, t)

この式を満たしているs, tを2重ループを使って探索して一つでも存在すれば最短距離のパスの中に使われていることになります。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

struct edge {
    int from, to, cost;
};

typedef pair<int, int> P;
typedef vector<vector<edge> > G;

G graph;
int n, m;

int d[105][105];
bool used[105][105];
vector<edge> dist;

void warshall_floyd(){
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int main(void){
    cin >> n >> m;
    graph = G(n);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == j){
                d[i][j] = 0;
            }else{
                d[i][j] = inf;
            }
        }
    }
    int cnt = 0;
    for(int i=0; i<m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        x--;
        y--;
        d[x][y] = c;
        d[y][x] = c;
        edge e;

        e.from = x;
        e.to = y;
        e.cost = c;
        dist.push_back(e);
        e.from = y;
        e.to = x;
        e.cost = c;
        dist.push_back(e);

    }

    warshall_floyd();
    int ans = 0;
    for(int i=0; i<dist.size(); i++){
        bool flag = false;
        for(int s=0; s<n; s++){
            for(int t=0; t<n; t++){
                if(d[s][dist[i].from] + dist[i].cost + d[dist[i].to][t] == d[s][t]){
                    flag = true;
                }
            }
        }
        if(!(flag)){
            ans++;
        }
    }
    cout << ans/2 << endl;
    return 0;
}

CODE FESTIVAL 2017 qual B C問題 3 Steps

問題

code-festival-2017-qualb.contest.atcoder.jp

解説

辺を3本巡って到達できる頂点と辺を新たに結ぶので、2頂点間に奇数長のパスが存在すれば辺を結ぶことができます。 では奇数長のパスが存在するとはどのような時なのでしょうか。それは2分グラフであるかどうかに影響されます。 * 2分グラフである場合 辺を結ぶことができるのは色が異なる頂点間です。それは同色であると必ずパスの長さが偶数になるからです。 よって黒と白に塗り分けるとすると、黒の頂点数=b, 白の頂点数=wとすると bC1 * wC1 が結ぶことができる辺の数であり、すでに結ばれている辺の数Mを引いた値が答えになります。 * 2分グラフでない場合 必ず奇数長のサイクルが存在するので全ての2頂点間のパスの中に奇数長のパスが存在することになり、任意の2頂点間を辺で結ぶことができるためnC2-mが答えになります。

コード

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;

const long long inf = 1e10;
const long long mod = 1e9+7;

typedef vector<vector<int> > G;
G graph;

int color[100050];

bool dfs(int u, int c){
    color[u] = c;
    for(int i=0; i<graph[u].size(); i++){
        int v = graph[u][i];
        if(color[v] == c){
            return false;
        }
        if(color[v] == 0 && !dfs(v, -c) ){
            return false;
        }
    }   
    return true;
}

int main(void){
    long long n, m;
    cin >> n >> m;
    graph = G(n);
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    long long B=0, W=0;
    if(dfs(0, 1)){
        for(int i=0; i<n; i++){
            if(color[i] == 1){
                B++;
            }else if(color[i] == -1){
                W++;
            }
        }
        cout << B*W - m << endl;
    }else{
        cout << ( (n*(n-1)) /2) - m << endl;
    }
    
    return 0;
}

ABC075 A~D問題

A問題

A - One out of Three

解説

これは解説省略します。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

int main(void){
    int a, b, c;
    string s;
    cin >> a >> b >> c;
    if(a == b){
        cout << c << endl;
    }else if(b == c){
        cout << a << endl;
    }else if(a == c){
        cout << b << endl;
    }
    return 0;
}


B問題

B - Minesweeper

解説

全ての' . 'に関して8方向に#がいくつあるかをカウントしていけば良いです。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

int main(void){
    int h, w;
    char field[55][55];
    cin >> h >> w;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> field[i][j]; 
        }
    }
    int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(field[i][j] == '.'){
                int cnt = 0;
                for(int k=0; k<8; k++){
                    int nx = j + dx[k], ny = i + dy[k];
                    if(nx >= 0 && nx < w && ny >= 0 && ny < h && field[ny][nx] == '#'){
                        cnt++;
                    }
                }
                cout << cnt;
            }else{
                cout << "#";
            }
        }
        cout << endl;
    }
    return 0;
}


C問題

C - Bridge

解説

全ての辺に関して、その辺がないものとしてDFSし、全ての頂点を訪れることができるかどうかを調べていきます。
訪れていない頂点があればその辺は橋であり、全ての頂点を訪れることができればその辺は橋ではありません。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

typedef pair<int, int> P;

int n, m;
bool visited[100];
bool AList[100][100];

void dfs(int u){
    visited[u] = true;
    for(int i=0; i<n; i++){
        if(AList[u][i] && !(visited[i]) ){
            dfs(i);
        }
    }
    return;
}

int main(void){
    int ans = 0;

    queue<pair<int, int> > que; 
    cin >> n >> m;

    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        AList[x][y] = true;
        AList[y][x] = true;
        que.push(P(x, y));
    }

    for(int i=0; i<m; i++){

        bool flag = true;
        fill(visited, visited+n, false);

        P p = que.front();
        que.pop();
        AList[p.first][p.second] = false;
        AList[p.second][p.first] = false;

        dfs(0);
        for(int j=0; j<n; j++){
            if(!(visited[j])){
                flag = false;
            }
        }

        if(!(flag) ){
            ans++;
        }

        AList[p.first][p.second] = true;
        AList[p.second][p.first] = true;
    }
    cout << ans << endl;

    return 0;
}


D問題

D - Axis-Parallel Rectangle

解説

ある長方形の区間にいくつ点が含まれているかを数え、それがkを超えている、かつ面積が最小である。この時の最小の面積を出力すれば良いので、長方形の区間をどのようにして決定させるか問題になります。そこで長方形の横の区間を決定付ける値を求めていきます。それは左右の辺には必ず頂点が含まれているため頂点のx座標が左右の端の座標の候補になります。同様にして上下の区間もy座標が候補になるので全て全探索して、その区間に含まれる頂点の個数を数えてあげ面積を保持しながら求めていけば解くことができます。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

typedef pair<int, int> P;

int main(void){
    int n, k;
    long long surface = 4e18;
    cin >> n >> k;
    vector<int> vecx, vecy;
    vector<P> vec;
    for(int i=0; i<n; i++){
        int x, y;
        cin >> x >> y;
        vecx.push_back(x);
        vecy.push_back(y);
        vec.push_back(P(x, y));
    }
    sort(vecx.begin(), vecx.end());
    sort(vecy.begin(), vecy.end());
    for(int xi=0; xi<n; xi++){
        for(int xj=xi+1; xj<n; xj++){
            for(int yi=0; yi<n; yi++){
                for(int yj=yi+1; yj<n; yj++){
                    int cnt=0;
                    long long tmp = (long long)(vecx[xj]-vecx[xi])*(vecy[yj]-vecy[yi]);
                    for(int i=0; i<n; i++){
                        P p = vec[i];
                        if(vecx[xi] <= p.first && p.first <= vecx[xj] && vecy[yi] <= p.second && p.second <= vecy[yj] ){
                            cnt++;
                        }
                    }
                    if(cnt >= k && surface > tmp){
                        surface = tmp;
                    }
                }
            }
        }
    }
    cout << surface << endl;
    
    return 0;
}

AGC014 B問題 Unplanned Queries

問題

agc014.contest.atcoder.jp

解説

まずこの問題では木を根付き木として考えます。各辺は偶数回 +1 されていれば良い、つまり各辺の値が0, 2, 4, ...となっていれば良いのでmod2で考えることができます。そして根をrとすると, +1する辺を(a, b)ならば(a,r)と(r,b)に分解できます。それはLAC(aとbのもっとも近い親)をcとするとa-cに+1, b-cに+1, c-r, r-cに+1ずつされることになりr-cは+2で実質操作を行っていないことになります。

次に奇数回しかクエリに出ていない数の中で一番深いノードをxとするとxの上の辺には+1しかされていないため全てを偶数にすることはできません。 よって全ての数に関して出現回数が偶数であればYES, 奇数回の数があればNOとなります。

コード

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

#define ALL(x) x.begin(), x.end()
using namespace std;

int point[100005];

int main(void){
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        point[x]++;
        point[y]++;
    }
    for(int i=0; i<n; i++){
        if(point[i] % 2 == 1){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}