C++の練習を兼ねて, AtCoder Beginner Contest 129 の 問題E (E – Sum Equals Xor) を解いてみた.
■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. 相変わらず苦手な DP の訓練となったと思う.
本家のサイトABC 129解説をご覧下さい.
■C++版プログラム(問題E／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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
// 解き直し. // ABC 129解説. // https://img.atcoder.jp/abc129/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 1e9 + 7; char L[123321]; LL dp[123321][2]; int main() { // 1. 入力情報取得. scanf("%s", L); // 2. 解説通り. // ex. // L = 10 の 場合. // L[0] = 1 L[1] = 0 // ----------------------------------------- // dp1 dp1[0] = 1 dp1[1] = dp1[0] * 3 + dp2[0] * 1 = 5通り // ※(A, B) = (0, 0) ※第1項: (A, B) = (0, 0) // ※第2項: (A, B) = (0, 0) // ----------------------------------------- // dp2 dp2[0] = 2 // ※(A, B) = (0, 1), // (1, 0) // // L = 101 の 場合(※前述の考え方を踏襲). // L[0] = 1 L[1] = 0 L[2] = 1 // ------------------------------------------------------------------------- // dp1 dp1[0] = 1 dp1[1] = dp1[0] * 3 dp1[1] = dp1[1] * 3 // + dp2[0] * 0 + dp2[1] * 3 = 15通り // ------------------------------------------------------------------------- // dp2 dp2[0] = 2 dp2[1] = dp2[0] // // L = 111 の 場合(※前述の考え方を踏襲). // L[0] = 1 L[1] = 1 L[2] = 1 // ------------------------------------------------------------------------- // dp1 dp1[0] = 1 dp1[1] = dp1[0] * 3 dp1[1] = dp1[1] * 3 // + dp2[0] * 1 + dp2[1] * 3 = 27通り // ------------------------------------------------------------------------- // dp2 dp2[0] = 2 dp2[1] = dp2[0] * 2 // 2-1. L = '1'. int l = strlen(L); if(l == 1){ printf("%d\n", 3); return 0; } // 2-2. L[0] ～ L[l - 2] を 確認. dp[0][0] = 1, dp[0][1] = 2; for(int i = 1; i < l - 1; i++){ // dp[i][0] の 更新(i桁目 が '0' or '1' で 処理 を 分岐). if(L[i] == '0') dp[i][0] = dp[i - 1][0] * 3; else dp[i][0] = dp[i - 1][0] * 3 + dp[i - 1][1]; // dp[i][1] の 更新(i桁目 が '0' or '1' で 処理 を 分岐). if(L[i] == '0') dp[i][1] = dp[i - 1][1]; else dp[i][1] = dp[i - 1][1] * 2; // MOD. dp[i][0] %= MOD, dp[i][1] %= MOD; } // 2-3. L[l - 1] を 確認. dp[l - 1][0] = dp[l - 2][0] * 3; if(L[l - 1] == '0') dp[l - 1][0] += dp[l - 2][1], dp[l - 1][0] %= MOD; else dp[l - 1][0] += dp[l - 2][1] * 3, dp[l - 1][0] %= MOD; // dp確認. // for(int i = 0; i < l; i++) printf("%lld ", dp[i][0]); // printf("\n"); // for(int i = 0; i < l; i++) printf("%lld ", dp[i][1]); // printf("\n"); // 3. 出力 ～ 後処理. printf("%lld\n", dp[l - 1][0]); return 0; } |
|
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 53 54 55 56 57 |
[入力例] 10 [出力例(debug版)] 1 5 2 0 5 ※AtCoderテストケースより [入力例] 1111111111111111111 [出力例(debug版)] 1 5 19 65 211 665 2059 6305 19171 58025 175099 527345 1586131 4766585 14316139 42981185 129009091 387158345 162261460 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 0 162261460 ※AtCoderテストケースより [入力例] 101 [出力例(debug版)] 1 3 15 2 2 0 15 [入力例] 111 [出力例(debug版)] 1 5 27 2 4 0 27 [入力例] 10101 [出力例(debug版)] 1 3 11 33 111 2 2 4 4 0 111 [入力例] 101010 [出力例(debug版)] 1 3 11 33 103 317 2 2 4 4 8 0 317 [入力例] 10100100010000100000100000010000000100000000100000000010000000000 [出力例(debug版)] 1 3 11 33 99 301 903 2709 8127 24389 73167 219501 658503 1975509 5926543 17779629 53338887 160016661 480049983 440149942 320449851 961349553 884048645 652145921 956437756 869313254 607939748 823819301 471457889 414373660 243120973 729362919 188088743 564266229 692798680 78396154 235188462 705565386 116696144 350088432 50265289 150795867 452387601 357162796 71488637 214465911 643397733 930193192 790579562 371738672 115216009 345648027 36944074 110832222 332497178 997491534 992474588 977423750 932271236 796813694 390441068 171323197 513969591 541908766 625727315 2 2 4 4 4 8 8 8 8 16 16 16 16 16 32 32 32 32 32 32 64 64 64 64 64 64 64 128 128 128 128 128 128 128 128 256 256 256 256 256 256 256 256 256 512 512 512 512 512 512 512 512 512 512 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 0 625727315 |
■参照サイト
AtCoder Beginner Contest 129