はじめに
こんにちは、高校2年生のBlueberryです。
SuperCon2024の本戦が終わってからかなりの時間が経つのですが、参加記は書いておきたいので書きます。予選から本戦までの出来事を大まかに振り返ります。
まずタイトルにもある通り、チームtcAtCaは本戦2位という結果でした。ここまで高い順位を取るのは人生で初めてで、とても嬉しかったです。チームメンバーのyaakiyu、raspberryにも感謝です。
さて、予選から時系列順に振り返っていきましょう。
予選
問題
予選問題は去年と違い高速化の課題でした。問題は以下のリンクから閲覧することができます。
まあ要約すると、
格子状に並んだ頂点と、頂点間を結ぶ辺からなるグラフが与えられる。それぞれの辺には重みが設定されている。
頂点(u,v)の最短距離は何か？という形式のクエリにたくさん答えよ。
という感じです。頂点は正方形状に並んでおり、頂点数は40000（200×200）、クエリ数は3000です。
一応制限時間はあり、10テストケース合計で300秒となっていますが、この時間におさめるのは難しくないため高速化がメイン目標となります。
考察
さて、素朴な解法としてはクエリが与えられるたびにダイクストラ法を行うというものがあります。ただこれだけで終わるような予選ではないと思ったので、ダイクストラの実装は他のメンバーに任せ、僕は他の解法を探していました。
与えられるグリッドが正方形であり、きれいな形をしていることから分割統治による解法を考えました。200×200の正方形の全頂点対最短距離を求めるのは不可能なので、分割して小さくした正方形に対してワーシャルフロイド法で全頂点対最短距離を前計算しておき、クエリに対して適切に組み合わせることで回答するというものです。
かなり実装に手間がかかったのですが、結論としてはこの解法は採用されませんでした。当初はダイクストラと競り合っていたものの、raspberryの実装したダイクストラには無駄が多かったため、そこを改善することで分割統治解とははっきりとした差が出るようになってしまいました。
分割統治解の方も高速化を頑張ったのですが、単純なダイクストラにも負けるということで将来性もあまり見込めず、捨てることになりました。
革命（？）
ダイクストラ法の高速化方法を探しているうちにDial's Algorithmをraspberryが見つけて来てくれました。確かに今回の問題では辺の重みが1以上100以下ということで、まさにこのアルゴリズムが適用できる状況でした。
Dial'sAlgorithmについては詳細は略します。以下の記事などを参考にしてください。
C++によるわかりやすい実装例は見つからなかったもの、アルゴリズムの仕組み自体は01BFSやダイクストラ法を理解していれば単純で、キューを使いまわす方法も発想しやすかったので、ダイクストラを書き換えるかたちで僕が実装しました。
これにより大幅な高速化に成功し、ひとまず予選通過を確信しました。少し調整をしたり、説明文を書いたりして提出しました。
環境について
予選ではVSCodeのLive Shareを使って共同編集しながら進めていきました。ホストが立てなければならないという制限はあったものの、概ね問題なく快適に開発ができました。
そして、yaakiyuにコードをテストする環境を作ってもらいました。まず愚直な解と比較することでそもそも出力結果が正しいかを判定し、実行速度も測定するものです。これの存在は大きく、分割統治解を捨てる判断やダイクストラ法の欠陥の発見、Dial's Algorithmのもたらした影響の大きさの認識や定数倍改善の成果などをしやすくしてくれました。
Discord
流れだけ書くと分割統治解をすぐに捨てたように見えますが、分割統治解は実装がかなり難しく、少なくとも僕は実装に手間取り、夜に睡眠時間を削って実装してもバグがとれず苦労しました。
実装に苦戦してはいましたがギスギスなどはなく、深夜までDiscordでVCを繋いだり普通にチャットしたりしつつにぎやかに楽しくやっていました。
また、Discordは実行結果の共有や考察の議論、Liveshareの開始を要求する時などにも活用しました。本戦でもDiscordが大活躍します。もはや身近すぎてツールとして認識する機会は少ないDiscordですが、ツールとして見たときにも貢献度は非常に大きいものだと思います。
予選まとめ
ということで無事に予選を通過し本戦出場できました。筑附からは5チームが予選に参加していたのですが、うち3チームがコードを完成させて提出することができ、2チームが本戦に進出しました。（同じ学校からは2チームまでという制限がありました）
もう片方の本戦出場チームでは予選の早い段階からDial’s Algorithmを見つけていたらしく、こちら側のチームが最後までDial’s Algorithmを見つけられずにいたらどうなっていたんだろうとひやひやしました。（まあダイクストラの高速化でギリギリ予選突破できる気がしなくもないですが...）
余談
去年参加したときには、予選の提出期限と前期中間考査の最終日が被るという最悪の被り方をしており、完全に考査を捨てる立ち回りをしなければならず大変でした。今年は考査終了から予選提出期限まで1週間程度空いていたのでかなり余裕をもって取り組むことができました。
本戦
さて、本戦の話に移ります。本戦は5日間ありました。月曜日スタートだったので金曜日が閉会式でした。また、木曜日の午後に提出が締め切られました。
1日のうちでスパコンに接続できる時間は決まっていたのですが、ローカルでもやれることはかなり多かったので、ほとんど毎日深夜まで作業していました。
ちなみに予選と同様本戦の問題も公開されているので見ると記事が読みやすいかもしれません。
まあ要約すると
島のマップが与えられる。各マスには「燃えていない木の割合」「燃えている木の割合」「燃え終わった木の割合」が定められている。ターンが経過すると、周りのマスの状態によって燃えていない木が燃え始めたり、燃えている木が燃え終わったりする。
適切に木を切ることで、一定ターン後の燃えていない木の割合の総和を最大化せよ。
という感じかな。
1日目（8/19）
（起床時刻：6:48）
朝
yaakiyuが所用で参加することができなかったため、この日は僕とraspberryだけで参加していました。せっかくなので僕の家に集まりました。（これ以降最終日を除く4日間、全て僕の家から参加しています）
9時から開会式がありました。その後問題概要とスパコンへの接続方法などが説明されました。
昼
1日目はまず問題を理解すること、そしてスパコンへの接続方法などを理解することに時間を使いました。序盤ではスパコンを使った実行が必要になる場面が少ないため、早めにローカルにサンプルケースをダウンロードし、できるだけ本番に近い実行環境をローカルに作れるとつよいです。スパコンへの接続ができなくなる17時以降も作業を続けることができるためです。
yaakiyuがいなかったのでかなり接続に手間取ったり、ディレクトリの移動すらおぼつかなかったりしましたが、なんとか17時までにサンプルケースをダウンロードすることができました。また、それをしながら問題の考察も緩く行っていました。
問題内容が何度か変更されたものの、本格的な考察を始めていなかったため大きな影響はありませんでした。ただ問題内の式が変更されたので、最新の問題PDFをダウンロードしておくことはしました。
夜
この日はyaakiyuが合流できる夜の時間帯からが本番でした。yaakiyuに開会式の内容を共有し、問題概要を把握してもらいました。ということで初日の夜は各自に睡眠のタスクを振り、睡眠時間を多く確保して翌日に備える...はずでした。
ボイチャを終了して（おそらく）他の2人が寝た後、僕は別の人とボイチャをしていました（SuperConとは無関係）。それの影響もあってかなり遅い時間になっていました。このまま何もせずに寝るのもなあと思い、ひとまず貪欲解を書こう！と思い立って貪欲解を実装しました。
サンプルコードは与えられていましたが、木の切り方はランダムで決められていたため、燃え残っている木の割合などをもとに木の切り方を決めるように変更しました。また、上限まで木が切られていない場合はかなり無駄であることがわかったので、できるだけ切るように調整しました。
また、サンプルコードを読み、コメントをつけたのもこの日だったと思います。
なんやかんや試していたらサンプルコードと比べて約4倍のスコアが出せるようになりました。しかしふと時間を見てみるとなんと3時を回りそうでした。成果は出たため、切り上げて寝ることにしました。
この時点でのmain.cppはこちら
（就寝時刻：3:00）
2日目（8/20）
（起床時刻：7:38）
朝
2日目の朝はraspberryの電話で起きました。8:00に最寄り駅で集合する予定でしたが、朝ご飯すら食べていなかったため、一旦支度を済ませて家を出てraspberryとyaakiyuを迎えに行きました。
raspberryが集合場所から動いてしまいすれ違いが発生するなどありましたが、それ以外特に大きな問題もなく合流できました。
昼
さて、この日はyaakiyuが初めてスパコンに接続する日でした。最初は普通にコマンドプロンプトを使って接続していたのですが、なんとyaakiyuがVSCodeからスパコンに接続できるようにしてくれました！！！
これにより、以降の開発が非常にスムーズに進むようになりました。少なくともファイルの移動などで苦労することはありませんでした。コードの共有用にはVSCodeのLiveshareも予選に引き続き使用していたため、併用していくことになりました。
その後はスパコン上でのプログラムの実行を試していました。並列化のためのライブラリがincludeされているとうまく動かず、一旦そういったライブラリのないコードを実行してみました。
ジョブの投げ方やその途中経過、結果の見方などをこのタイミングで理解したと思います。
夜
この日もスパコンに接続できる9時〜17時では作業の進捗はあまりなかったです。本格的な実装を始めるのは1日目と同じく深夜となります。
上の画像を見てもわかる通り、やることが一気に増えています。流石にそろそろ危機感を持ってSuperConと向き合うようになりました。
まず、今まではシンプルな貪欲法で初期解だけを決めてシミュレーションしてスコアを計算していましたが、その初期解を少し変化させてスコアが上がったら採用する、シンプルな山登り法を実装しました。切る量を増減させる近傍を使用したところ、例えば減らす方のもともとの切る量が小さくほとんど盤面が変化しないなどの問題は起きましたが、ひとまずスコアを少し改善することに成功しました。
しかし、コードを改善して実行する際、本番と同じ制約のケースを使って実行していたため、実行に約10分程度かかり、その間できることが少なく非効率的でした。そこで、小さめのテストケースを作成し、それに伴って本番と違う制約にも対応できるようにコードを書き換えていきました。
この作業はかなり時間がかかりましたし、（深夜にやっていたからというのも大きいですが）何度もバグらせてしまいました。山登り法を実装した後は、この夜はほとんどこの作業に時間を使っていたと思います。テストケースの作成方法は問題文内で与えられていたため、それを参考にしながら実装しました。
また、シミュレーションの計算コストが重く、盤面のスコアを計算するために非常に長い時間がかかってしまっていたため、このシミュレーションを高速化または省略することも考えていました。いわゆるnextDPの考え方を用い、配列を使い回すことで約2倍の高速化に成功しました。
1日目でも少し触れましたが、サンプルコード内でaslというライブラリが用いられていたのですが、このライブラリは並列化を前提としたものでした。ローカルにも導入しようとしたのですが、環境が合わず、うまく行きそうに有りませんでした。サンプルコード内ではaslが多用されていたので、どうにかする必要がありました。
そこで、関数名などはaslのもの、中身はmash.hとなっている、asl.hのダミーを作り対応しました。
最初はifdefを使って対応しようとしましたが、yaakiyuと思想が衝突してしまったため、yaakiyuにダミーのasl.hを作ってもらいました。
以下は僕が作ったもの
yaakiyuによるもの
まとめ
この夜にやったのはコードをローカルで開発するための準備が主でした。これにより、快適にローカルで開発できるようになったと思います。
なお、この間yaakiyuは僕の手伝いもしつつコンパイル・実行・提出用ツールを作っており、raspberryは早めに睡眠をとっていました。
僕はその後シャワーを浴び、仮眠を取りました。
この時点のmain.cppはこちら
（就寝時刻：5:12）
3日目（8/21）
（起床時刻：7:55）
朝
2日目〜3日目はベッドではなくソファで寝ていました。本来家を7:30ぐらいに出てraspberryとyaakiyuを迎えにいかなければならなかったのですが、7:55に起床したので家まで来てもらいました。
昼
この時間は何をしていたのかは記録が残っておらずわからないですが、初期解の改善などをしていたと思います。
その後、山登り法を並列化しようとしてMPI関連のエラーが出てしまい、解決にかなりの時間を要しました。最終的には僕が修正し、動くようになりました。（軽く書いていますが、ずっとエラーが出たり思うように動かなかったりしたあとだったので、きちんと動いたときにはだいぶ3人とも感動していました）
夜
主に焼きなまし法の実装をしました。並行して、何故かこの日に配布されたビジュアライザを動かそうとしていました。
焼きなまし法はきちんと実装したことがなかったので、診断人さんの以下の記事を参考にしながら実装しました。温度の管理方法が非常にわかりやすかったです。
ここからはパラメータ調整を主にしていたと思います。
（就寝時刻：2:54）
4日目（8/22）
（起床時刻：7:08）
朝
この日もなんだかんだソファで寝ていたような気もします。最初に僕がDiscordで発言しているのは7:08ですがこの後の発言が7:43なのでちゃんと覚醒できてなさそうですね...
僕とyaakiyuは早めに合流し、後からraspberryも合流しました。
昼
この日はあまり記録が残っておらず、何をしたのかは正確に思い出せないですが、最終日ということで完成に向けて最終調整をしていたと思います。おおむね出せる形には仕上がっていましたが、主に二つの点において改善の余地がありました。その二つというのは、
- 初期解の改善。初期解は延焼可能性のあるマスに対して均等に切る量を定めていたが、この決め方だと切る量を上限まで使いきれないケースがあり、その場合焼きなましの遷移がうまくいかない。
- 近傍の改善。近傍は、初期解で切ったマスから2つを選んで増減させるかたちをとっていたが、これだと遷移できる状態の種類が多くないことがある。
でした。これらをどうにかしようと頑張っていた気がします。が、実装がうまくいかず結局ほとんど改善はできませんでした。（もちろん細かいパラメータ調整はしていたので、この時間全く進捗がなかったというわけではなかったです）
提出時間の30分ぐらい前からいわゆる「限界定数倍高速化」が始まりました。定数の部分をすべて数字に置き換えたり、使わない変数を削除したり代替できるものを探したり、除算をできるだけ減らしたりしていました。（このあたりの処理は去年もやっていたことで最も慣れているyaakiyuが、僕に変更しても問題ないか確認しつつやっていました）
ところが、提出時間の直前で提出時間が30分延長されました。スパコンが混雑して実行待ち時間がかなり長くなっていたのが理由だったと思います。これでかなりの余裕ができたため、いろいろな確認をゆっくりできました。提出時間の直前まで粘って最後にミスったら嫌なので早めに提出しました。
提出時間を過ぎると、何やらほかのチームが何チームかトラブルを解決できなかったらしいということがDiscordでわかりました。自分たちも何か失敗していないかびくびくしましたが、ひとまず挙げられていたものに該当するミスはなく、安心しました。
その後は解説ドキュメントを書きました。僕は3人の中では文章を書くのが得意な方だったため、僕が大体全部書いてほか2人に確認してもらいました。
提出したドキュメントはこんな感じ（実名は一応隠してあります）
解法の概要なんかも書いてあるのでその辺が気になる方もこちらを参照してください。
提出したコードはこちら
また、同じ学校のもう片方のチームともすこし話しました。
終了後
終わった後、3人で最寄り駅まで行き、ファミチキを食べ、
カラオケに行きました。
その日はこれで解散しました。カラオケもそこまで長時間は滞在しなかったと思います（たぶん1時間）
適当な画像
まあ最終日なのでDiscordで騒ぐ元気もなかったようで、あまり話せるエピソードがありません。4日間睡眠をほとんど取れていなかったのでとにかく疲れていたのを覚えています。就寝時刻はここの画像にも写っている通り20:45でした。
5日目（8/23）
閉会式の日です。この日は普通に部活もあったので、学校から参加しました。
閉会式の具体的な内容はあんまり覚えていません。チームごとに発言する場面であまりうまくしゃべれなかったことを覚えています。
順位の発表の前に、各ケースにおいてどのチームが上位を取ったかが公開されました。（これで大体の順位を知ることができます）
この時点でCalamariが1位であることが確定し、また自分のチームの名前もかなりの頻度で見えていることから少なくとも3位以内にはいるだろうということが予測でき、かなり部員たちで盛り上がっていました。
そして2位であることが確定し、みんなでとても喜びました。同じ部屋にいた別の団体の人も僕たちに注目し始めていたので「2位だったんですよ！！！全国！！」と報告して祝ってもらいました。
閉会式終了後も少し交流の時間がありました。そこで解法を少ししゃべったりしましたが、正直こんなにシンプルな手法でよく勝てたなあと思いました。一位の解法はすごく賢くて、すごいなと思いました（語彙力）
おわりに
ということで、SuperCon参加記は以上になります。ここまでの長い文章を読んでくださりありがとうございました！
