競プロをはじめた家事手伝いロボットのブログ

競技プログラミングをしている家事手伝いロボットのブログです

クリスマスコンテスト2019 write up

ぱちぱちぱち...(maimaiのボタンを押す音)
ふぅ...
え、今日ってクリスマスコンなんですか(イブにあるとは思っていなかった顔)

これはなに

Xmas Contest 2019にチーム「TSG」で参加して、全体27位でした そのwrite upです ちょっと解説です

atcoder.jp

ごはん

クリスマスコンがあると思っていなかったので18:50くらいからいそいでごはんをたべました おいしかったです 戻ってきたのは19:15

A

256x256の画像を8x8に分割した画像がシャッフルされた状態で与えられるので、復元します。

f:id:MMNMM_259:20191224233940p:plain

します。

f:id:MMNMM_259:20191224234000p:plain

します。

f:id:MMNMM_259:20191224234045p:plain

します。

f:id:MMNMM_259:20191224234109p:plain

しま... えっ これ 何

f:id:MMNMM_259:20191224234127p:plain

しました。

おわりです。

K

ゲームなので私が担当するしかないですね!!!!

f:id:MMNMM_259:20191224234636p:plain
チームSlackに噴出する欲求

当然不偏ゲームなのでgrundy数を考えますね この設定ではgrundy数は「根つき木の中で何番目に小さいか(0-origin)」ですね

さてそうすると困るんですけど、{1}は{0,0,0,...,0}=n (0がn個)より真に大きいです つまりgrundyの終域を自然数にしたままだと足りないんですね。

f:id:MMNMM_259:20191225000050p:plain
困り

なので...

f:id:MMNMM_259:20191225001542p:plain
これなに

順序数まで拡張するんですね いかなる自然数より大きい元であるところのωです ペアノの公理系のうちいかなる元の後続でもない元が0のみであるみたいな制約を取り去るとこんな感じの自然数もどきが作れますよね

順序数をとることを許すとこんな感じに計算が進んで、ぐっと睨むと計算式が出ますね

f:id:MMNMM_259:20191225003806p:plain
ウッ

さてgrundy数が出たはいいんですけど、これのxorってどうやって取ればいいんでしょう 実はωの次数が同じものどうしで係数をxorすればいいんですね すごいでしょ そうでもないですか? これをfactとして認めて考察を進めていきます(証明には石の数が順序数まであるNimをプレイしてみるといいと思います たぶん)

grundy数が等しい <=> 根つき木として同型 なのはそれはそうですね これを使うと結局全体のgrundy数が0というのは次の条件と同値になることがわかります

後手必勝と同値な条件

根つき木 \tau に対して、i\ \ (0\leq i\leq k) 番目の根のすぐ子にある \tau の個数を a_{\tau,i} としたとき、すべての \tau について a_{\tau,0}\;\mathrm{xor}\;a_{\tau,1}\;\mathrm{xor}\;\cdots\;\mathrm{xor}\;a_{\tau,k}=0

同じ次数どうしでxorされるので、それはそうですね

つまり、それぞれの根の直下にある部分木を列挙して同じものをまとめることができればこれが解けたことになります。 コンテスト中に「木 同型判定」でぐーぐる検索をすると

snuke.hatenablog.com

これが来ます(ところでサムネの画像が折り畳まれてるところの画像なんですけど いいんでしょうか) えっ writerさんのブログですけど 書きます テストケースが219個あってびっくりします 落ちます

hashをこねくりまわすと結果が変わるのでhashの衝突で落ちていることがわかります ちーん まあそれはそうですけどね

さて、みなさんは決定的な根つき木の同型判定を知っていますか?私は知りませんでした... と言いたいところなんですけど、私は知っているべき立場にいたんですよね みなさんはこの問題を知っていますか 私はwriter/tester陣だったんですけど当時これが解けませんでした これの想定解法とほとんど同じ方法で根つき木の同型判定ができます

www.hackerrank.com

基本的に根つき木をhashにするアイデアは同じです {}を0にします 子のhashをソートした列を考えます これを今までに出てきたものと比較して、違うなら(今までで最大のhash値)+1にします 同じならそれと同じhash値にします

おわりです(trieとかで高速になるんでしょうか わかりません)

あとは各頂点に対する部分木のhashがわかっているので上の問題をunordered_mapなどのデータ構造を使って高速に解くことができます。 FAでした。 やったあ!

まとめ

とけるとたのしい みなさんも得意分野をぜひひとつ ゲームが得意なだけだったらたぶん解けてないんですけどね 運がよかったです