AtCoder Beginner Contest 113

C - ID

https://atcoder.jp/contests/abc113/tasks/abc113_c

方針

県ごとに pair 型の配列を持っておき、誕生年と市番号のペア (Y, i) を詰めていきます。各配列を県ごとに Y でソートすると、市 i がその県の中で何番目に誕生したかがわかるので、認識番号を作ることが出来ます。出力は i の順に行うので、string 型の配列 ans を持っておき、ans[i] に答えを入れていくことにします。

なお値 n を 0 埋めで 6 桁にする方法ですが、私は to_string(n) でstring に変換した後、while 文で文字長が6未満のときに先頭に "0" を追加しました。

ソースコード

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> Pint;

int main(){
    int N, M;  cin >> N >> M;
    vector<vector<Pint>> cities;
    cities = vector<vector<Pint>>(N+1, vector<Pint>());
    // cities[p][i] は 県 p の i 番目の市を表す。
    for(int i=0; i<M; i++){
        int p, y;  cin >> p >> y;
        cities[p].push_back(Pint(y, i));
    }

    vector<string> ans(M);  // ans[i] は市 i の認識番号。
    for(int p=1; p<=N; p++){
        sort(cities[p].begin(), cities[p].end());
        int n = cities[p].size();
        for(int i=0; i<n; i++){
            int num = cities[p][i].second;     // num は市番号(市 i の i )に相当。
            string prefID = to_string(p);       // 県番号。
            string numID = to_string(i+1);   // 市の誕生した順番は 1 番目 から始まるので i+1
            while(prefID.length()<6) prefID = "0" + prefID;      // 6 桁になるまで先頭を "0" で埋める
            while(numID.length()<6) numID = "0" + numID;

            ans[num] = prefID + numID;
        }
    }

    for(int i=0; i<M; i++) cout << ans[i] << endl;
}

D - Number of Amidakuji

https://atcoder.jp/contests/abc113/tasks/abc113_d

方針

縦棒 w の上から h [cm] の点のことを と書くことにします。縦棒 1 の上端から出発し、 に達するようなあみだくじの種類を 通りとします。求めるものは です。

まず出発点は縦棒 1 ですから、 です。

次に h > 1 とし、 がどのように表されるかを考えます。 に達するのは、以下の3通りであることがわかります。

1. に位置し、上から へ降りてくる場合
   • このとき、高さ h における横棒は、縦棒 w を端点としてはいけません。
2. に位置し、左から へ達する場合
   • このとき、高さ h における横棒は、縦棒 w - 1, w を結びます。
3. に位置し、右から へ達する場合
   • このとき、高さ h における横棒は、縦棒 w, w + 1 を結びます。

ここで h - 1 から h への遷移は、h における横棒の配置のみが影響します。上記 1. ~ 3. の条件と「正しいあみだくじ」の条件を満たす、位置 h における横棒の配置がそれぞれ 通りとすると、漸化式は
　　
と書くことができます。

最後に を求めましょう。「正しいあみだくじ」であるための条件のうち、(a)「それぞれの横棒の 2 つの端点は同じ高さ」と (b)「横棒は隣り合う縦線を繋ぐ」のみを満たす横棒の配置をすべて列挙し、その中から「どの 2 つの横棒も端点を共有しない」と上記の 1. ~ 3. の条件を満たすものが何個あるかを数える、という方針でいきます。

二進数表記で W ビットとなる値 i を考えます(最も左を第 1 ビットとします)。i の第 j ビットが 1 のときに縦棒 j, j + 1 が結ばれていると考えることにすると、 通りある、(a) (b) を満たす横棒の配置を という値によって表すことができます。さらに (c) は「 i の隣り合うビットがともに 1 にならない」と、上記の条件 1. ~ 3. はそれぞれ下記のように言い換えられます。

1. i の第 j - 1, j ビットが共に 0
2. i の第 j - 1 ビットが 1
3. i の第 j ビットが 1

実装においては で初期化し、 をループで回しながら、条件 k を満たすときに を 1 増やす、とすればよいです。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool isValid(int n){
    // n の隣り合うビットがともに 1 になるとき false 、それ以外の時に true を返す。
    if(n==0) return true;

    bool ret = true;
    if(n%2==0) ret = isValid(n/2);
    else{
        if((n/2)%2==1) ret = false;
        else ret = isValid(n/2);
    }
    return ret;
}

int main(){
    ll mod = 1000000007;
    int H, W, K;  cin >> H >> W >> K;
    vector<vector<ll>> dp;
    dp = vector<vector<ll>>(H+1, vector<ll>(W+1, 0));
    dp[0][1] = 1;
    for(int h=0; h<H; h++){
        for(int w=1; w<=W; w++){
            ll c1 = 0, c2 = 0, c3 = 0;
            int N = (1 << (W - 1));
            for(int i=0; i<N; i++){
                if(!isValid(i)) continue;
                int n = i;
                int j = 1;
                vector<bool> bridge(W+1, false);  // bridge[j] = true のとき、縦棒 j, j + 1 が横棒で結ばれる。
                while(n > 0){
                    if(n%2==1) bridge[W-j] = true;
                    n/=2;  j++;
                }
                if(!bridge[w] && !bridge[w-1]) c1++;
                if(bridge[w-1]) c2++;
                if(bridge[w]) c3++;
            }
            dp[h+1][w] = c1*dp[h][w]%mod;
            if(w-1>=1) dp[h+1][w] = (dp[h+1][w] + (c2*dp[h][w-1])%mod)%mod;
            if(w+1<=W) dp[h+1][w] = (dp[h+1][w] + (c3*dp[h][w+1])%mod)%mod;
        }
    }

    cout << dp[H][K] << endl;
}