SRM663 Div1 Easy "ABBADiv1"
解法
最終的にinitialが反転しないで終わったのか、反転して終わったのかを決め打つ。
■反転しないで終わった時の条件
target = 左側の文字列 + initial + 右側の文字列 とすると、 ・左側と右側の文字列で、含まれる'B'の数が一致する事 ・左側の文字列の最初が'A'でないこと
■反転して終わった時の条件
target = 左側の文字列 + initial(反転) + 右側の文字列 とすると、 ・左側と右側の文字列で、含まれる'B'の数が左側の方が1つ多い事 ・左側の文字列の最初が'A'でないこと
事後
ヒントなしで解けたけど、なんか回りくどい方法・・
反対に考えてtarget->initialにできるか?を考えるとよかったポイ
ソースコード
class ABBADiv1 { public: string canObtain(string initial, string target) { int n = initial.size(); int m = target.size(); // 順 for (int i = 0; i <= m - n; i++) { bool match = true; for (int j = 0; j < n; j++) { if (target[i + j] != initial[j]) match = false; } if (!match) continue; int lb = 0; for (int j = 0; j < i; j++) { if (target[j] == 'B') lb++; } int rb = 0; for (int j = i + n; j < m; j++) { if (target[j] == 'B') rb++; } if (lb != rb) continue; if (i != 0 && target[0] == 'A') continue; return "Possible"; } // 逆 reverse(initial.begin(), initial.end()); for (int i = 0; i <= m - n; i++) { bool match = true; for (int j = 0; j < n; j++) { if (target[i + j] != initial[j]) match = false; } if (!match) continue; int lb = 0; for (int j = 0; j < i; j++) { if (target[j] == 'B') lb++; } int rb = 0; for (int j = i + n; j < m; j++) { if (target[j] == 'B') rb++; } if (lb != rb + 1) continue; if (target[0] == 'A') continue; return "Possible"; } // 無理ぃ return "Impossible"; } };