Typical Game Contest

参加ありがとうございました！（まだの人はやってみてねー！）

https://yukicoder.me/contests/275

 

あなたは ゲームは好きですか？

私は好きです（楽しいので）。みんなも好きだと思います。

 

 

コンテストについて

決まったテーマに沿った問題を出そうと決めていたのですが、ゲーム（特に2人対戦ゲーム）に関する問題を集めることにしてみました。

私は競プロ自体はあまり得意ではないですが、ゲーム問題は以前から好きだったのもあり、テーマを決めると案外すぐに思いつきました。

 

 

インタラクティブ問題

今回のこだわりのひとつで、ゲームコンと言うからにはちゃんと対戦もしたいなということで、インタラクティブ問題を入れることにしました。Aで練習、Dで本番という感じです。

Aがインタラクティブだったり、1コンテストで2問がインタラクティブというのも珍しい気がしていますが、ゲームコンということでご容赦ください。

インタラクティブ問題は、決してそれ自体難しいわけではなくて、慣れると解きやすいし、楽しい問題も多いと思ってます。A問題では、なるべく解きやすい問題を入れてみました。D問題は遊び心が半分です。

 

インタラクティブもスペシャルジャッジ（E問題）も初めてだったので、ジャッジはかなり神経使いました。

 

 

 

A問題

https://yukicoder.me/problems/no/1149

とりあえずゲームコンテストというからにはゲームをしましょう！ということで対戦することにしました。

この問題の作成時点で、結構難しめの問題がそろっていたので、なるべく易しめにしようとした結果、このような形になりました。

 

ジャッジでは100までの Grundy 数を前計算した配列を愚直に持っています。実はこの配列は最初間違えてたんですが、テスターのねてるくんさんに指摘してもらって修正しました。危なかったです。

あとこれもテスターさんに教えてもらったんですが、 Kayles という名前があるれっきとした（？）ゲームのようです。

 

B問題

https://yukicoder.me/problems/no/1150

解説にも書きましたが、この手の最適化ゲームって、お互いに阻止できるムーブは無視できるんですよねー。重要事項だと思うけど、競プロ界隈ではあまり浸透していなさそうなので取り入れてみました。

 

ちなみに、最初制約はもう少し小さくて、min-max 法も許容しようと思っていたのですが、 C 問題とかぶるので後から変えました。

 

ところでちょうど作問してからコンテストまでの間にあったこどふぉでも似たようなのがありましたね。

https://codeforces.com/contest/1383/problem/B

 

そのこどふぉ後、いろいろ解説ツイートしようとしたんですが、この問題の言及になりそうだったので雑にごまかしました。

 

ちなみに、ここ1か月でゲーム問題に関するツイートをたくさん見かけてコメントしたいこともたくさんあったんですが、言及をさけるためにほとんどふぁぼ付けるだけにしてしまいました。

 

C問題

https://yukicoder.me/problems/no/1151

確率的な（確定的じゃない）ゲームも1問は出そうと思っていました。

min-maxするだけと言えばそれだけだけど、ちゃんと証明するのは結構難しかったかもしれません。私も苦労しました。テスターのつるさんともかなり議論して、助けてもらいました。

存在証明もつるさんが詳しく書いてくれました。バナッハの不動点定理って何ですか。

 

戦略についてですが、実際にどういう場合にどれが最適かというのは結構組合せ次第なので難しいです。（単に大きいやつが良い、小さいやつが良い、という訳ではないです。）

 

例えば、カードが 1, 20, 20 なら 1 の価値がめちゃくちゃ大きいです。20は簡単に取れないのでランダムに配られると思うと、1を持っている方が 3/4 ぐらいの確率で勝てます。

逆に 1, 18, 20 なら 1 に価値はないです。

 

3, 4, 5, 10, 15 だとどれが良いでしょうか？

答えは 4 です。これだと 19 取った方が勝つので、4 を取るとあと 15 取ればよいので効率が良いです。ちなみに、4を取った（取られた）後は5と15が同率で最善です。

 

3, 4, 5, 10, 12 だとさらにややこしいです。

この場合、先手は 5 、後手は 3 を狙うのが最善です。先手は 18 取らないといけないので、 5 を取ったあとは 3 → 10 を狙います。

後手は 17 取れば良いので、3 を取った後は 4 → 10 を狙います。

 

リアルでやってみても結構面白いゲームになりそうです（ほんと？）。

 

ちなみに、実装にあたっては 3^n の形で持つより、 2^n と「必要な得点」でメモ化すると先手・後手をまとめてきれいに書けます。

先手と後手の違いの処理は、全部のカードを2倍して後手に1点あげておくとかでもできます。

てか解説に書けよって話ですね。（証明が気になりすぎて、実装面まで気が回ってませんでした。）

 

D問題

https://yukicoder.me/problems/no/1152

ゲームコンという意味では目玉問題のつもりでした。いろいろ実験すると解けたんじゃないかなと思います。

 

元ネタは、子供のときにみた何かの付録についていた問題で、一旦遠くまで（と言っても3マスぐらい）行くと偶奇が調整できて捕まえられるというのがあったので、思い出して入れてみました。

 

f_4 の書き方が若干いじわるな感じがしたけど、発見したときに嬉しいかなと思ってそのままにしておきました。

想定ムーブはこんな感じでした。

 

割とそんな感じの方が多かったのでしょうか。

 

 

E問題

https://yukicoder.me/problems/no/1153

全方位木DPの問題です。慣れている人にとっては、（★4にしては）解きやすかったかもしれません。

 

全方位木DPは 前回の出題 に引き続き2連続なので、ワンパターンだと言われるとごめんなさいになります。が、シンプルな設定で気に入ったので出してみました。

判定だけにしようか迷ったけど、最初の1手を答えることにしました。テストケース特定で簡単にACできてしまうので。

結果的にスペシャルジャッジをすることになりましたが、Aでしくっていたのもあり、コンテスト中もこれが一番心配でした。

ジャッジの方法は、結構迷ったのですが、前計算した Grundy 数の結果を出力ファイルに持たせています。その方がジャッジが若干速くなるので。（ファイルが重すぎてアップロードが一気にできないのが大変でした。ユーザーレベル（？）が上がると容量増えるんでしょうか。）

 

F問題

https://yukicoder.me/problems/no/1154

これは難問です！証明もちゃんと書くと簡単な論文が書けるんじゃないかというレベルです（言い過ぎ？）。ただ、設定はとてもシンプルなので、既出じゃないかは怖かったです。

逆にAC者いなかったらどうしようという不安もあったのですが、まるーんさんが通してましたね（しかも全完！）。天才すぎる。

 

 

一応、B問題の考え方が少しヒントになっています。

あと、証明は何度もしたつもりですが、最後まで自信がなかったです。ちなみにテスター募集時点ではまだ細かい証明はできていなくて、その後頑張って考えた感じです。解説ページも、直前まで書き直したり記号を変えたりしてました。

マージテクについてはテスターののいみさんに教えてもらいました。制約を 10^5 にするのも提案されたのですが、 Python で（私の実装では）全然間に合わず断念しました。

 

 

公開設定

設定で迷ったのは、公開設定です。

Writer をやった人は知ってると思いますが、解説などは「ACで公開」か「コンテスト終了後に公開」か選べるようです。

ゲームコンということで似たような問題が多いので（ Grundy 数とかがAの別解で出てきたり、Bの解説がFのヒントになったり、・・・）一律「コンテスト終了後に公開」にしようと思ってました。

でもジャッジミスとかがあったときに早めに指摘してくれるのかなと思ってやっぱり「ACで公開」に変えました。ジャッジ不安だったので。。

 

コンテスト中の心境

序盤いくつか質問が来て焦りましたが、問題文などに大きな誤りはなかったようなのでとりあえず良かったかなと思います。 

 

難易度設定が失敗だったかな。。ゲーム問題では典型（？）だけど、競プロ問題の中では決して典型ではないので、AC数の予測が難しかったというのはあるかも（言い訳）。

投票も参考に、コンテスト後にこっそりAとBの難易度を0.5ずつ上げておきました。

 

 

（参考）前回の記事

https://kiri8128.hatenablog.com/entry/2020/06/10/014306

 

気を付けた点などは今回もほぼ同様でした。 「証明」が難しいのがあったので（ C 問題、 F 問題）、そこは前回にはなかったポイントでした。

 

 

参加してくれたみなさん、ありがとうございました。

いろいろ教えてくれたテスターのみなさんにも感謝です！