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