SuperCon2021 参加記
この記事は N・S高等学校 Advent Calendar 2021 10日目の記事です。
SuperConとは
スーパーコンピューターを使った並列プログラミングで、出題された課題に対してどれだけ良い点数を出せるかを競うタイプの（いわゆるマラソンマッチ）高校生向けプログラミングコンテストです。
チームについて
構成としては私（AtCoder水）と相方（AtCoder緑）の二人チームで、相方はマラソン系コンテストの経験が無かった（というかほぼ無理やり誘った）のでメインの考察・実装は私が担当し、相方には基本的にシミュレーション部分の実装やパラメーター調整等をお願いしていました。
予選
正直あんま覚えてないので雑
とりあえずなんやかんやしてグラフに帰着し、そこからビームサーチ… といきたい所だったが解き始めたのが遅かったこともあって実装が間に合わず断念 最終的にはランダム性のある貪欲を繰り返して一番点数の良かったものを出力する、といったものを提出した。
通るかはだいぶ不安だったけど無事に通過できて一安心。
提出コード
本戦
一言で言えば感染症の流行の仕方からネットワークの繋がりを推定する、という問題です（実にタイムリー…）
こう言われると難しそうに聞こえるかもしれませんが、基本的には単純に焼きなましをすれば良さそうです。重要なのはスパコンを使って並列化する上でどんな工夫をしていくかという点なのでしょう。
ちなみに並列化の種類（API）はOpenMPとMPIの二種類あって、それぞれマルチスレッド、マルチプロセスに対応しています。このうちどちらを選択するか、あるいは組み合わせるのかは自由に選べるとのことでした
提出コード
やったこと
1日目
とりあえず問題を読んで考察したり、富岳へのログインを試したりしつつ、ランダムな初期値でシミュレートするコードを生やして終了。
2日目
頑張って焼きなましを実装する。ここで工夫した点として、焼きなましの遷移は種類を増やすと良い、みたいな記事があったのを思い出したので遷移を2種類持たせ、ランダムに選ばせるようにした。
その後OpenMPによる高速化を試すもなかなか上手くいかず、結局全部MPIによるマルチプロセスでやるのが良いんじゃね？と思ったりした（これは結果的に正解だったっぽい）
3日目
MPIによる並列化を完成させつつパラメーターの調整をしていたところでスコア改善の決め手となるアイデアが思い浮かんだ。
このときのプログラムの内容では、複数のプロセスでそれぞれ個別に焼きなまし法による探索を行っていたわけなのだが、これだと下位のスコアで停滞してしまうプロセスがいくつか生まれてしまっていた。
そこで上位のスコアを持つプロセスから下位のプロセスへ良い感じに逐次状態をコピーすることで、全プロセスを活用して効率的な探索ができるのではないか、というお気持ちである。
そこまで考えたところでこの日は時間切れ、最終日に託すことになる。
4日目（提出最終日）
3日目に浮かんだアルゴリズムを急いで実装する。スコアが思った以上に劇的に改善し、これワンチャンあるのでは…？と思い始める
4日間ロクに寝てないため睡眠不足もあって死にそうになりながらもなんとか時間ギリギリに提出を間に合わせた。
結果
というわけで、全体2位という結果でした。
強い人達のいる中で実力を出し切って入賞できたというのは勿論嬉しかったし、1位のチームがあまりに強すぎた*1ので優勝できなくて悔しいという思いもそこまで浮かばず、晴れ晴れとした気持ちで大会を終えることができました。
おわりに
このような大きな大会で良い成績を残せたのは初めてだったので、本当に嬉しかったし良い経験でした。付き合ってくれたチームメイトには感謝しかありません。ありがとうございました
