ICPC2023横浜大会準備記

ICPC2023横浜大会の準備に関わったので記録を書きます

G問題

n 枚のカードが並んでいる。 6面ダイスを振り、出た目を x として、左から x+6k 枚目にあるカード (k=0,1,2,...) をすべて除去するような操作を繰り返す。最後の1枚になるまで繰り返す。各カードが生き残る確率は？

継子立てのように、なんらかの機械的な篩分けのプロセスを経て最後の1つが残るような設定を考えたいと思って作問を始めました。継子立て自体は古典的な題材なので何か真新しいものをなんか考えようかなぁと思い、せっかくなのでサイコロ君に登場してもらうことにしました。ICPC名物要素です。

自明には状態数が O(n ^ 2) なのでなんか工夫しないといけないのかなぁと思ったのですがちょっと考えるとカードの枚数は操作回数に対して指数的に減衰していくから、必要な状態はそんなに多くなさそうということがなんとなく察せます。もうちょっと真面目に考えると普通にメモ化再帰すれば線形時間くらいになっているということが示せます。

で、この問題は結構ギャグっぽい感じがしました。よくわからないけどそれっぽくメモ化再帰するとなぜか速い、みたいな。なんか、ガチガチに計算量絞り込んで高速化するタイプとはちょっと違う感じがします。問題文に黒いタロットカードを出してちょっとムーディーな感じを出せたので満足です。問題への個人的な思い入れ度合いは… 普通くらい。

K問題

インタラクティブ問題です。地区予選の恒例になるかどうかは定かでないですが、とりあえず2年目です。

自分が原案の問題ではありません。傍から見ると手でデバッグするのは辛そう、かつこの問題でハマって多くの時間を消費するのもなんだかなと思ったのでテスト用ツールを選手に配布できると良いのではと思い、そのように進めました。準備に協力いただいた方々に感謝です。たくさん解いてもらえたのもありがたかったです。

インタラクタ (ジャッジ用のプログラム) を書いていて一つ苦労した点として誤差の扱いがあります。円と線分の共通部分の計算には平方根が必要となるわけですが、平方根は原点付近で微分が急峻になる、つまり仮に誤差が1e-14くらいの超小さい数だとしても平方根を取ると1e-7くらいのまぁまぁでかい数になって結構やばいということに気づきました。ちょうどインタラクタをストレステストしていたときの頃です。レスポンスが0であるはずのクエリに対して正の実数を返してしまうことがあり、これはちょっと真面目にやらんとまずいと気づきました。というか、それまで平方根が及ぼす影響を甘く見すぎていました。幸いなことに今回の制約ではレスポンスが0であるかの判定は浮動小数点数無しで行えることがわかったのでそれを実装しました。

競プロまわりをめぐる情勢など

ついでなので。世界的に権威ある大会であった Topcoder Open や Google Code Jam が今年で終幕し、さらに今年10月に予定されていた ICPC 世界大会が中東情勢のあれこれで延期するなど、結構波乱に満ちた年になった感じがします。特に Topcoder にはもう記憶がはるか彼方ではあるものの自分が20代の頃かなりの時間を費やした場なのでこれが消滅していくのは寂しい気持ちがあります。

”寂しい”というと小さな感情に過ぎない感じがしますが、なんというか個人的にはそれ以上のものがあるような気がしています。結局世の中にあるものは日々変遷として、古きものは消え去り、人々の記憶からもなくなる運命にきっとあるのでしょう。領土が異民族に侵略されればその土地の歴史などはすべて都合の良いように塗り替えられ、プラットフォームが消滅すればその上で培われたいかなる秀作や努力の結晶、良い思い出も跡形もなく消え去っていく、というように。あるいは、なにがしかのデータがどこかのサーバーで残っていたしても、人々が新しいものだけに価値を感じ、古きものにはアクセスする方法も知らされないのなら、それは誰からも見られすらしないスクラップ同然であるというように。

しかし、優れたものはたとえ時を超えても継がれていく価値があるのではないだろうか？何百年前の文学作品であっても人間の普遍的な性質を描写したものであれば現代であってもそれは心を打つだろう。絵画にしても然り。数学も時代によって動機や関心が違うところがあるかもしれないけど、数理的に興味深いと思わせるような概念や問題には多分なにかしらの普遍性がありそう。まぁ分かりませんが。プログラミングコンテストの問題は分かりませんが、しかし根本的には与えられた問題の構造をいかに数理的に解明し、それをどう機械的な手続きに落とし込むかというところにあって、コンピュータという複雑な装置は経るもののやってることはだいぶ根源的なのでは？

…とここまで書いて何が言いたいんだかわからなくなってきましたが。コンテストの問題でも古くても面白いものは面白いはずだし、それが時間とともにプラットフォームが終了したり大会が閉幕したりして見向きもされなくなるのは、いかに自分にとって前世のことだと言ってもやるせないなぁと思うのです。そこには過去のいろんな人の情熱や感性が注がれているのです。その正体は注意深く見ないと、ただの無機質で形式的な言葉が並べられているだけにしか見えないわけですが。

とはいってもプログラミングコンテストに関して大会が存続していない限りはまぁ見向きもされなくなるのはやむを得ないでしょう。例えば75分3問形式のコンテストがもう廃れて同然なのにその過去問をわざわざ謎のプラットフォームを起動して解くというのはまぁ結構奇特かよほど熱心でない限りやらない気がします。(こんなこというとファンの方には不快かもしれませんが、すいません) 話にオチはありません。とりあえず今日はこれくらいで。そういえば AOJ-ICPC は旧 twitter にどっぷり依存したウェブサイトだったのですが、APIが使用不可になった影響で更新作業もできなくなりました。これも課題です。