CADDi 2018 Beginners: D - Harlequin

問題

CADDi 2018 Beginners: D - Harlequin

自分の考察

　まず、 のときを潰した。その次に、 のときを書き出した。 のときはサンプルにある通り。 のときを考えたときにパターンとして、

• 自分が引いて全てを 2 にすることができれば勝ち。
  自分が引く ->

• が つ、それ以外は or というパターンの時に自分が引ければ勝ち（ が つという状況を相手に引かせれば勝ち）
  -> 自分が引く ->

を思いついたが、どのように計算すれば良いか分からなかった（見当違いだった...）。最終的には書き出していた例から の和が偶数なら通るかもしれないという考えから、それを実装したが WA が 3つ出て解決できずに終了。

解法

• 公式解説

　解法は、全ての色が偶数個であればsecond、それでなければfirstというとてもシンプルな解法だった（自分が書いた全ての和が偶数だと奇数が偶数個ある場合にだめといいうことか）。
以下解説から引用。

理屈を説明します。
・「どの色のりんごも偶数個」という状態を E(Even)、
・「いずれかの色のりんごが奇数個」という状態を O(Odd)
とする。

現在の状態が E の場合、
すでに「全色 0 個」(相手が勝った) でなければ、どのようにりんごを食べても食べた色のりんごが奇数個になり、必ず O に移ります。
一方で現在の状態が O の場合、
奇数個の色のりんごだけを 1 個ずつ食べることで E に必ず移れます。よって、初期状態が E の場合、後手が先手の「真似」をすると先手は E に閉じ込められ、いずれ「全色 0個」に至り負けます。初期状態が O の場合は、先手は最初に奇数個の色のりんごだけ食べて後手に E を押し付け、それ以降は後手の真似をすることで勝てます。

なお、コンテスト中にこの結論にたどり着くには、(メモ化) 再帰により小さいケースを解くプログラムを書いたり、N = 2 のケースを紙と鉛筆で解くことで実験して仮説を立てる方法もあります。

　正直なところ自分はこの解説を読んでももやもやした。解説放送では、表を使ってその時々の勝ち負けを導き、パターンを見つけるという実験をしていた。自分は数を固定して、実験していたが、表を作れば状態の遷移が分かりつつ勝ち負けがわかるので、網羅的に探せる。表を使ってパターンを列挙する実験方法を知らなかったのでここで覚えておきたい。

　以下、実験の表を書いてみた。

　色が2色の時、それぞれのりんごの数を とする。各マスは「あなた」（以下、自分）の手番 のとき自分が勝つ(Win)か負ける(Lose)かを表す。例えば、自分の手番で ならば、食べることができないので（相手に最後のりんごを食べられた状態） L と書く。 現在の手番から相手が負けるという手番に「移行」することができれば、自分の勝ちとなる 。「移行」とは、現在のマスから「左 or 上 or 左斜め上」に移動することである（少なくとも1つは食べる）。

　このようにして、 がどれも偶数の時にsecondの勝ち、そうでないときにfirstの勝ちというパターンが見えてくる。実装は非常にシンプルである。（自分は帰納的に証明ができないなかったのでTLで探そうと思う）

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; ++i) cin >> vec[i];
    
    // calc
    for (int j = 0; j < N; ++j) {
        if (vec[j]%2 != 0) {
            cout << "first" << "\n";
            return 0;
        }
    }
    cout << "second" << "\n";
    
    return 0;
}

　実験を適切に行えるか否かが、C問題以降を解けるかどうか大きく異なると思った。詰まった時はまずは簡単なもの実験することを心がけたい。

実験するときのポイント

• 最適に行動する = 相手がどういう操作をしてきても必ず勝つような動き方があるのならばそれをやる

• まずは簡単に結果を出せるものを考える。必要があればプログラムを書いてより複雑な例を考えてみる。

反省点

　C問題は、WAを出してから落ち着いて条件を考えてACできたのでそれは自分にとっては進歩だと思った。D問題に関しては、C問題を解けたことにより少し気が抜けて考察を丁寧に粘り強くしなかったことが良くなかった。300点以上の問題にも尻込みせず果敢に挑まねば緑・水色は見えてこないなあ。

リンク

あとで見るかも知れないゲーム問題のリンク。

• 競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析]
• 競プロにおけるNim、Grundy数とNimK
• grundy数を習得したかった