ARC064-D、500点。解き心地の良い問題でした。
考察の流れ
わからないのでとりあえず手を動かしてみます。
話をすっ飛ばして、手を動かした結果わかったことをここに書きます。
- 文字列の両端の文字は消すことができないので、ゲーム開始前とゲーム終了時の文字列で両端の文字は変わりません。
- 終了時の文字列は必ず1種類または2種類の文字から構成されています。(それ以上含むと必ずまだ消せる文字があることは実験するとなんとなくわかると思います)(証明は3種類目の文字周辺の状態を全て列挙することでできると思います)
この二つのことから
- sの両端の文字が同じ → 終了時の文字列の長さは奇数 (abab...aba のようになります)
- sの両端の文字が異なる → 終了時の文字列の長さは偶数 (abab..ab のようになります)
ということが言えます。
これを用いると文字列の長さの減りの偶奇がわかるので、最終状態に至るまでの操作回数の偶奇がわかります。
偶数回の操作をして最終状態に至れば青木君の、奇数回ならば高橋君の勝利となるので、要するに「sの両端の文字」「最初のsの文字数」からどちらが勝つか判定できるわけです。
僕の場合は真面目に頭を使って計算するよりも、入出力例と自分で作ったサンプルケースに前述の考察を当てはめて適当に考える方が早いし楽だったのでそうしました。あんまりよくないかも
結果です。
こういうのってどれぐらい簡潔に書くか、どれぐらい親切に書くかちょっと悩みますよね
ソースコード
bool found[26]; long cnt; std::string s; int main(){ std::cin >> s; long same = (s[0] == s[s.length() - 1]); long even = s.length() % 2; if((same + even) % 2){ printf("First\n"); }else{ printf("Second\n"); } return 0; }
感想
こういう感じの問題はわからなかったらとりあえず手を動かすことにしています。
どちらかというと、サンプルを眺めたり手を動かしたりしながら全てのケースに共通する法則を探してる感じがします。
ところで、2人が別に最適な戦略を取らなくても、どうやっても最終的に勝つ人が決まっているのって面白くないですか。