【競プロ】超大規模マラソン問題に取り組む際の3つのポイント〜日立北大ラボ×北大コンテスト2021〜

B問題で3位入賞しました!!

日立北大ラボ×北大コンテスト2021は、その規模と複雑さで間違いなく競プロの歴史に名を残したものと思います。

2か月半にわたる長丁場であったとともに、特に、B問題の規模と複雑さは群を抜いており、最終的に自明でない（サンプルを超える）正の得点を記録した選手が10名少々しかいない、というものでした。筆者のプログラムでソースコードサイズは83KBになりました。

自慢できるアルゴリズムは入れていませんので、アルゴリズム解説は他の記事に譲り、本記事では、このような大規模マラソン問題への取り組み手法について解説を試み、3つのポイントでまとめてみました。最初から綺麗に進んだわけではなく、振り返った今だからこそ言える話も、次回の参加時（するのか・・？）への自分への備忘録も兼ねて含んでいます。

1. 見える化

1.1. コードを書く前に見える化する（Visualize to Actualize）

今回の問題の場合は、公式からのアナウンスはありませんでしたが、北海道の実際の都市周辺が題材となり、スマートグリッドやEVを配備操作するものでした。

そのため、見える化することで、単純な入出力仕様では読み取りにくいデータの概況を、直感的に理解することが可能です。例えば、人口はかなり偏って集中しているとか、人口集中地点は、頂点も密で、土地は高価で狭いとか、が理解できます。

これにより、実際に実装して試行錯誤することで時間と労力を費やすのではなく、予め効果が高そうな実装方針に絞り込むことが可能になります。

最近において、今回の問題に準じる大規模マラソンとしては、ゲノコンがありましたが、そちらは主催者側からプロ向けのゲノム見える化ツールが提供されていました。このことを考えても、見える化はとても重要であると言えるでしょう。

たいしたものでありませんが、人口・面積・地代を表示するビューワーをgistに置きました。サンプルDの旭川とかこんな感じで、石狩川とか自衛隊駐屯地とかが丸わかりです。https://t.co/zzE4t6m1lH

#2HC2021 pic.twitter.com/pqc6BJAOPV

— toast-uz (@ToastUz) December 11, 2021

B問題のサンプルデータをもとにスコアを試算。
・輸送、電力、環境は、輸送一本足戦略で最高効率達成時（乱数影響あり）
・災害、作業は、理論最大値
これにより、輸送一本足でスコア上昇がサチったら、次に狙うべきは作業であることがわかります。
#2HC2021 pic.twitter.com/pW0CujYGE7

— toast-uz (@ToastUz) January 9, 2022

コードを書くのとデータ分析するのとのバランスが要求されるのが、日立北大の面白いところです。
図はマップDの旭川。赤ぼんやりと人口分布を示しています。青星は私のアルゴリズムで導いたEV初期配置候補点、水色が作業所の分布です。こういう図を見るだけで実装アイデアが湧きます。
#2HC2021 pic.twitter.com/zAZpCNWnqv

— toast-uz (@ToastUz) January 13, 2022

1.2. ログをもとに見える化する

事前の見える化で実装方針を立てることは重要ですが、実行時の適切なログ出力により、何が起こっているのか、想定通りかどうか、を見える化することも重要です。

筆者は、ログレベルを変えることで、概略のログから詳細のログまでを段階的に出すような仕組みを入れ、個々の実装の効果を確認するようにしていました。

//------ グローバル定数でログレベルを指定
const DEBUG: usize = 0;  // level=0 デバッグしない, =1 山登り, =2 日次詳細, =3 各時刻 =4 さらに詳細
//------ 各所でログレベルに応じたログを出力（以下例）
        if DEBUG > 0 { eprintln!("{} {} {} {}", s_trans, s_ele, s_env, s_work); }

また、A問題のジャッジプログラムは、それ自身が大量のエラー出力をするため、こちらで用意したログが流れてしまい、見えにくいです。そのため、ジャッジプログラムを一部改造して、エラー出力を抑止しました。

なお、今回は、公式のジャッジプログラムのログを全面改造し、ログを取り込んでインタラクティブな見える化をするツール開発をして一般公開するような、強者も出現していました。

1.3. 複数の言語を使いこなす

マラソンコンテストの多くは、時間内に完全な最適解を求めることは困難であり、どれだけ最適解に近づけることができるかが勝負です。そのため、一定時間内の計算量を高められる、高速なプログラミング言語を使う必要があります。

一方、見える化には、柔軟な試行錯誤が可能な言語が求められます。また単にグラフを描画するだけではなく、さまざまなデータ処理をする必要があります。見える化はローカル環境で行うため、AtCoder提出のようなライブラリ制限はありませんので、多種多様なデータ処理・見える化のライブラリが揃った言語が有利です。

筆者は、コンテストそのものにはRustを使用しつつ、見える化にはPythonを使用しました。Pythonのライブラリとしては、Numpy、Pandas、Matplotlibを使っています。今回は使いませんでしたが、問題によっては機械学習を使って、隠れた傾向を見つけ出すこともできるでしょう。（本項とは少し話題が異なりますが、Optunaを使って提出プログラムのパラメータを最適化する戦略も有力です。例はこちら）

このような形で、大規模マラソン問題に対しては、複数言語を使いこなし、データ処理もできるようなことが要求されています。

2. 適切なクラス設計（Composition over inheritance）

複雑な問題、長大なプログラムであっても、見通しを良くしてバグを最小化するには、適切なクラス設計が必要です。Rust言語は継承が基本できないようになっており、クラスは所有関係で結ばれます。むしろこの制約に素直に従うことで、シンプルなクラス設計が可能になります。

以下はB問題のクラス設計図です。最終的にはここまでの設計実装には到達できておりませんが、今振り返って、このような設計をしておけばよかった、と思われる姿です。

特に、多数のオブジェクト間の複雑な調整が必要な電力需給詳細は、独立したオブジェクトに調整役をまかせる、メディエータパターンを使っておけばよかったです。これをやってなかったので、さまざまな組み合わせを試す実装ができませんでした。

3. 最も重要なのはモチベーション維持

超大規模マラソン問題への取り組みの最重要ポイントは、モチベーション維持である、と言えるでしょう。途中で「折れる」ことが最大のリスクです。

これまでの話と矛盾するようですが、実装も少しずつ進め、動く部分を作ることは、モチベーション維持にも必要です。

一方で、最初からクラス設計が「決まる」ことはありえませんので、実装が複雑になると、初期のクラス設計の「限界」により、だんだんと実装が大変になってきます。いわゆる「技術的負債」です。「技術的負債」は開発生産性だけでなくモチベーションを蝕みます。個人の競プロ開発である利点を活かして、早期に解消を図るべきです。実際、筆者は1〜2週に1回は、大きなリファクタリングをしていました。

その際、テストを適度に書いておくと、重要な部分の動きが正しいことの確証をとりやすく、結果としてリファクタリングがスムーズに行えます。一方、納品物ではないためテストをかっちり書く必要は無く、むしろテストを書きすぎることで競プロとしての開発生産性とモチベーションが損なわれることも事実です。そのため、うまい具合の箇所・ボリュームでテストを書く、ということが重要になります。このあたりの感覚は、筆者も発展途上です。

また、今回の競技は、競プロとしては珍しく、実質「なんでも情報共有可」というものでした。そのため、筆者含めて一部の人は、twitterで情報発信〜共有をしており、これがモチベーション維持に大きく貢献したと思っています。

終わりに

最後になりましたが、このような超大規模問題を企画運営した関係者の皆様に、厚く御礼を申し上げます。