SuperCon 2024 参加記 - Cyanmond - 競技プログラミング

去年はチーム Takenoko (17 + ytqm3 + Cyanmond) で出たが、今年はチーム Calamari (17 + Cyanmond + shiomusubi496) で出た。この名前は、使うスパコンが SQUID という名前でこれはイカの意味があるらしいので、英語でイカ料理を表す Calamari を提案したところ他に案がなく決まった。

1 日目

この日は鉄緑会の校内模試があったようなので、後半は自分が回収した。どちらにせよ初日はスパコンまで到達しないので、深夜労働などをしてもらった。

問題概要を把握した。問題としては、

森林火災のモデルがある
初期状態が与えられる。具体的には島があって 10 箇所で火災が発生し始める
10 単位時間後に、燃えている木の半分まで木を切ることができる

という条件で、 500 単位時間後まで残る木の本数を最小化するというタスクだった。

なんとなく方針を考えた。焼きなましくらいしかないのではないか、という結論になった。

2 日目

まだ並列化にはたどり着きそうになかったので、競技時間に限らずだらだらと進めていた。

Visualiser を GPT に書いてもらった。火災の広がり方だけ見たかったので、変なツールを作るのはやめて maplotlib で 10 単位時間ごとに画像を出力させるスクリプトを書いた。他のチームを見るに、少し雑すぎたかもしれない。Visualiser を見たことで、結局それぞれの火災は消せない限り大きく広がることがわかった。そのため、まずいくつの火種を消せるか、そして全てを消せないならどれを選んで消すかの勝負になると判断した。

火が存在するマスやその周辺のマスにある木を割合に応じて雑に切るルールベースの戦略を実装したが、全然消えなかった。木を切るコストの制約がだいぶ厳しいと判断して、以下の方針に決めて実装を始めた。

各火種はほぼ独立と考えられるので、各火種についてそれを消すために必要な最小のコストを求める。
消す火種を bit 全探索などして、最終スコアが一番良い選び方を求める。

前半の、火種を消す最小コストを求める焼きなまし法を、深夜まで書いていた。

3 日目

思ったより火が消せることがわかったので、全ての火種を消すのがスタートラインと考えた。上の焼きなましの近傍を追加するなどしたところ、 8/10 ほどのケースで全ての火種を消せるようになった。

そろそろ並列化をしたかったので、午後は SQUID 上で実行を始めた。ところが全然コードが動かないハプニング発生。チューターの方のヘルプを頂いて 1 時間ほど格闘していたら、特に何もしていないのに動くようになった。原因不明。兎にも角にも色々とバグがあったので、それらを直していたら、あっという間に 17:00 になってしまう。まだ何も並列化できていなかった。

方針上細かい計算が多くなり、並列化が難しかった。焼きなましにおけるシミュレーションに並列化を試したが、 OpenMP のスレッド起動がボトルネックとなり遅くなるだけで終わってしまった。MPI で SQUID VE 1 ノードの 8 procs に 10 の問題を分配 (事実上 5 procs)、 10 コアは単に焼きなましの初期解 30 個ほどを試すのに使った。実はこの初期解をひたすら変えて実行するのが割と効いた。あまり洗練されていない焼きなまし法だったということかもしれない。手元環境に MPI を入れて動かしたところうまく動いたので、これがきちんと動くことを祈っておいた。

並列して、火種を消した後の微妙なスコアの最適化が勝負を分ける可能性を考えて、そのために別で焼きなまし法を使うことにした。初期解を上の最小コストの方法、近傍を雑に定めて動かした。終わってから聞いてみると、これが実はあまり上手に書けておらず、一部チームはもっとうまく最適化したようだった。(残念ながら、そこは本番うまくコードが動かなかったらしい。)

ちなみに、バグ取りではスパコン上で動かすと勝手が違って難しいので、手元で gcc のデバッグ用オプションを付けて動かすのがよかった。最適化で Runtime Error にならないようなバグを拾ってくれたことが 2 回ほどあった。

4 日目

ここまでのコードを全部合わせて SQUID 上で動かしたところうまく動いた。提出は 13:00 で 3 時間ほど余裕があったので、一応配布の Evaluation プログラムを動かして出力が正しい形式かどうか確認するなどしていた。結局 19/20 くらいのケースで火が全て消えるようになった。地味なパラメータ調整をして、おそらく最終提出が 12:00 くらいだったと思う。

閉会式

他の強いチームが出力形式を間違えた？こともあったのか、全問題で 5 点 (順位に応じて各問題のスコアが 1, 2, 3, 4, 5 位に 5, 4, 3, 2, 1 とつく) を取ることができて 1 位で文部科学大臣賞をもらえた。レポートをちゃんと書いたからか、学会からの賞などももらえた。去年は 2 位相当のスコアを出していながら非本質部分でバグを埋め込んで 0 点だったので、リベンジができてかなりうれしかった。

その他雑多

去年は速度競技だったのに対して今年はスコア競技だった。スコア競技のほうが単純にやるべきことが増え、去年より環境が扱いづらいこともあって、コンテスト期間の時間管理がシビアだったと思う。個人的には速度競技の方がスパコンで感動できて楽しかったが、スコア競技で色々アイデアを試すのもなかなか面白かった。

まだ賞品類諸々が学校にあるようなので、日本に帰ったときに回収したい。

自分はもう出られないのですがとても面白いコンテストなので、いま中学生の人は今後ぜひ挑戦してみてほしいです！