phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

TCO18 MM R1 RoadsAndJunctions

概要

ラソンはできるだけ参加していきたいお気持ちだったので参加。

問題やスコアリングが微妙らしく、苦情もでてた。
(Unratedにもなりえそうだけど、まあしょうがない)

最終順位は107位(239人参加)でした。

問題

10~100の町があり、これらすべてを道でつなぎたい。
ただし、確率fpで建設に失敗するジャンクションをコストJCで任意地点に設置依頼することができ、もし成功した場合は道をつなぐ選択肢に含めることができる。
スコアを「設置依頼したジャンクション数 * JC + 道の総距離」としたとき、これを最小化せよ。

最終的に提出したアプローチ

  • 町に対してドロネー三角形分割して、各三角形からシュタイナー点の候補を列挙
  • 候補点を使うか使わないかを焼きなまし(どちらかというとベター山登りのつもりで使用)で決定
  • fpを考慮したスコアを計算して、その平均値がfpを0としたときよりも大きく、コストJCが小さい場合に使う候補点すべてを多重化
    • 1点追加のみ

振り返り

工夫したつもりでも順位とか下がって最終提出に入れられなかった。

シュタイナー点の候補列挙と使うものの選択

【最終提出に入れたこと】
最小シュタイナー木問題は知っていたので、3点決めてのシュタイナー点を候補とするとよいのでは?と思って「MST作って、その2辺で作れる三角形」と「ランダムに3点選んで三角形」で時間いっぱい山登りを書いたところ、まあまあなスコアがでていたので、それを最初に提出。

そのあと、いい感じの三角形を用意するのに「ドロネー三角形分割」で三角形を決めるように変更し、(回数を稼いでないので)ベター山登りのつもりで焼きなました。

【最終提出に入れなかったこと】
隣接三角形から四角形を使って、(正方形に近い形の場合を想定して)その四角形の対角線の交点と辺で作られる三角形からも候補点を求めたりしたけど、候補点数が多くなりすぎて計算回数をあまり確保できていないところで使うとあんまり効果が得られなかったようなので、最終提出には入れなかった。

焼きなましするのに高速化は口酸っぱく言われてたので考えていたけど、時間伸ばしたりしても改善があんまり見られなかったり、高速化しなくてもそこそこ良い解にたどり着けてしまっていたので、雑な実装のままで終わってしまった。
ただ、回数はある程度確保できるよう、改善率の多い候補点を選ぶようにはしたけど、提出したらスコア下がったのでいれなかった。
ツイッターみてると、クラスカルの差分更新の案やPrim法使うなど、議論されてたので、もっときちんと考えるべきだった。

ジャンクションの多重化

結果がランダムに変化するので、できるだけ分散が小さい方がよいのでは?と思い、考えてた。

【最終提出に入れたこと】
JCが小さく、追加ジャンクション数が多い何個かのテストケースで、ジャンクションの真横にジャンクションを置いて多重化することで何回か実行しても結果がよりよくなることがあるので、そういうケースのために、全部のジャンクションを多重化しても、実際のスコア期待値よりも小さければ多重化する、というのを入れておいた。

【最終提出に入れなかったこと】
各ジャンクション個別にも考えて、ジャンクションごとに一番期待値が小さくなるよう候補点を最大4点まで追加するコードもやってみたけど、スコアがものすごく悪化してしまった。(けど、もしかしたらバグで-1なケースが出ていたから下がったかも)。
実際、fp=0.2でジャンクション数が3個追加の場合、

  • 0個失敗=51.2%
  • 1個失敗=38.4%
  • 2個失敗=9.6%
  • 3個失敗=0.8%

ぐらいなので、ほとんどの場合失敗しない。

テストケースが100個や2000個程度(ある程度収束してそう?)だと少なくて、追加するジャンクション数が少ない場合、JCだけコストを費やして失敗したときの保証をかけるより、失敗しない確率に賭けたほうがよいのかと判断して最終提出にはいれなかった。

反省
  • コードの書き方
    • 雑に書きすぎてるので、書き方を修正したい
    • 実験コードなまま提出してしまって、テストが手で確認程度で終わってるので、ちゃんとテスト書きたい
      • 後でそのままライブラリに追加できるように書く
  • コードの管理方法
    • 工夫したい
  • 高速化
    • 焼きなまし使うわりに高速化をサボって焼きなましの本領を発揮できていない気がするのでちゃんと高速化する
  • 評価スクリプトが配布のやつを使ってたせいで時間かかりすぎなので、分散とか高速化の手段を調べておきたい
  • 可視化
    • 手を動かす時間があんまり取れずにテスターのやつだけだったので、可視化ツール導入したい
    • ぐりぐり動かせるよう、診断人さんが使われてたSiv3Dのmacでも使える版OpenSiv3Dをインストールしたのに結局使わず終わった...