問題
提出
ダイクストラ内の最短路木の差分更新
- 解説放送でも1位や7位のユーザ解説でも「ダイクストラの実行後は最短路木ができていて、工事を[増やす/減らす]すると最短路木が部分的に変わるだけなので、差分更新で高速化します」と言われている
- 当時は「ほーん、たしかにできそう」でスルーしたが、知っていることとやったことがあるのは違うということで挑戦してみた。1, 2日くらいでできると思っていたら5日かかった
- ハマった理由は、スコアが上がらなかったときに「巻き戻し」する必要があるのにしていなかったから（いつもの[山登り/焼きなまし]では状態のデータが軽いので捨てるだけで済んでいて、盲点だった）
- グラフの持ち方をvectorからsetにしたり、最短路木の管理用に新たに構造体を作ったりもした
初期解
- 連結を重視して、各日にどこからからBFSして全点と連結させた
- さらにスコアを伸ばすなら、すべきは初期解の洗練だろう
サンプル点
- スコアは5頂点からのダイクストラで近似。10頂点にしてもローカルでは悪化した
- 回転数が減るので、登りきれていないのだろう
- （でも参加記では10以上が多かった記憶）
登り成功回数 / 登り挑戦回数 のサンプル
2338/33999
1893/26778
1982/31588
1680/29365
1735/25026
1399/43452
1546/54964
1699/44082
1558/41998
1932/44380
追記：さらに延長戦
216/38806
288/38283
125/20027
139/5611
207/12576
