Marathon Match 100 のゴミメモ！
下書きで終わっていた記事が、残っていました。ゴミメモのままでしかないのですが、脱線に至るまでの経緯が、今見るとおもしろかったので、そのまま投稿。
50位以内だと、懐かしの旧TopCoder時代のTシャツがもらえるマッチでした。まだ現役なので、老兵どもに負けるわけにはいかないのじゃ！
結果：76位/280（遠くへ行きたいです）
最初のメモ（開始２日目）
当時のメモで、あまりよく覚えてないのですが…。
ファーストインプレッション
- 近くからしかとらない・縦しかとらない・横しかとらないという条件であれば、いろいろできる
- 斜めどりはかなり難しい。
- ダイヤに穴をあけるようにしても、端からきれいにとっても、取れる箇所はほとんど増えない。
- とったことにより、どれが取れるようになるかの分析が最重要。
- 距離を限定して焼きなましするアイディアは面白いかもしれない。ただ後半の焼きなましは疑問。
- ビジュアライザ、最終的にどれとどれをペアで取ったのかは、見たいかも。
- 無害でとれる
- ハマり形（はまり形を事前に知ってれば、避けたり、評価値に入れたりすることも可能。）
- 焼きなまし解法。
- 遅延セグ木
なんか、うまい取り方を考えようとしてたっぽいですね！（なんで遅延セグ木と書いてるんでしょう…）
反省点：ファーストインプレッションの前に簡単な解法を提出せよ！！
まず、この問題のポイントとして、ほとんどのケースで全部とれます。最初に簡単にそれに気づくはずなのに、その条件なしで考えはじめると、複雑な条件で考えないといけなくなります。無駄に時間がすぎる。
あ、でも、いつも簡単な解法をやらずに失敗しているので、今回は絶対に簡単な解法を書こうと思ったんですよ。でも、なぜか感覚が麻痺していて、
- せめて貪欲法で書きたいなぁ
- なんらかの評価関数がほしいなぁ
- これは取れる個数ができるだけ多くなるように
- めっちゃ重くならない？
- というか、これはどこから取るのがいいんだろう？
- 考察へ移行
という感じで、簡単な解法すら思いつかず、なんか脱線するわけですね、自分をコントロールできない！すでに自我がない！あなたの生きている意味は？
そういうときは、ランダム！O(1)で最強！！
というか、超簡単な解法リストでも作って、機械的にやったほうがいいような気もしてきました。思いつかないんだから。
ファーストインプレッションの前に、簡単な解法
ランダムでとるのが思いつかないんですね…簡単な解法
（ビームサーチ解は捨てる！）
焼きなまし法（最終日）
評価関数
- 解決されていないやつは、後半にとるやつのほうが被害が少ない。
- エリアが広いこと自体をマイナスとしてもいいかも。（すぐに他のやつが入りこむので）
評価差分
囲われフラグは、orderは無視したもの。
- 全盤面評価はひどいので直す。
- Swap Pos -> それぞれのRectごとに、スコアをキャッシュしておく。Rect別再計算
→Orderも考えると、
→今囲んでいるやつ、各点の囲われフラグを解除
→新しく囲んだら、各点に囲んでいるフラグを追加
- Order change -> OrderをかえたRectの再計算。囲われているRectに対して+1,-1
点ごとに、囲われているRectを持つ必要がある。→これは問題！！！
- Order Changeはなしにして、定期的にOrder計算と最終結果計算を行う方法はあるかも。
面積でソートすれば、それなりに
- そもそも距離2のは無条件にとって良い。order無意味。
- Orderほんと必要？一意に決まるのに。
- 分割エリアごと orderなら毎回
- Forward形式に変更
近傍
- SwapOrderをChange Orderにする（orderはfloatかdouble）
- 移動をprogression ratioに合わせて、徐々に小さく（Swap Pos・Change Order両方）
- Posを移動面積距離が大きい順にソートして、近くしか移動
- だめな部分を狙って変更する？
温度管理
→ats式がよさそう。
大きい近傍
- 分割統治（やるなら、端からとったほうが良さげ）
わるあがき
- はじを優先的にとるランダム
- 後半単純に遅いかも。
- 失敗したやつを優先的のとるランダム（これは簡単なので、先にやっていいかも）
- 焼きなましの結果を使う
- 高速化版ランダムGreedy解法
- ランダム途中からスタート解法
初期解
- 最寄りペアからスタート
- 貪欲解からスタートのほうがいいのでは！？まぎれが少ないし、一定の得点は保証される。逆より全然良い。ただし、
