ぱちぱちぱち...(maimaiのボタンを押す音)
ふぅ...
え、今日ってクリスマスコンなんですか(イブにあるとは思っていなかった顔)
これはなに
Xmas Contest 2019にチーム「TSG」で参加して、全体27位でした そのwrite upです ちょっと解説です
ごはん
クリスマスコンがあると思っていなかったので18:50くらいからいそいでごはんをたべました おいしかったです 戻ってきたのは19:15
A
256x256の画像を8x8に分割した画像がシャッフルされた状態で与えられるので、復元します。
します。
します。
します。
しま... えっ これ 何
しました。
おわりです。
K
ゲームなので私が担当するしかないですね!!!!
当然不偏ゲームなのでgrundy数を考えますね この設定ではgrundy数は「根つき木の中で何番目に小さいか(0-origin)」ですね
さてそうすると困るんですけど、{1}は{0,0,0,...,0}=n (0がn個)より真に大きいです つまりgrundyの終域を自然数にしたままだと足りないんですね。
なので...
順序数まで拡張するんですね いかなる自然数より大きい元であるところのωです ペアノの公理系のうちいかなる元の後続でもない元が0のみであるみたいな制約を取り去るとこんな感じの自然数もどきが作れますよね
順序数をとることを許すとこんな感じに計算が進んで、ぐっと睨むと計算式が出ますね
さてgrundy数が出たはいいんですけど、これのxorってどうやって取ればいいんでしょう 実はωの次数が同じものどうしで係数をxorすればいいんですね すごいでしょ そうでもないですか? これをfactとして認めて考察を進めていきます(証明には石の数が順序数まであるNimをプレイしてみるといいと思います たぶん)
grundy数が等しい <=> 根つき木として同型 なのはそれはそうですね これを使うと結局全体のgrundy数が0というのは次の条件と同値になることがわかります
根つき木 に対して、 番目の根のすぐ子にある の個数を としたとき、すべての について
同じ次数どうしでxorされるので、それはそうですね
つまり、それぞれの根の直下にある部分木を列挙して同じものをまとめることができればこれが解けたことになります。 コンテスト中に「木 同型判定」でぐーぐる検索をすると
これが来ます(ところでサムネの画像が折り畳まれてるところの画像なんですけど いいんでしょうか) えっ writerさんのブログですけど 書きます テストケースが219個あってびっくりします 落ちます
hashをこねくりまわすと結果が変わるのでhashの衝突で落ちていることがわかります ちーん まあそれはそうですけどね
さて、みなさんは決定的な根つき木の同型判定を知っていますか?私は知りませんでした... と言いたいところなんですけど、私は知っているべき立場にいたんですよね みなさんはこの問題を知っていますか 私はwriter/tester陣だったんですけど当時これが解けませんでした これの想定解法とほとんど同じ方法で根つき木の同型判定ができます
基本的に根つき木をhashにするアイデアは同じです {}を0にします 子のhashをソートした列を考えます これを今までに出てきたものと比較して、違うなら(今までで最大のhash値)+1にします 同じならそれと同じhash値にします
おわりです(trieとかで高速になるんでしょうか わかりません)
あとは各頂点に対する部分木のhashがわかっているので上の問題をunordered_mapなどのデータ構造を使って高速に解くことができます。 FAでした。 やったあ!
まとめ
とけるとたのしい みなさんも得意分野をぜひひとつ ゲームが得意なだけだったらたぶん解けてないんですけどね 運がよかったです