Xmas Contest 2018 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

Xmas Contest 2018 今年も開催しました。
コンテスト密度の高い中、ご参加いただいた皆さまありがとうございました。
楽しんでいただけたでしょうか？（よろしければアンケートお願いします）

今年の運営は４年連続のじゃっぷるさんと、2010~2014の運営の本家本元hosさんとやりました。
hosさんが数学的に面白くて奥深い問題とかをどんどん出していてすごかったです。さすが。
特にxorのやつはまじですごいのでおすすめです。クッソむずいですが。
diceの問題も楽しかったです。（楽しくなって作った謎ゲーム）

自分が原案の問題の解説を書いておきます。

A - Art Time

難問枠はhosさんから無限に湧いてくるので、なんかお手軽なwelcome枠を作ろうと思って用意しました。
今年のICPCアジア地区の四色定理の問題が面白かったので、四色問題にしてみました。

想定解などは特にありません。
ペイント等で頑張ってください。右クリックでスポイトツールが使えるようになっていると捗ります。
あるいは、スクリプトのコードに埋め込んであるグラフデータを使ってプログラムで探索するというひねくれた別解もありですね。
FAは ILJJ さんの 1:42 でした。早すぎです（驚

準備が地味に大変で、非自明な問題図を作るのに苦労しました。
あとグラフデータ作成もミスりがちなので、プログラムで生成したりしました。

非自明な問題図の作り方

適当に分割すると左上から適当に塗っていくだけであっさり解けちゃうので結構悩みました。
四色問題といえば、エイプリルフールのジョークで出題された問題が有名で、この図からヒントを得ました。
僕が出題した問題は下図のような構造に近いものになっています。

f:id:snuke:20181224225739p:plain

すなわち、何層かの輪に分かれていて、中心→外になるにつれて分割の個数が少→多→少というようになっています。
中心から塗り始めても外から塗り始めても、中盤までは選択肢が多いのに、逆側の"少"の部分にたどり着いた瞬間に制約が一気に厳しくなるので、大規模な修正を余儀なくされる可能性が高まるというわけです。

あと、最初の図案では文字の部分を同じ色で塗る解が存在したので、XとCの間に完全グラフっぽい仕掛けを置くことでそれを回避したりもしました。

おまけ：自分は何を血迷ったのか、頭のおかしい配色で解きました。 f:id:snuke:20181224224217p:plain

G - Good Game

それは 12/24 コンテスト当日明け方のこと...

f:id:snuke:20181224232139p:plain

あと１問簡単めなのが欲しいかもという雰囲気だったので、（←???）
お風呂に入りながら「そういえばリアクティブないなぁ」とか考えてたら思いついた問題でした。

まずは部分点解法。
こういう問題でありがちなのは真似っこ戦略で、部分点だと普通に使えます。
要は後手を選んで、相手の手が(i,j)だったときは(i,W-1-j)に置けば良いんです。

次に満点解法
戦略自体はとても簡単です。
以下のようにマスを畳状にペア分けしてみます。
f:id:snuke:20181224234506p:plain

そして、相手が畳の片方のマスに石を置いてきたら必ずもう片方のマスに石を置くことにします。（畳以外のマスに置いてきた場合は畳以外のいずれかのマスに置くことにします）
すると、「各畳内では石の色が必ず異なる」という条件を満たすことができます。
ここで、2*2のブロックというのはどこに置こうと必ず１つの畳を完全に含むことにを考えると、「各畳内では石の色が必ず異なる」という条件が満たされている以上は絶対に2*2の同じ色からなるブロックはできないことが言えます。
つまり、この戦略を徹底すれば全部のマスに石を置けることになるので、H*Wが奇数なら先手/偶数なら後手を取れば必ず勝てることになります。

「ここに置いてきたらここに置く」という対応を決めておいてそれに従って置いていけば何らかの条件を満たすため必勝、というテクニックもゲーム系でたまに出てくるので覚えておくと良いでしょう。

おまけ

D問題

writer,tester３人とも各々の方法で全探索を書いた。
埋め込みが想定解でしたが、なぜかそれで通した参加者はいなさそうだった。
じゃっぷるさんの全探索は0.1s/1ケースくらいまで高速化されていて埋め込まずに通るのですごい。

とりあえず自分の全探索の方針を書いておく

まず、引き分けは意味がないので目はdistinctとしてよい
M個のサイコロであって、サイコロ i のサイコロ i+1 (mod M) に対する勝率がX/K^2以上のものを探すことにする
以下のような有向グラフを考える

「サイコロ i の大きい方から j 番目の目」の値を $x_{i,j}$ とし、これに対応する頂点 $v_{i,j}$ を作る
であるような場所全てにの有向辺を張る（ただしi=M-1のとき、i+1は0）
- 各サイコロ間にはX本以上の辺が張られる

正しい解において、このグラフはDAGになっているはずである

逆にこのような有向グラフであってDAGになっているものを見つければ、トポロジカル順を割り当てることでサイコロの目を構成できる
サイコロ間の辺の張られ方は O( ${}_{2K} C_K$ ) 通りある（ $x_{i,j} \gt x_{i,j+1}$ により単調性のある感じにしか辺を張れない）
これをM層組み合わせてDAGを作れるかを全探索できればいい
DAGになる条件は以下の通り

$v_{0,j}$ から（ $v_{M-1,*} \to v_{0,*}$ の辺を通らずに）到達できる頂点 $v_{M-1,j'}$ について、 $v_{M-1,j'}$ と $v_{0,j}$ を結ぶ有向辺が存在しない

辺の張り方の制約から単調性があることに注意すると、「 $S_{i,j}$ = $v_{0,j}$ から $v_{i,j'}$ 到達できるような $j'$ のうちの最小値」という $S_i$ だけを状態として考えれば十分である
層を増やしながら $S_i$ として出来うるものを求めていき、DAGの条件を満たすような $S_M$ が存在するかをチェックすればいい