Hokkaido Univ. & Hitachi 1st New-concept Computing Contest 2017

2017/12/01 (Fri) MM

問題文

全文はこちら

要約 :

2 つのグラフ $G, G_{emb}$ が与えられる.ただし $|V(G)| \le |V(G_{emb})|$ であり,$G$ はランダムグラフまたは完全グラフ,$G_{emb}$ は king’s graph である. また,$G$ の辺 $e$ には重み $w(e)$ がある. 単射 $\phi : V(G) \to V(G_{emb})$ のスコアは,$uv \in E(G)$ かつ $\phi(u)\phi(v) \in E(G_{emb})$ であるような,$w(uv)$ の総和で計算される. スコアが大きい $\phi$ を求めなさい.

結果

順位表

47 位でした.北大と日立のグッズがもらえるそう✌.

やったこと

最終的な提出でやっていることは次の通り.

  • 写す先は正方形に固定する.
  • 初期解は左上から 1, 2, 3, … と順番に並べる.
  • 焼きなまし法をする.近傍は次の通り:
    • $G_{emb}$ に写した先の頂点をランダムに 2 つ選んで入れ替える (127/128の割合で).
      • ただし,(稼げているスコア) / (刺さっている辺の重みの合計) が小さいものが少しだけ優先的に選ばれるようにする.
    • $G_{emb}$ で隣接しない頂点集合をランダムに選び,そこに写されている頂点をハンガリアン法によって最適に配置する (1/128の割合で).
  • 最後の 50 ミリ秒で,山登り法をして最終調整する.

ファーストインプレッションから焼きなまし法が良さそうだと思っていた. とりあえず,何も考えずに 2 頂点を選んで,写した先を入れ替える山登り法を組んで出してみたら当時 60 位くらいになった. 山登りを焼きなましに変えればわりといい順位に着くような気がしたので,焼きなましでいいのかなっていう気分になった.

適当に Prim 法みたいな貪欲をしてもあまり良くならず,ビームサーチか Chokudai サーチをするにも,状態をうまく持たないとメモリがアになってつらそうだと思ったのもある.

正方形に固定したのは,最初にバラバラな状態を初期状態にしてやっていたら,収束が間に合わずけっこう非連結なまま時間切れになることが多かったかったから. 今思えば,なぜ固定するのは初期だけにして遷移は自由にしなかったんだろう.

ハンガリアン法の部分を簡単に解説してみる. まず,$V(G_{emb})$ から隣接しない (誘導部分グラフに辺が無い) 部分集合 $S$ を適当に選ぶ.大きさは大きくても 50 程度にする. 次に,$V(G)$ から $S$ と同じサイズの部分集合を選ぶ. $v \in V(G)$ を各 $v’ \in S$ に写したときに得られるスコアを計算しておく.これは,$v$ 以外の $V(G)$ の頂点の写し先に影響されないことに注意. すると,$|S|^2$ 通りの組み合わせそれぞれのスコアを要素とする行列ができる.

この行列を利益行列として,ハンガリアン法 を適用すると,最適な割り当て方がわかる. ただし,$O(|S|^3)$ の計算量がかかるのと,グラフ全体を見たときの局所最適に陥りやすいので,呼び過ぎないようにする. 最小費用流と両方試したけどハンガリアン法の方が速かった.

焼きなまし法の最終的なイテレーション回数は平均して 1 億くらいだと思う. 時間を 200 秒にして走らせるとスコアが爆上がりしたので,高速化が効くのは分かっていたけど, それよりも上位の人たちはもっと賢い遷移を思いついていると思ったので,そっちを優先してた. 実際,賢い遷移をしていたという予想は正しく,またイテレーション回数も 2 倍以上の人ばかりで完全に負けていたのでさすがだなあという感じである.

ちなみに,システムテストが無いルールだったときに,シードを特定するスクリプトを書いて走らせるのをやった. 僕はこの手法を kyuridenamida さんから学んだので kyuridenamida 法と勝手に呼んでいる.

感想

  • かけた時間の割に順位がよくてうれしい.
  • wata さんや tmaehara さんのようなリアルガチ最適化マンが参加していてうおおとなった.
  • AtCoder では clock 関数が大きなボトルネックにはならず,rdtsc 命令を使わなくてよかったのでやりやすかった.
  • コードテストも便利だった
  • 2nd コンテストはもっと時間が取れないのでどれくらい真面目にやるか分からない.
  • 今後も AtCoder マラソンが継続的に開催されるとうれしいなあ.