C++の練習を兼ねて, AtCoder Beginner Contest 071 の 問題D（Coloring Dominoes）を解いてみた.
■感想.
1. 動的計画法(DP)の練習問題と見て, 時間かかったものの(汗), 何とかACになったので良かったと思う.
2. コーディング後, 解説を見たら, おおよそ同じ方針だったので, とりあえず良かったと思う.
本家のサイトAtCoder Beginner Contest 071 / AtCoder Regular Contest 081 解説をご覧下さい.
■C++版プログラム.
|
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 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> #include <string> using namespace std; typedef long long LL; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) int main() { // 1. 入力情報取得. int N; cin >> N; string S1, S2; cin >> S1; cin >> S2; // 2. 動的計画法(DP)が使えるか検証. // d[0] = 0 として, d[j] が, j列目までのドミノの塗り方総数(mod 1000000007)と設定する. // d[1] は, S1[0], S2[0] が, 等しいかどうかで分岐する. LL d[53] = {}; if(S1[0] != S2[0]) d[1] = 6; // 塗り方について, S1[0] … 3色, S2[0] … 2色 を選べるので, 6通り. else d[1] = 3; // 塗り方について, S1[0], S2[0] を同じ色にする必要があり, 3通り. // 3. d[i] は, 以下のパターンに分類できると考えられる. // 3-1. S1[i-1] と S2[i-1] が等しく, S1[i] と S2[i] が等しい(パターン①). // 例) // .ab... // .ab... // // S1[i](=S2[i]) は, S1[i-1](=S2[i-1]) と異なる色を選択すればよいので, 2通り選択可能. // -> d[i+1] = 2 * d[i] // // 3-2. S1[i-1] と S2[i-1] が等しく, S1[i] と S2[i] が異なる(パターン②). // 例) // .ab... // .ac... // // S1[i] は, S2[i] 及び S1[i-1](=S2[i-1]) と異なる色を選択すればよいので, 2通り選択可能. // S2[i] は, S1[i] の塗り方に依存して決まるので, 1通り. // -> d[i+1] = 2 * d[i] // // 3-3. S1[i-1] と S2[i-1] が異なり, S1[i] と S2[i] が等しい(パターン③). // 例) // .ac... // .bc... // // S1[i](=S2[i]) は, S1[i-1], S2[i-1] と異なる色を選択すればよいので, 1通りだけ選択可能. // -> d[i+1] = d[i] // // 3-4. S1[i-1] と S2[i-1] が異なり, S1[i-1] と S1[i], S2[i-1] と S2[i] が, それぞれ等しい(パターン④). // 例) // .aa... // .bb... // // S1[i], S2[i] は, それぞれ S1[i-1], S2[i-1] と同じ色を選択すればよいので, 1通りだけ選択可能. // -> d[i+1] = d[i] // // 3-5. S1[i-1] と S2[i-1] が異なり, S1[i-1] と S1[i], S2[i-1] と S2[i], S1[i] と S2[i] が, それぞれ異なる(パターン⑤). // 例) // .ac... // .bd... // // S1[i-1] と S2[i-1] が, それぞれ, 赤, 緑 で塗られていたとすると, // S1[i] は, 緑 or 青 を塗ることが可能, S2[i] は, 赤 or 青 を塗ることが可能. // -> まとめると, (S1[i-1], S2[i-1], S1[i], S2[i]) = (赤, 緑, 緑, 赤), (赤, 緑, 緑, 青), (赤, 緑, 青, 赤) の 3通り. // -> d[i+1] = 3 * d[i] FOR(i, 1, N) { // パターン①. if(S1[i-1] == S2[i-1] && S1[i] == S2[i]) d[i+1] = 2 * d[i]; // パターン②. if(S1[i-1] == S2[i-1] && S1[i] != S2[i]) d[i+1] = 2 * d[i]; // パターン③. if(S1[i-1] != S2[i-1] && S1[i] == S2[i]) d[i+1] = d[i]; // パターン④. if(S1[i-1] != S2[i-1] && S1[i-1] == S1[i] && S2[i-1] == S2[i]) d[i+1] = d[i]; // パターン⑤. if(S1[i-1] != S2[i-1] && S1[i-1] != S1[i] && S2[i-1] != S2[i] && S1[i] != S2[i]) d[i+1] = 3 * d[i]; // d[i+1] に, mod 1000000007 を適用. d[i+1] %= 1000000007; } // 4. 出力 ～ 後処理. cout << d[N] << endl; return 0; } |
■補足.
以下のような, 入力例のテストケースが, 通過するようにプログラムの修正等を実施している.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
[入力例] 4 aabb ccdd -> 18 通りのはず(パターン④, ⑤ に分岐させて解決). [入力例] 5 aabbe ccdde -> 18 通りのはず(パターン⑤ を修正して解決). [入力例] 52 RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn -> 958681902 通り(※AtCoderテストケースより)になる必要がある(上記までの入出力例が解決したことで, 自動的に解決). |
■参照サイト
AtCoder Beginner Contest 071