はじめに
こんにちは。データ本部 AI 技術開発部で nagiss というハンドルネームで活動している者です。 先日行われた HACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016) において 1 位を獲得することができましたので、その解法を紹介します。

HACK TO THE FUTURE とは
HACK TO THE FUTURE は、 フューチャー株式会社 が AtCoder 上で 2018 年から毎年開催しているプログラミングコンテストです。
コンテストでは、問題がただひとつ出されます。 参加者は、この問題に対しどれだけ高いスコアを獲得できるプログラムを書けるかを競います。 (いわゆる"マラソン (ヒューリスティック) 形式"のコンテストです。)
一昨年まで予選の制限時間は 8 時間でしたが、昨年からは 1 週間程度の長さとなり、より凝った解を提出できるようになっています。
問題概要
今回の問題の概要は以下のようなものです。より詳細な内容は 問題ページ を参照してください。
- 整数
とエラー率 が与えられるので、プログラムはまず、整数 と、頂点数が であるような 個の無向グラフ を出力してください。 - その後、
頂点の無向グラフが 個与えられます。このグラフは、 のいずれかに対し、頂点番号のシャッフルと、ノイズの付加 (各頂点間の辺の有無の確率 での反転) を行って生成されているので、プログラムは元のグラフがどれであったかを予測して出力してください。
昨年の予選に引き続いて、予測系の問題です。 ただ、昨年は MCMC が 猛威を振るった のに対し、今回は MCMC が得意とする問題とは毛色が違いそうです。
コンテスト中にやったこと
考察
方針
初手での考察はこのような感じでした。
- グラフの同型判定っぽい
- 簡単なケースでは厳密に答えを出せそう
- というか今回どう見ても NN (ニューラルネットワーク) での予測が強そうなタスクじゃない……?
いつもの長期ヒューリスティックコンテストでは方針を立てるのに 3 日はかかるのですが、珍しく今回は早い段階で当たり方針を引けていました。 そして機械学習が使えて他の人と差をつけられそうということで、気合も入ります。
スコアの期待値
今回の目的関数は、頂点数を
予測の成功確率を
この計算式は
具体的な
のとき のとき のとき
となり、少しの精度の違いでスコアの期待値が大きく変わるため、
そして、
相対スコア
今回はケースごとに全参加者内の最高点を
簡単な (
相対スコアの仕様のために順位表上のスコアも不安定で、あまり信頼のおけるものではありませんでした。
対策として、ローカルでの評価で、mean(ln(scores))
のような値を使いました。
解法に変更を加えた結果としてこの値が
が小さいケースの攻略
最初に、簡単なケースでほぼ最適な解を求める実装を行いました。 実装するまでは何割程度のケースでこの解法を適用できるか見当をつけられていなかったため、優先度高く試す必要がありました。
……しかし、コンテスト中に私の実装できたのは
が大きいケースの攻略
NN を使って予測をします。
入力がグラフとなるので、グラフ畳み込みを使うことを考えますが、1 つ注意しなければならないことがあります。
それは、今回の問題で扱うグラフにおいて、頂点間に辺がある状態と無い状態は、完全に対称だということです。 グラフ畳み込みは、ある頂点に対し、辺で直接繋がれた頂点だけを使って計算を行うアルゴリズムです。 したがって、例えばノイズが加わることによって辺が消失した場合、計算において本来考慮されるべき隣接頂点が全く考慮されなくなってしまいます。
今回の問題で扱うグラフは、「頂点間に辺がある状態と無い状態があり、ノイズによって有無が入れ替わる」と考えるより、「全ての頂点間に辺が張られた完全グラフであって、辺の色は白か黒のいずれかであり、ノイズによって色が入れ替わる」と考えた方が、本質的な理解がしやすいように思います。
アーキテクチャ
実装しているうちに「これ Attention っぽくね?」と思ってグラフ畳み込みを Attention に変えたりした結果、NN のアーキテクチャはこのようになりました。Transformer の Encoder を参考にしています。

Linear は通常のアフィン変換 (入力の
- 入力は、各頂点に
次元の特徴量が割り振られたグラフ - 出力は、各頂点の新しい
次元の特徴量 - 全ての頂点に対して、以下を行う
- 他の全ての頂点に対し、自身との関係性の強さを計算する
- 関係性の強さは、自身の特徴量ベクトルを行列
でアフィン変換してできたベクトルと、相手の特徴量ベクトルを行列 (間に辺が無い場合) または (間に辺がある場合) でアフィン変換してできたベクトルの内積 , , は学習されるパラメータ
- 関係性の強さは、自身の特徴量ベクトルを行列
- 関係性の強さを、後で使いやすいように調整する
- まず、全ての関係性の強さの値を
で割る- 内積を取ったときに
個の値の和を取っており、ひとつひとつの値が独立な分散 の正規分布に従うとすると、 個の和を取った後の値は分散が になるため
- 内積を取ったときに
- その後、softmax 関数
を適用する- 全ての値が正かつ総和が
になる
- 全ての値が正かつ総和が
- まず、全ての関係性の強さの値を
- 関係性の強さに応じて、他の頂点の情報を足し合わせ、自身の新しい特徴量とする
- 具体的には、相手頂点の特徴量ベクトルに対し行列
(間に辺が無い場合) または (間に辺がある場合) でアフィン変換して得たベクトルを、関係性の強さを重みにして線型結合する , は学習されるパラメータ
- 具体的には、相手頂点の特徴量ベクトルに対し行列
- 他の全ての頂点に対し、自身との関係性の強さを計算する
推論時の動作
NN は、グラフを入力に取り、グラフ全体を表す特徴量 (
- 全ての
のグラフ全体の特徴量に対して、 のグラフ全体の特徴量と内積を取ることで類似度を計算し、類似度が 位以下だったものは切り捨てて候補を 個以下に絞る - 候補となった
に対して、 の全ての頂点と、 の全ての頂点の類似度を特徴量の内積をとることで計算する の類似度行列が 個できる
- 全ての類似度行列に対してハンガリアン法を行って、最適な頂点の割当を求め、そのスコアが最も高かったものを予測結果とする
元々はハンガリアン法で全てのグラフに対してスコアを計算する算段でしたが、
学習方法
NN の学習は以下のようにして行いました。
- 推論時と同様に、グラフ全体の特徴量を使った予測と、ハンガリアン法を使った予測を行う
- 損失関数は、グラフ全体の特徴量での予測とハンガリアン法での予測それぞれで計算したクロスエントロピーの和
- グラフの候補の数
は最大で とし、推論時のような候補の絞り込みは行わない に対して、正解の との間ではハンガリアン法による計算は行わず、真の頂点の割当を使ってスコアを計算する- NN 自体の計算量は小さく、ハンガリアン法が律速となったため、GPU は使わず学習
グラフの選択
ここはコンテスト中あまり上手くできなかったところだと思っています。 NN は精度良く元のグラフを予測してくれますが、元のグラフ集合をどのように選ぶかは人の手で上手く決めなければなりません。

私は 13 がかっこいいと思います
これにより生成された
のような行列を何個も生成します。
実際には入力の
回答を AtCoder に提出する際には、グラフを生成するシード値を埋め込みました。
提出への道のり
かなり熱中して取り組んでいたので、ここまでのコードの大枠はコンテスト開始から 3 日くらいでできていました。
解法もできたし、さあ提出するぞ!と行きたいところですが、それはまだできません。 提出のためには、いくつかの面倒な作業が必要でした。
C++ の埋め込み
まず、
幸いにも、2022 年現在の AtCoder のジャッジ環境は Python のコードに C++ のコードを埋め込むことが非常にやりやすくなっています。
AtCoder のジャッジは、提出されたコードに対して、選択された言語に応じて、1 回の「コンパイルコマンド」とテストケースごとの「実行コマンド」が実行される仕組みになっています。
例えば C++ (GCC) であれば、コンパイルコマンドは g++ ./Main.cpp
(オプションは省略)、実行コマンドは ./a.out
です。
このコンパイルコマンド、Python の場合はどうなっているのでしょうか? その答えは ルール に書かれています。
これを見ると、Python のコンパイルコマンドは bash -c 'python3.8 ./Main.py ONLINE_JUDGE 2>/dev/null'
であることがわかります。
すなわち、提出言語に Python を選択した場合は、最初に標準入力無し・ONLINE_JUDGE
のコマンドライン引数ありでプログラムの実行が行われるということです。
(Python 以外に Julia も同じような仕様になっているようです。)
これのおかげで、(C++ で constexpr を使ってコンパイル時に計算を行うのと同じように、) Python では入力に依存しない計算を各ケースの実行時間外で予め済ませておくことができます。
import sys
if sys.argv[-1] == "ONLINE_JUDGE":
compile_time_process() # コンパイルコマンドでのみ実行される
この仕様は Numba の AOT コンパイルを行うことを想定して設定されたものと思われますが、今回はこれをありがたく C++ のコンパイルに使わせてもらいます。 加えて、時間のかかる前処理もこの時間で予め済ませておくようにします。
モデルの埋め込み
C++ の埋め込みもできた!さあ提出するぞ!
まだできません。次は、NN を提出できる形にする作業です。
AtCoder 環境で使用できるサードパーティのライブラリは Numba, NumPy, SciPy, scikit-learn, NetworkX のみです。(上記のルール内にリンクのある 言語アップデートテスト用のコンテストページ に記載されています。) NN の学習は PyTorch で行いましたが、AtCoder で PyTorch は使えません。
仕方がないので、NumPy でモデルの推論を書き直します。
また、NN の学習済みパラメータは、全て結合して base64 で文字列にして埋め込みます。
このあたりでモデルの学習コードにバグでリークを起こしていることに気づき、手戻りが発生してしんどくなっていたりします。 また、ハンガリアン法では速度が足りず、グラフ全体の特徴を出力するように変更したのもこのタイミングでした。
アーキテクチャの欠点
ところで、このあたりで NN のアーキテクチャに想定していなかった欠点があることに気づきました。
この NN は、実は
この
ここまでかなり強い解法を作れている自信がありましたが、急に不安になります。 良い対応策も思いつかないので、悪影響が軽微であることを願いながら実装を進めていきます。
の調整
モデルの埋め込みもできた!バグも直した!速度も改善した!さあ提出だ!
まだです。
今回の問題では最初にグラフの数
これは NN を使った解法と相性の悪いものでした。
NN の精度を高めるには、推論時に実際に NN の入力として与えられるような
しかし、
仕方がないので、最初は色々な条件で学習を行い、それを使ってスコアが最大となるような
そして提出へ
いいよ。
OK が出たので提出します。 コンテスト時間は残り 48 時間を切っていました。
コンテスト終了まで
初提出の結果は Runtime Error
でした。
コンパイル用の時間で作ったファイルが大きすぎたようです。
直してやって再提出をすると、6 位に入ることができました。
ローカルでの seed 0 から 99 まで 100 ケースの mean(ln(scores))
の値は 16.64 でした。
残り 46 時間、ここから解の改善をしていきます。
の候補の追加
今回のスコアの計算式では、
これまで、
これでローカル評価は 16.73 になりました。 3 回目の提出をしますが、順位表でのスコアはあまり変わりませんでした。 そこまで頻度の高くなく、運要素が大きい上にトップが得点を総取りするケースの改善なので、まあそういうこともあるかと思い直します。 コンテストは残り 41 時間です。つまり、今は夜中の 2 時なので寝ます。
起きました。
さらに、
ローカル評価は 16.84 まで上がリました。 今は土曜日の午後 5 時、残り 26 時間です。
ここで、すでにある程度良いグラフの選択はできていると信じて、NN の学習時に使うグラフも固定してしまいます。 ローカル評価 16.89 になります。 提出を行うと、順位は 3 位と 2 位を行ったり来たりする位置まで上がりました。もうちょっと……!
しかし困ったことに、有効そうな改善策のスタックは既に空になっていました。 コンテストは残りはもう 20 時間しかありません。 一体何をすれば……。
最終日
やることが思いつかないので、予測がどれくらい上手くいっているのかを分析してみます。 試しに難しめのケースで混同行列をプロットしてみると、割と均等に間違っています。ん??
これはおかしいです。私の今の解法は、グラフを
ここで、
これを
また、NN の各 embedding をプロットしてみるとあまり綺麗では無かった (
さらに、グラフの並び替えによる最適化を使って、
提出はもう少し引き延ばします。 相手の嫌がることをするのが対戦ゲームの鉄則です。 他のトップ層には、スコアがあと 1.05 倍になれば勝てると思わせておいて、作戦を狂わせましょう。 駄目だ、まだ笑うな……と独りごちながら順位表を眺めるとなお良いです。
全体的に精度が良くなったので、
もう眠いので、手元で 2000 ケースを回してエラーが起こらないか確認し、いよいよ提出です。
残り 4 時間半、2 位に十分差を付けて 1 位に立つことができました。
コンテスト後の戦い
その後大きな順位の変動も起こらず、コンテストは終了時刻を迎えました。
良い気持ちで Twitter の感想戦 TL を眺めていると、こんなツイートが流れてきます。
【AHC016】ご参加ありがとうございました。解説配信は19:30からの開始となります。皆様の度肝を抜く解説を用意しておりますので、ぜひご期待ください!#AHC016 #HTTF
— AtCoder (@atcoder) November 20, 2022
HACK TO THE FUTURE 2023 予選 解説配信 https://t.co/NYIqyAtlvs
今回のコンテストでは、終了後にフューチャーの ツカモさん と問題作成者の wata さん による解説配信が企画されていました。
それにしても、度肝を抜く解説とは一体何なのでしょうか。 まさか 1 位よりめっちゃ高いスコアが出るとか? いやいやそんなことないでしょ、我 Kaggler ぞ? Kaggler の作った NN モデルぞ?
解説配信を見ます。
wata さん「ちなみに自分の解法はどれくらい出たかっていうと」
「これくらいでました」

!?!?!?😱🤬🤢🤢🤮🤮🤮🤮😈😣😭😭😭
おしまいです。私は予測モデルの精度で人力を超えられない Kaggler でした。 これからは職人芸の時代としてアナログトランスフォーメーションを推進していきます。
……本当にこのまま終わっていいのでしょうか?
ここまでの内容を堂々と「1 位」解説としていいのか?
配信見てて気持ちよかったところw#HTTF #AHC016 pic.twitter.com/yod6ckYP9V
— chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) November 20, 2022
1 週間頑張った結果が chokudai さんを気持ちよくさせて終わるのでいいのか?
嫌です。 せめて wata さんの解法と同じくらいの点数を出せるようになってから、1 位解法を書きたい。
ここから HTTF2023 予選は延長戦が始まっていきます。
結果
結論から言えば、解説配信で説明されていた手法をいくつか取り込み、ここまでスコアを上げられました。
該当の提出コードは こちら です。
ここからは、どのようにしてこのスコアを得られたかの解説になります。
の大きいケースの改修
冷静になると、NN を使って予測を行った部分が職人芸に引けを取るとはあまり思えません。
私の解法の中で、最も手応えの無かった部分は、最初に出力する
解説配信によれば、wata さんの解では

赤は孤立点、黒はクリーク
また、予測モデルにも以下のような改善を行いました。
- 予測精度にあまり寄与していなかったハンガリアン法関連の要素を全て取り除く
- 学習が数倍〜十数倍高速化されたのでその分多いステップ数の学習が可能に
- 予測結果の候補となるグラフが実質
個に絞られたため、 クラス分類問題として解くようにアーキテクチャ・学習方法を変更 - 埋め込めるデータの大きさにまだ余裕があったため、NN は大きいほど強いと信じて Attention を 1 層増やす
- 推論時、補グラフでも予測を行う Test-Time Augmentation を実施
これにより、最大ケース
の小さいケース
コンテスト中に私の作成した解は、解説配信で解説のあったものと基本的な部分では同じでしたが、解説配信では式変形を非常に上手く行って計算量を削減していました。
このため、私はコンテスト中
(ほぼ) 最適な解は、以下のようにして得られます。 (解説配信と別の視点での解説です。)
例として、
まず、ノイズが加わることによって第
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | .531 | .354 | .079 | .003 | .020 | .003 | .009 | .001 | .000 | .000 | .000 |
2 | .059 | .564 | .242 | .013 | .061 | .013 | .040 | .006 | .001 | .000 | .000 |
3 | .007 | .121 | .571 | .061 | .013 | .061 | .124 | .033 | .007 | .003 | .000 |
4 | .001 | .020 | .182 | .532 | .002 | .020 | .040 | .182 | .002 | .020 | .001 |
5 | .007 | .121 | .053 | .003 | .532 | .003 | .239 | .027 | .013 | .003 | .000 |
6 | .001 | .020 | .182 | .020 | .002 | .532 | .040 | .182 | .002 | .020 | .001 |
7 | .001 | .020 | .124 | .013 | .060 | .013 | .565 | .124 | .060 | .020 | .001 |
8 | .000 | .003 | .033 | .061 | .007 | .061 | .124 | .571 | .013 | .121 | .007 |
9 | .000 | .003 | .027 | .003 | .013 | .003 | .239 | .053 | .532 | .121 | .007 |
10 | .000 | .000 | .006 | .013 | .001 | .013 | .040 | .242 | .061 | .564 | .059 |
11 | .000 | .000 | .001 | .003 | .000 | .003 | .009 | .079 | .020 | .354 | .531 |
仮に、第
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | .531 | .354 | .079 | .003 | .020 | .003 | .009 | .001 | .000 | .000 | .000 |
2 | .059 | .564 | .242 | .013 | .061 | .013 | .040 | .006 | .001 | .000 | .000 |
3 | .007 | .121 | .571 | .061 | .013 | .061 | .124 | .033 | .007 | .003 | .000 |
4 | .001 | .020 | .182 | .532 | .002 | .020 | .040 | .182 | .002 | .020 | .001 |
5 | .007 | .121 | .053 | .003 | .532 | .003 | .239 | .027 | .013 | .003 | .000 |
ここで、ノイズが加わった後のグラフとして第
これは、表の
他のグラフを受け取った時も同様に考え、各列で最も精度の高い予測となる番号の行が黒くなるように色を塗り直すと、以下のようになります。
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | .531 | .354 | .079 | .003 | .020 | .003 | .009 | .001 | .000 | .000 | .000 |
2 | .059 | .564 | .242 | .013 | .061 | .013 | .040 | .006 | .001 | .000 | .000 |
3 | .007 | .121 | .571 | .061 | .013 | .061 | .124 | .033 | .007 | .003 | .000 |
4 | .001 | .020 | .182 | .532 | .002 | .020 | .040 | .182 | .002 | .020 | .001 |
5 | .007 | .121 | .053 | .003 | .532 | .003 | .239 | .027 | .013 | .003 | .000 |
実は、この黒いマスに書かれた値を全て足し合わせ、
元のグラフが第
さて、これで
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | .531 | .354 | .079 | .003 | .020 | .003 | .009 | .001 | .000 | .000 | .000 |
4 | .001 | .020 | .182 | .532 | .002 | .020 | .040 | .182 | .002 | .020 | .001 |
6 | .001 | .020 | .182 | .020 | .002 | .532 | .040 | .182 | .002 | .020 | .001 |
9 | .000 | .003 | .027 | .003 | .013 | .003 | .239 | .053 | .532 | .121 | .007 |
11 | .000 | .000 | .001 | .003 | .000 | .003 | .009 | .079 | .020 | .354 | .531 |
ところで、「グラフ
まず、頂点の順序を固定した場合 (どちらのグラフの頂点にも
これは、
これで、ラベル付きグラフ
……コンテスト中の私の考察はここまででした。
発想を変えると、ラベル無しグラフ
へのラベルの振り方を、適当な一つに固定する。- 全ての
のラベルの振り方に対し、ラベルを付けた への変化確率を辺の有無の変化の個数 を使って計算し、平均を取る。 2.
で求めた確率に、 へのラベルの振り方の種類の数 ( 、後述) を乗算する。
こちらの方が効率の良い計算ができそうです。 解説配信でこの 2. の値は、
と表現されています。
そして、このアルゴリズムはさらに効率を高めることができます。
先にも述べましたが、この方法を使って山登り法などで選ばれた

43 もかっこいいですね
グラフ
隣接行列が等しくなるものを同一と見做した、頂点ラベル付きの
現れる回数は前計算で数えれば良いですが、実は、
この個数は
また、グラフ
さて、問題作成者による解ではこれで
おわりに
今回のコンテストは、AtCoder で開催されたヒューリスティック系のコンテストの中で最も熱中した回でした。 あらゆる領域 (今回であれば機械学習、最尤推定、情報理論、群論) からヒントを得て、 あらゆる手を使ってスコアを伸ばすのがヒューリスティックコンテストの醍醐味だと思っており、 今回はそれを上手く行うことができたので満足です。 (コンテスト中に Writer 解を超えることができなかったのは悔しくありますが。)
最後に、今回コンテストを開催していただき、この記事の公開を許可していただきましたフューチャー株式会社様に深く感謝申し上げます。
フューチャーグループは「ITコンサルティング&サービス事業」と「ビジネスイノベーション事業」を展開するソーシャルデザインカンパニーです。「ITコンサルティング&サービス事業」では、AI、IoTなど最新テクノロジーをベースにデータ活用からビジネスモデルのデザイン、実装、さらにはDX人材育成など様々な業種・業界のお客様のDXを推進しています。2018年からはマラソン形式の競技プログラミングコンテストHTTF(HACK TO THE FUTURE)を主催しています。
最後まで読んでいただき、ありがとうございます!
この記事をシェアしていただける方はこちらからお願いします。