HTTF 2023 qual 54th place solution

あいさつ

はじめまして、nadareと申します。 普段は機械学習エンジニアとして、レコメンドエンジンをつくったりkaggleやatmacupのような機械学習コンペティションに参加しています。

AtCoderも三年前くらいまではアルゴに参加していたのですが、就職後はkaggleのHaliteコンペやCodingGame等の長期コンテストが中心になっていました。

今回はHTTFではじめてratedのヒューリスティックコンテストに参加して、54位になったので解法やテクニックをまとめたいと思います。

overview

グラフの頂点を次数(接続している辺の数)が多い順に並び替え、大きい順に並べた次数の配列を二乗誤差で比較した際に最も似たグラフを予測として出力しました。 グラフのNは黄金分割探索によって決定し、一定のルールでグラフをたくさん生成したのち、焼きなましで用いるグラフの組み合わせを最適化しました。

ある程度整理したコードは以下のリンクになります。本記事中で出てくる関数は以下のコードに出てくるものです。 Submission #36724658 - HACK TO THE FUTURE 2023 qual（AtCoder Heuristic Contest 016）

  • solution
    • グラフ生成
    • 最適N探索
    • スコアシミュレーション
    • グラフ組み合わせ探索
  • technique
    • numpyによる並列化
    • matplotlibによる可視化
    • ipythonによるテスト
    • joblibによるパラメータ探索

また、私と類似した解法でyunixさんがツイートで解説を行っています。 こちらを先に読むとより理解が深まると思います。

solution

グラフ生成

グラフ生成方針

今回の方針では多様で区別の付きやすい次数の組み合わせを作ることが大切でした。 特に、次数の平均よりも何個かの点の次数が大きく離れていることが重要で、

  • 次数が4の頂点が10個のグラフ vs 次数が5の頂点が10個のグラフ
  • 次数が0の頂点が10個のグラフ vs 次数が5の頂点が5つ、次数が0の頂点が5つのグラフ

では、後者の方が見分けがつけやすかったです。 (これは何パターンかグラフの生成方法を試し、得点の高かったケースと低かったケースをそれぞれ可視化しながら見つけました)

グラフ生成方法

以下の方針でパラメータを渡せば自動的に作れるような関数を作成しました。

  • N個の頂点をX個とN-X個に分割する。(0 ≦ X ≦ N/2)
  • それぞれ片方ずつのみで頂点を結びグラフを生成する。(make_side_sparse_expression関数)
  • 最後に両者の頂点を結ぶ。(make_inter_sparse_expression関数)

make_side_sparse_expression

二つに分割した頂点に対しては以下の二種類のグラフを作成しました。

  • 次数が全て同じグラフ
  • 次数が単調に変化するグラフ
次数が全て同じグラフ

次数が全て同じグラフは頂点数Xが奇数の時はX/2 + 1個、Xが偶数の時はX個作成できました。 作成方法は二種類あり、奇数の時は前者、偶数の時は後者で作成しました。

  • 頂点を円形に並べたとき距離A以内の頂点と辺を結ぶ方法(次数0~2Aのグラフができる)
  • 頂点を半分ずつにわけ、片方から片方へA個の辺を結ぶ方法(次数0~Aのグラフと、補グラフでA~2Aのグラフができる)
次数が単調に増加するグラフ

結ぶ辺が変化する傾きのαと切片のheightを与え、以下のようなコードで生成しました。

for i in range(X):
     for j in range(i + 1, min(X, i + 1 + int(round(alpha * i + height)))):
        sparse_expressions.append((left + i, left + j))

make_side_sparse_expression

片方のグラフのすべての頂点からそれぞれA本ずつ、もう片方のグラフの頂点へ辺を結びました。 これにより片方は次数がA、もう片方は次数がA x 頂点の比で増えました。

パラメータの与え方

片方のグラフの大きさやその高さ、単調増加させるときの傾きは全探索すると間に合いませんでした。 そのため、NやM、epsの大きさから増やす値の大きさを手探りで決定しました。(generate_graphs関数)

最適N探索

あるM, epsのときにNとスコアの関係は凸関数のようになると予想しました。 そこでNを決定するために黄金分割探索を実装しました。 黄金分割探索は凸関数に対し、上端と下端を狭めながら頂点を探す手法で、効率的な探索ができます。 詳しい解説は省きますが、golden_search関数で実装しました。

スコアシミュレーション

最適Nを決めるためにはスコアの高速なシミュレーションが重要でした。 シミュレーション方法は、今回の方法の場合

  • 全ての辺にたいしてエラーをシミュレーションする方法: O(N2)で正確
  • 次数に対して二項分布に従う乱数でシミュレーションする方法: O(N)でだいたい正確

の二種類のシミュレーション方法を実装しましたが、スコアとの乖離から後者を採用しました。

それぞれのグラフにノイズを加えた際の次数の期待値はGraph.calc_expectで実装し、それらに対してPredictor.simulate関数でスコアを計算しました。 二項分布に従う乱数はnumpyのnp.random.binomialを用いました。 正確なスコアを計算するには頂点の次数に対して乱数を加えた後、必ずソートした値で期待値を計算することが重要でした。

グラフ組み合わせ探索

貪欲パート

グラフの組み合わせは最初に全結合のグラフを選んだ後、貪欲にそれまで選んできたグラフとの距離が最も遠いグラフを選び続けました。 正確なスコアのシミュレーションには次数の期待値を乱数を加えてからソートをする方法で計算する必要があったのですが、この貪欲で選ぶ段階ではソートしてから期待値を計算しても大体同程度のスコアが得られました。

焼きなましパート

Nを決定した後は焼きなましでグラフの組み合わせを改善しました。 この際に毎回正確なシミュレーションをすると焼きなましの試行回数をとれないので、グラフを入れ替えた際に一番近いグラフとの距離が大きくなればOKというように近似し、時間で無理やり遷移させる確率を変えながらグラフの組み合わせをよくしました。(Predictor.climbing関数)

technique

numpyによる並列化

生のPythonでループを書くと遅いので、numpyによって高速化を行いました。 numpyを採用した理由は、np.random.binomialが使えたというのもあるのですが、普段はdeeplearningのためにTensorFlowの関数を用いたGPUによる高速化を行うことが多く、行列計算による高速化に慣れていたのが理由です。(大体似た感じで書けますが、たまにnp.linalg.svdとtf.linalg.svdみたいに違う関数があるので〇にますが...) numpyは配列のindexingが簡単ですが、tensorflowはtf.gatherやtf.tensor_scatter_nd_XX系を使う必要があります。この辺りは慣れるとパズルみたいで楽しいです。

matplotlibによる可視化

生成したグラフの次数の配列の組み合わせはmatplotlibで可視化しました。 以下のツイートのようなグラフを生成し、どのようなグラフがいい性質を持つかを考察していました。

Jupyter notebookによるテスト

テストはJupyter notebook上でマジックコマンドを用いて一つのバージョン一つのセルでテストを回しました。 公式のテスターを用い、以下のようなコードでテストを回しました。

for i in range(20):
    print(i)
    inp = f"in/{i:04}.txt"
    oup = f"out/{i:04}.txt"
    !tester.exe python script/exp027.py < $inp > $oup

joblibによるパラメータ探索

今回は各土日に集中して終了ぎりぎりまで取り組んだため、事前にMとepsから最適なNを決定し埋め込むことまでたどり着けませんでした。 ただ、途中で並列化によるN探索のコードは書いていて、その際はjoblibによる並列化を行っていました。 joblibはPythonで(比較的簡単に)プロセス並列を行うためのライブラリで、以下のようなコードで並列化ができます。

from joblib import Parallel, delayed
from math import sqrt
Parallel(n_jobs=1)(delayed(sqrt)(i**2) for i in range(10))

感想＆謝辞

HTTFは2018年の#ふみこん openから毎年参加しているのですが、今回もとても面白い問題でした。 本戦オープンや来年以降も楽しみにしています！ありがとうございました！