C++の練習を兼ねて, AtCoder Regular Contest 059 の 問題F (F – バイナリハック / Unhappy Hacking) を解いてみた.
■感想.
1. DPが良くわかってないので, 解説(数え上げテクニック集)を参照して実装してみた.
■C++版プログラム(問題F／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// 数え上げテクニック集 // https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view #include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 1e9 + 7; LL dp[5001][5001]; int main() { // 1. 入力情報取得. LL N; string S; cin >> N >> S; // 2. 数え上げ. // 数え上げテクニック集 に従って, dp[n][x] で 数え上げ. // n: 操作回数, x: 現在の文字列長. // ex. // n = 1: dp[1][0] = 1, dp[1][1] = 2 // => 合計 3通り. // n = 2: dp[2][0] = dp[1][0] * 1 + dp[1][1] * 1 = 3, dp[2][1] = dp[1][0] * 2 = 2, // dp[2][2] = dp[1][1] * 2 = 4 // => 合計 9通り. // n = 3: dp[3][0] = dp[2][0] * 1 + dp[2][1] * 1 = 5, dp[3][1] = dp[2][0] * 2 + dp[2][2] * 1 = 10, // dp[3][2] = dp[2][1] * 2 = 4, dp[3][3] = dp[2][2] * 2 = 8 // => 合計 27通り. int l = S.size(); dp[1][0] = 1, dp[1][1] = 2; for(int i = 1; i <= N; i++){ for(int j = 0; j <= N; j++){ // 2-1. (j - 1)文字 から j文字 に 遷移(文字 '0' or '1' を 右端 に 追加)する場合. if(j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1] * 2, dp[i][j] %= MOD; // 2-2. (j + 1)文字 から j文字 に 遷移(バックスペースキー で 右端 の 文字 を 削除)する場合. if(j + 1 < i) dp[i][j] += dp[i - 1][j + 1] * 1, dp[i][j] %= MOD; // 2-3. 0文字 から 0文字 に 遷移する場合. if(j == 0) dp[i][j] += dp[i - 1][j] * 1, dp[i][j] %= MOD; // cout << "i=" << i << " j=" << j << " dp=" << dp[i][j] << " "; } } // 3. 出力 ～ 後処理. // 数え上げテクニック集 に従って, 同じ文字数の文字列を作る場合の数が, すべて等しいとの内容を反映. // -> 2 で, S.size()回割れば良い筈 => 500000004 を 乗ずる形に修正. LL ans = dp[N][l]; for(int j = 1; j <= l; j++) ans *= 500000004, ans %= MOD; cout << ans << endl; return 0; } |