問題
#AtCoderAGCコラボ
— TEA(ティー) (@tea437354) May 14, 2019
AGC社は特殊な窓ガラスを発明しました。ある座標に設置すると壁もしくは端に当たるまで縦横1直線にガラスが伸びるようになってます。
とある一面に窓を設置したいです。最低何枚のガラスが必要でしょう?
なお、1マスにガラスは複数枚重なっても構いません。 pic.twitter.com/bkJTRgG15b
Approach 焼きなまし法にしたけど、山登り法になりました。
- 近傍1 : ガラスを消す
- 近傍2 : ガラスを同一直線上に移動する
- 近傍3 : ガラスを同一直線上でもっとも重複しているところに移動する
- 近傍(使わなかった) : ガラスをランダムに置く
- これをやった方が良いときもあったが、平均するとない方が良かった。
感想 IP ができるようなったかも。MM107 のようにほとんど最適解が求まるかと思ったけどそうでもなかった。
IP は koyumeishi さんの https://gist.github.com/koyumeishi/1dc332012cf875f7892844ddf17a5274
を参考にしました。
source code(Solver IP)
source code(Solver SA)
source code(Tester)