Yandex Algorithm 2017 Marathon 感想
Yandex Algorithm 2017 Marathonの反省です．
Marathon Roundは2017/5/6, 6:00~2017/5/8, 6:00の2日間で行われました．
https://contest.yandex.com/algorithm2017/contest/4524/problems/
問題
N×Mのグリッド上に生命の泉と魔法の泉がK個ある．
このグリッドをK色に塗り分ける．
この時，同色のマスは連結であり，生命の泉と魔法の泉をちょうど1つずつ含む必要がある．
スコアは，面積 / 別の色との隣接数^2 を各色について算出したものの平均とする．
方針
- 生命の泉と魔法の泉のペアを作る．（ペア間の線分の交差数と距離の和が小さくなるようにビームサーチ）
- 各ペア間のパスを塗る
- まだ塗られていないマスを隣接マスで一番多い色で塗る．
- 1つペアを変えて2,3を試す．（スコアでビームサーチ）
ソース
綺麗にしてから上げます．
反省
- ペア生成に関して
- 方針の1は最小費用流を使ったマッチングでこれより良いペアが見つかりそう．
- 塗り分けに関して
- まず，ペアの作成より色を塗る部分の方が得点に関わってくることを見抜けなかった
- 同面積であれば正方形に近い方が得点が高いので，その辺を考慮すべきだった．
- 全般
- 制約を確認していない．
- スコアの伸ばし方をしっかり考えずに取り組み始めた．
- ビームサーチ等の実装に時間を取られすぎるのでパッと試せるようにテンプレ化しておきたい
- 雑なvisualizerを作ったのはモチベの向上に割りと良かった．（素早く作れるように練習が必要そう）
