2011-04-10 - TopCoderの学習のお時間

非常に今更ながら、今年のTCOも近いことだし振り返り。

ノードの数が1000～20000のでかいグラフが与えられる。

その中から連結しているi個のノードを取り出して、そいつら同士の枝だけを残したグラフをサブグラフH_iと呼ぶ。

H₅、H₆、H₇、…が順番に与えられるので、大きいグラフの中のどのノード由来のものかを答える。制限時間内にいくつ答えられたかがスコアとなる。

解答が複数通り考えられる場合はどれを答えてもよい。

DFS全探索+枝刈り。

早めに解答が見つかるよう・早めに枝が刈れるよう、調べる順番を工夫する。

でかいグラフの方は、たくさん枝を持っているものから順に調べる
サブグラフのノードを一つずつ決定していくにつれて、サブグラフの各ノードがでかいグラフのどのノードに対応する可能性があるかを更新する。どれともマッチする可能性がなくなったノードが現れたら枝を刈る
サブグラフのノードの調べる順序。
- ↑で随時更新している、でかいノードで対応する可能性があるものの数が少ないもの優先
- たくさん枝を持っているもの優先
- そのノードから出るループ（とくに短いもの）を多く持っているもの優先
  - ループが一周つながる（あるノードについて、その隣接ノード複数がでかいグラフでどのノードに対応するか決定された状態になる）とそこで大きく枝が刈れるので
- これら3つを状況に応じて重み付けして決定

よく覚えてないのでほかにもあったに違いない

順位：22位/79人

レート：2074->2105

速度を上げると確実にスコアは上がるのはわかっていたことだからさっさとC++に書き換えるべきだった
- この頃は「Javaで最上位にならない限り書き換えはしない」という妙なこだわりを持っていた
全体のスコアに大きく効く部分に注力するという発想がなかった。終盤かなり思考の袋小路に陥って細かい高速化ぐらいしかやれなくなってしまっていた
- ログ出力の様子はいっぱい見てて、どんなときに早く答えが決まりやすいのかは把握していたはずだが
- 時間はまだあったのだから、細かい調整は後回しにして大きな変更をがんがん試さないとTCOでは上位にはとても入れない
- チューニングは本当に最後の局面になってからにするべし
サブグラフのほうを、リーフノードとそうじゃないノード（ループを持つノード）を塗り分けて画像に出力していた。これはアイディアを考える上でとても役に立った（wataさんのビジュアライザほどではありませんが…）