yukicoder contest 399開催記

2023/07/28

コンテストURL: https://yukicoder.me/contests/452

7/20（コンテスト8日前）。全ての始まりです。長らくコンテスト予定が詰まっていたyukicoderでしたが7/28のコンテスト枠に久しぶりの空きが出ており、運営さんからコンテストの募集がかかっていたので突発的に枠を入れさせてもらいました。

準備期間は8日間と短めですが、完成済みの問題ストックから６問程度を放出して高難易度コンテストにするつもりだったので特に心配はございませんでした。ただコンテストを参加者の皆様になるべく楽しんでいただけるように、統一感を持たせるべく全体のテーマを設定できたらしたいと思っており、どの問題を選出しようか考えておりました。

するとそこへhiro1729さんがご自身の作問中の問題（本コンテストのB問題）も追加して共同での開催にして欲しいとご相談してくださり、１つ問題が決まればテーマも決めやすいこと、そしていつか共同コンテストを主催したいと思っていたことからこれ幸いと承諾いたしました。これまではオムニバスコンテストに応募して出題させていただくことはありましたが、実力的にまだtesterできる問題の難易度が狭いため自分で共同コンテストを主催することはなく、今回が初の共同コンテスト主催です。もちろんとても緊張しました。

ちなみに元々B問題はこちらがtester兼テストケース作成等の作問補助を引き受けていた問題です。共同コンテストを成功させるにはまず残り8～9日間でB問題を完成させなければなりません。当時の時点では問題文が未完成で解説が空欄の状態だったのでそこそこの不安を覚えつつも、コンテスト当日はhiro1729さんが待機できないかもしれないとのことだったので、なるべく本番で質問が来ないようにtesterとして問題の完成度をできる限り高めようと意気込みました。

7/21（コンテスト7日前）。更にhiro1729さんがもう１問（以下B’問題）思いついたとのことで（そして問題と解法をうっかり聞いてしまったため）そのtesterもお引き受けし、せっかくなら原案より少し高難易度にして今回のコンテストにそちらも合わせて２問出題したいというご本人のご要望を受けそちらの作問作業もお手伝いさせていただくことになりました。どちらも魅力的な問題で、これらを２問とも出題できたら難易度のバランスもよくきっと良いコンテストになるだろうと思いました。

7/22（コンテスト6日前）。朝の時点でB’問題の入力制約や解法が思いついていらっしゃらないご様子だったことに加えて、hiro1729さんが7/22～23はご多忙なため作問作業が進められないことが分かっていたことから、さすがに不安になり万が一当日ギリギリまで完成しなかった場合の事故が怖い旨を正直に吐露し、完成期限を少し早めに設定した方が良い旨をご相談しました。名残惜しいですが結局その問題案は温存しておいてまた別の機会に出題なさるということになりました。

7/23（コンテスト5日前）。日頃いくつかの問題をtesterさん方にチェックしていただいているのですが、ちょうどいいタイミングでその１つが完成しました。それがB問題と同じく整数の問題であったため、これらを軸にコンテストのテーマを設定できるのではないかと思い、元々予定していた１問を外し完成したてのその問題をD問題に据えることにしました。それにより無事コンテストのテーマ（後述）も決まり、テーマに合わせて残りの問題選出も固定できました。

ただC・D問題（この時点でともに★2.5設定）の難易度順に不安があったため、あまりにも著しい難易度反転が置きていないかをチェックしてもらうためにC・D問題のみの全体（？）testerを募集させていただきました。前回のコンテストでE問題（★2.5）とF問題（★3）の間で著しいAC数反転を起こしてしまったことの反省を活かして、できるだけ★2.5付近の難易度評価を正確にしたいという気持ちです。もちろん残り日数的に、応募があればラッキーという程度の認識ですが。

7/24（コンテスト4日前）。hiro1729さんからB問題の解説をこちらにお任せできるかのご相談をいただいたので承諾し、代わりに問題文の完成に集中していただくことにしました。問題の性質上解説にかなり時間が掛かりそうだと見積もっていたため、完成のタイミングが分からないよりは自分で引き受けた方が安心だと思っていたのでこれ幸いとできる限り丁寧な解説を書かせていただきました。そしてついに問題文と解説が無事完成！　後はC・D問題のみの全体testerさんのご応募を待ちつつコンテストを迎えるだけ！

7/25（コンテスト3日前）。C・D問題のみの全体testerさんの募集に特に進展もなかったので、他のコンテストのtesterを２件引き受けて解いていました。作問が楽しいのと同じくらいtester作業は楽しいですね。

7/26（コンテスト2日前）。C・D問題のみの全体testerさんのご応募がないままコンテストが近づいてきました。このまま見つからないかなあと思いきや、hiro1729さんがご応募くださいました！　C・Dの難易度順はあっている一方でDが★2.5より高めだとご評価していただいたため、★3に難易度を上方修正しました。２人分のご意見をいただけてとても安心です。次回のコンテストでも★2.5付近は慎重に難易度評価をするため全体testerさんを募集したいところですね。

7/27（コンテスト前日）。コンテストの準備が万全に整ったので、しばらくサボっていた「直近の★3埋め」（自分が競プロの勉強を始めて以降に出題された★3のみを埋める練習方法）を少し進めました。３問解けたには解けましたが、相変わらず解くのが遅いです。３問とも、考察はすぐ終わって実装に手間取るパターンでした。解き方が悪いのかと思いきや、３問とも想定解です。

単に★3埋めの最中なので考察の傾向を掴めて（ある種ヒントを得ているようなもので）たまたま考察が早く済んでいるだけで実力は伴っておらず、結果的に実装の遅さに実力が現れている感じがします。実装の遅さはライブラリーの拡充である程度補えてきましたが、それとは別に問題数をこなしてリアルタイムの実装力も鍛えなきゃいけませんね。

7/28（コンテスト当日）。いよいよ迎えた本番です。思い返せば前回のコンテスト開催は3ヶ月も前の4/14でした。ちょうどyukicoderのコンテスト予定がぎっしり詰まっている時期だったため１ヶ月待ちでその間ずっと緊張していましたが、今回は１週間強の緊張で済んだため結果的には気持ちに余裕を持ってコンテストを迎えることができました。毎回こんな感じだと嬉しいですね。

こうしてコンテストを終えてみて、とにかく無事大きな事故もなく済んで安心しています。参加者の皆様、testerの皆様、B問題をご提供いただいたhiro1729さん、そしてご質問をしていただいた皆様にこの場を借りてお礼申し上げます。

前回の開催記で「逆に１つの分野に集中させたコンテストも開いてみたいと思います」と述べたことを踏まえて、今回は「数の表示」をテーマに問題を集めさせていただきました。

A問題二平方和：平方数の和による、素数の表示
B問題 Bit Grid Connected Component：$2$進法による、正整数の表示
C問題部分和乗総和：冪乗の和の、積による表示
D問題区間二次変換一点取得：非線形漸化式の一般項の、行列積による表示
E問題等差二項展開：冪根を添加した数体系における冪乗の、二項係数による表示
F問題 ω冪：順序数の、カントール標準形による表示
G問題ヒドラ崩し：順序数の、ヒドラゲームによる表示前回は代数・幾何・解析・論理からバランスよく出題させていただきましたが、今回はテーマがテーマなだけに整数・代数・論理に出題分野が集中しており幾何・解析を期待していた方々には厳しいコンテストとなったかもしれません。

それでも自分の専門が整数論であり数に対する思い入れが強いため、数に対する苦手意識を持っていらっしゃる方々も解説を読んで楽しんでいただければという思いで解説もなるべく丁寧に書かせていただきました。現在開催準備中の線形代数コンテストと基礎論コンテストも丁寧な解説を心がけておりますので、開催の際はぜひよろしくお願いいたします。

A: No.2392 二平方和 ★☆
問題リンク：https://yukicoder.me/problems/no/2392 tester：MZKiさん
整数論、特に初等整数論です。愚直解はもちろん通りますが、二平方定理をご存知の人は更に高速に実装できる問題です。ただし定理の主張をうろ覚えにしていると不正解となり逆に時間がかかってしまうかもしれません。実際に本番では結構$4$で割った余りが$1$か否かで場合分けをしてしまった提出が多かったですね。この問題自体は$P$が素数であるという制約がなくても解けるわけですが、こういう余計な制約がついていることに疑問を抱いた参加者の方々が解説を読んで二平方定理に触れる機会を提供できればという意図で出題させていただきました。

A: No.2392 二平方和 ★☆

問題リンク：https://yukicoder.me/problems/no/2392

tester：MZKiさん

整数論、特に初等整数論です。愚直解はもちろん通りますが、二平方定理をご存知の人は更に高速に実装できる問題です。ただし定理の主張をうろ覚えにしていると不正解となり逆に時間がかかってしまうかもしれません。実際に本番では結構$4$で割った余りが$1$か否かで場合分けをしてしまった提出が多かったですね。

この問題自体は$P$が素数であるという制約がなくても解けるわけですが、こういう余計な制約がついていることに疑問を抱いた参加者の方々が解説を読んで二平方定理に触れる機会を提供できればという意図で出題させていただきました。

C: No.2394 部分和乗総和 ★★☆
問題リンク：https://yukicoder.me/problems/no/2394 tester：hotman78さん、hiro1729さん（C・D全体tester）
整数論ですが、アイデアの背景には組合せ論と可換環論があります。もし$M$が不定元$X$であれば、競技プログラミング典型の部分和問題です。適当な法のもとでなら冪乗の和を積に分解することで畳み込みに帰着させる高速な解法が知られており、そういった競技プログラミングにおける畳み込み事情を初めて学んだのはtesterさんの解説記事でした。今からおよそ11ヶ月前。競技プログラミングの勉強を初めて間もない頃で、今でも当時の感銘は記憶に新しいです。話が逸れましたが、この問題では多項式と整数の類似性をきちんと活かせるかを問いました。畳み込みによる部分和問題の解法を知っている人なら不定元$X$の代わりに$M$を考えるだけなので、体係数多項式環の代わりに整数環を使えばいいだけです。可換環論では体係数多項式環と整数環の類似性に注目した議論が多く、この問題も多項式の係数表示と整数の$M$進法表示の類似性に着目して思いつきました。もちろん★2.5では畳み込みが典型ではないので畳み込みを知っている人しか解けないのでは難易度過小詐称になってしまいますが、本問は★2.5の典型手法である動的計画法でも解くことができます。これは部分和問題が優しい制約なら動的計画法で解ける（そしてその遷移の高速化に畳み込みが使える）という事実と対応していますね。コンテスト本番は解法を思いついていながらもオーバーフローしたり$M$と$B$の役割を逆にしたりという提出がそこそこあったようです。何度も「あれもこれもあってそうなのに何で通ってないの！？」と不安になりテストケースに不備がないか確認していました。

C: No.2394 部分和乗総和 ★★☆

問題リンク：https://yukicoder.me/problems/no/2394

tester：hotman78さん、hiro1729さん（C・D全体tester）

整数論ですが、アイデアの背景には組合せ論と可換環論があります。もし$M$が不定元$X$であれば、競技プログラミング典型の部分和問題です。適当な法のもとでなら冪乗の和を積に分解することで畳み込みに帰着させる高速な解法が知られており、そういった競技プログラミングにおける畳み込み事情を初めて学んだのはtesterさんの解説記事でした。今からおよそ11ヶ月前。競技プログラミングの勉強を初めて間もない頃で、今でも当時の感銘は記憶に新しいです。

話が逸れましたが、この問題では多項式と整数の類似性をきちんと活かせるかを問いました。畳み込みによる部分和問題の解法を知っている人なら不定元$X$の代わりに$M$を考えるだけなので、体係数多項式環の代わりに整数環を使えばいいだけです。可換環論では体係数多項式環と整数環の類似性に注目した議論が多く、この問題も多項式の係数表示と整数の$M$進法表示の類似性に着目して思いつきました。

もちろん★2.5では畳み込みが典型ではないので畳み込みを知っている人しか解けないのでは難易度過小詐称になってしまいますが、本問は★2.5の典型手法である動的計画法でも解くことができます。これは部分和問題が優しい制約なら動的計画法で解ける（そしてその遷移の高速化に畳み込みが使える）という事実と対応していますね。

コンテスト本番は解法を思いついていながらもオーバーフローしたり$M$と$B$の役割を逆にしたりという提出がそこそこあったようです。何度も「あれもこれもあってそうなのに何で通ってないの！？」と不安になりテストケースに不備がないか確認していました。

D: No.2395 区間二次変換一点取得 ★★★
問題リンク：https://yukicoder.me/problems/no/2395 tester：ecotteaさん、hiro1729さん（C・D全体tester）
線形代数と代数、特に群論とモノイド論です。線形変換が行列に翻訳できることは有名で、アフィン変換も$1$（変数の$0$乗）を巧みに使うことで行列に翻訳できることも競技プログラミングではよく話題に出る知識だと思います。同様により一般の多項式による変換も変数の冪乗を必要なだけ全部持てば行列に翻訳できる、というところまで来ると有名知識とはいえ★2.5～3ではあまり目にすることがないテクニックかもしれません。この問題は一見高次の変換を翻訳しなければいけないように見えて、★2.5～3の知識の範囲で解けるようにクエリを工夫して一次変換と軽めの処理の組み合わせで記述できるようにしてあります。クエリをデータ構造でさばくためにクエリの代数的な翻訳ができるかを問いました。この問題の難易度評価は色々悩ましかったです。作問当初は解説に記載したtester解を元々は気づいておらず、★2.5では非典型でありかつやや重実装かと思い難易度を高めに見積もって★3としていました。しかしひとたびシンプルなtester解を教わってみるとコンテスト参加者にとってはtester解の方が自然に思いつくものだろうと考え、testerさんの難易度評価に合わせて★2.5に変更しました。それでも★2.5～3の難易度評価は慎重に行いたいと思って募集していたC・Dの全体testerさんに改めてCよりだいぶ難しく★3～3.5相当ではないかと評価していただいたので、再びtesterさんとご相談し★3に戻しました。この辺は自分だけで考えても不安が募るばかりなので、testerさんと全体testerさんの２人に体感を教えていただけて本当に助かりました。本番でのAC数は１時間経過時点で問題順を差し引いてもC問題より有意に落ちていました。最終的にはAC数の差が縮まりましたが、コンテスト時間がながければ差が縮まるモオだと思いますので、結果的に★3にして正解だったようです。なお解説の余談にも書かれていますが$5$次正方行列を直接扱うとTLEしやすく、言語間の不平等がなるべくないように早い言語でもTLEしてくれればと思っていました。実際に早い言語でTLEしている提出も見かけたので、TLがちょうどいい塩梅に設定できているようで一安心です。

D: No.2395 区間二次変換一点取得 ★★★

問題リンク：https://yukicoder.me/problems/no/2395

tester：ecotteaさん、hiro1729さん（C・D全体tester）

線形代数と代数、特に群論とモノイド論です。線形変換が行列に翻訳できることは有名で、アフィン変換も$1$（変数の$0$乗）を巧みに使うことで行列に翻訳できることも競技プログラミングではよく話題に出る知識だと思います。同様により一般の多項式による変換も変数の冪乗を必要なだけ全部持てば行列に翻訳できる、というところまで来ると有名知識とはいえ★2.5～3ではあまり目にすることがないテクニックかもしれません。

この問題は一見高次の変換を翻訳しなければいけないように見えて、★2.5～3の知識の範囲で解けるようにクエリを工夫して一次変換と軽めの処理の組み合わせで記述できるようにしてあります。クエリをデータ構造でさばくためにクエリの代数的な翻訳ができるかを問いました。

この問題の難易度評価は色々悩ましかったです。作問当初は解説に記載したtester解を元々は気づいておらず、★2.5では非典型でありかつやや重実装かと思い難易度を高めに見積もって★3としていました。しかしひとたびシンプルなtester解を教わってみるとコンテスト参加者にとってはtester解の方が自然に思いつくものだろうと考え、testerさんの難易度評価に合わせて★2.5に変更しました。それでも★2.5～3の難易度評価は慎重に行いたいと思って募集していたC・Dの全体testerさんに改めてCよりだいぶ難しく★3～3.5相当ではないかと評価していただいたので、再びtesterさんとご相談し★3に戻しました。この辺は自分だけで考えても不安が募るばかりなので、testerさんと全体testerさんの２人に体感を教えていただけて本当に助かりました。

本番でのAC数は１時間経過時点で問題順を差し引いてもC問題より有意に落ちていました。最終的にはAC数の差が縮まりましたが、コンテスト時間がながければ差が縮まるモオだと思いますので、結果的に★3にして正解だったようです。なお解説の余談にも書かれていますが$5$次正方行列を直接扱うとTLEしやすく、言語間の不平等がなるべくないように早い言語でもTLEしてくれればと思っていました。実際に早い言語でTLEしている提出も見かけたので、TLがちょうどいい塩梅に設定できているようで一安心です。

E: No.2396 等差二項展開 ★★★★
問題リンク：https://yukicoder.me/problems/no/2396 tester：ecotteaさん
整数論、特に代数的整数論または可換環論です。D問題から一気に★1個分開いているためAC数に開きが出てしまうだろうなと心配はしつつも、★3以下が４問あるので★3以下が主戦場となる方々にも十分楽しんでいただけると信じて出題させていただきました。問題の方は極めてシンプル。しかし要求される知識はやや高め、といういかにも整数論でありがちな問題に仕上げました。二項係数と冪乗の組み合わせを適切に「$\mathbb{Z}$上有限生成自由加群である環（$\mathbb{Z}$係数の基底を持つ環）における冪乗の基底表示による係数」に翻訳できるかを問いました。そういった環の基底は一意でないので様々な解法が得られると思いますが、その解法ごとに別の係数を見ることで新たな組合せ論的関係式を得られるので、ぜひ作問の種にしていただけたら幸いです。 testerさんからはToeplitz行列を使った解法を教えていただきました。作用素環論でちょくちょく使っていた（主に無限次元の）Toeplitz作用素がまさか競技プログラミングでも使われるなんて全く知らなかったためとても感嘆しました。普段扱っている数学たちが思わぬ形で応用されているのを見ると嬉しくなりますね。いざコンテスト本番を迎えてみると、writer解やtester解とは違った畳み込みでの提出がいくつか目に入ってきました。後で皆さんの解法を勉強させていただきたいと思います。

E: No.2396 等差二項展開 ★★★★

問題リンク：https://yukicoder.me/problems/no/2396

tester：ecotteaさん

整数論、特に代数的整数論または可換環論です。D問題から一気に★1個分開いているためAC数に開きが出てしまうだろうなと心配はしつつも、★3以下が４問あるので★3以下が主戦場となる方々にも十分楽しんでいただけると信じて出題させていただきました。

問題の方は極めてシンプル。しかし要求される知識はやや高め、といういかにも整数論でありがちな問題に仕上げました。二項係数と冪乗の組み合わせを適切に「$\mathbb{Z}$上有限生成自由加群である環（$\mathbb{Z}$係数の基底を持つ環）における冪乗の基底表示による係数」に翻訳できるかを問いました。そういった環の基底は一意でないので様々な解法が得られると思いますが、その解法ごとに別の係数を見ることで新たな組合せ論的関係式を得られるので、ぜひ作問の種にしていただけたら幸いです。

testerさんからはToeplitz行列を使った解法を教えていただきました。作用素環論でちょくちょく使っていた（主に無限次元の）Toeplitz作用素がまさか競技プログラミングでも使われるなんて全く知らなかったためとても感嘆しました。普段扱っている数学たちが思わぬ形で応用されているのを見ると嬉しくなりますね。

いざコンテスト本番を迎えてみると、writer解やtester解とは違った畳み込みでの提出がいくつか目に入ってきました。後で皆さんの解法を勉強させていただきたいと思います。

F: No.2397 ω冪 ★★★★
問題リンク：https://yukicoder.me/problems/no/2397 tester：googol_S0さん、testestestさん
基礎論、特に集合論です。順序数を扱う問題を今後も出題していくため、また他の方々にもっと出題してもらいため、カントール標準形の知識を持っている人が増えるといいなと思いチュートリアル的な問題を作成しました。とはいえ競技プログラミング界隈で広く知られているわけではない概念を問題文で使うにはその定義を最低限書くべきであると思い、１つの壁となったのが順序数演算です。順序数演算の定義をまともに書き下してしまったら問題文がとても長くなってしまい、参加者の不満も高まってしまいかねません。そこで試行錯誤を重ねて、集合の既知の操作（和集合など）のみを最小限使って順序数演算の定義を翻訳しました。カントール標準形の知識がない人にアウトリーチする問題である以上、定義が書かれているだけでなくきちんと検索しやすいキーワードを散りばめた問題文になるよう意識しました。実際に検索で必要な情報に辿り着きやすいかなども含めてtesterさんたちにご相談し、★4レベルを主戦場とする参加者なら頑張ればカントール標準形の必要知識に到達できるだろう問題文になっただろうと期待しています。なお元々カントール標準形の知識があった人には物足りない問題となったかもしれません。そこは申し訳ないところですが、そんな人のためにカントール標準形の知識が十分活用できる問題をG問題にご用意させていただきました。ぜひお楽しみいただけていれば幸いです。

F: No.2397 ω冪 ★★★★

問題リンク：https://yukicoder.me/problems/no/2397

tester：googol_S0さん、testestestさん

基礎論、特に集合論です。順序数を扱う問題を今後も出題していくため、また他の方々にもっと出題してもらいため、カントール標準形の知識を持っている人が増えるといいなと思いチュートリアル的な問題を作成しました。

とはいえ競技プログラミング界隈で広く知られているわけではない概念を問題文で使うにはその定義を最低限書くべきであると思い、１つの壁となったのが順序数演算です。順序数演算の定義をまともに書き下してしまったら問題文がとても長くなってしまい、参加者の不満も高まってしまいかねません。そこで試行錯誤を重ねて、集合の既知の操作（和集合など）のみを最小限使って順序数演算の定義を翻訳しました。

カントール標準形の知識がない人にアウトリーチする問題である以上、定義が書かれているだけでなくきちんと検索しやすいキーワードを散りばめた問題文になるよう意識しました。実際に検索で必要な情報に辿り着きやすいかなども含めてtesterさんたちにご相談し、★4レベルを主戦場とする参加者なら頑張ればカントール標準形の必要知識に到達できるだろう問題文になっただろうと期待しています。

なお元々カントール標準形の知識があった人には物足りない問題となったかもしれません。そこは申し訳ないところですが、そんな人のためにカントール標準形の知識が十分活用できる問題をG問題にご用意させていただきました。ぜひお楽しみいただけていれば幸いです。

G: No.2398 ヒドラ崩し ★★★★★
問題リンク：https://yukicoder.me/problems/no/2398 tester：testestestさん
基礎論、特に証明論とゲーム理論です。順序数を用いたゲームの翻訳とグランディ数の計算ができるかを問いました。ゲームで順序数というとグランディ数が有名ですが、グランディ数とは別にゲームの状態をラベリングするためにも順序数が使えるという知識が問われる競プロの問題はあまりないようなので出題させていただきました。過去にも同様に順序数でゲームの状態をラベリングする問題（ネタバレを防ぐためリンクは貼りません）を出題したことがありますが、今回はラベルとグランディ数の両方を同時に扱うため順序数への２種類の写像を考えなくてはならないという、何とも頭が混乱しやすそうな問題です。グランディ数の明示公式の導出にはまず実験で推測する手段が有効ですが、本問のようにゲームの状態自体が自然数ではなく順序数でラベル付けられてしまう問題では実験コードが書きにくく、うまく実験をする方法が思いつきにくかったかもしれません。実は順序数の計算は慣れれば案外手計算がしやすいもので、実験コードを書くのではなく手計算で実験することでラベルとグランディ数の関係式を推測できるものだったりします。もちろん高難易度を解く狭義プログラマーはこちらの想定以上に実験コードを書くのが得意だとは思いますが、もし順序数絡みの計算で実験コード作成に詰まったらぜひこれを機に手計算も案外できるということを思い出していただければ幸いです。ちなみに解説は最初かなり誤植が多かったのですが、testerさんに非常に丁寧に直していただきました。こういう高難易度問題の解説こそ気を引き締めて何度も見直しをしなければなりませんね。、

G: No.2398 ヒドラ崩し ★★★★★

問題リンク：https://yukicoder.me/problems/no/2398

tester：testestestさん

基礎論、特に証明論とゲーム理論です。順序数を用いたゲームの翻訳とグランディ数の計算ができるかを問いました。ゲームで順序数というとグランディ数が有名ですが、グランディ数とは別にゲームの状態をラベリングするためにも順序数が使えるという知識が問われる競プロの問題はあまりないようなので出題させていただきました。

過去にも同様に順序数でゲームの状態をラベリングする問題（ネタバレを防ぐためリンクは貼りません）を出題したことがありますが、今回はラベルとグランディ数の両方を同時に扱うため順序数への２種類の写像を考えなくてはならないという、何とも頭が混乱しやすそうな問題です。

グランディ数の明示公式の導出にはまず実験で推測する手段が有効ですが、本問のようにゲームの状態自体が自然数ではなく順序数でラベル付けられてしまう問題では実験コードが書きにくく、うまく実験をする方法が思いつきにくかったかもしれません。

実は順序数の計算は慣れれば案外手計算がしやすいもので、実験コードを書くのではなく手計算で実験することでラベルとグランディ数の関係式を推測できるものだったりします。もちろん高難易度を解く狭義プログラマーはこちらの想定以上に実験コードを書くのが得意だとは思いますが、もし順序数絡みの計算で実験コード作成に詰まったらぜひこれを機に手計算も案外できるということを思い出していただければ幸いです。

ちなみに解説は最初かなり誤植が多かったのですが、testerさんに非常に丁寧に直していただきました。こういう高難易度問題の解説こそ気を引き締めて何度も見直しをしなければなりませんね。、

トップページ前の開催記親記事次の開催記