■ [TCO][MM]TCO11 Marathon Round2 
http://www.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14556
今回も安定の第2グループ
問題概要
0<=x,y<700の格子点にある点がN個（50<=N<=5000）与えられる。
これらの点を使って凸な多角形をたくさん作る。同じ点は一度しか使えない。
作った多角形それぞれにつき頂点の数を2乗して足し合わせたものがスコアとなる。
ただし作れる多角形には制約があって、
- 一番長い辺の長さと一番短い辺の長さの差がS%以下
- 多角形の中心から一番近い頂点と一番遠い頂点の距離の差がR%以下
- 1<=S,R<=20
基本的な戦略
与えられる点の数の範囲が非常に大きいので、問題のサイズによって方針を変える。
Nが小さい（400以下くらい）場合
まず、15角形、14角形、…と順に調べて、可能な多角形を全部列挙する。
多角形の調査は、最初に2点固定してのDFS。1つ前の辺を元に、次の頂点がどこになるかを予測してその近くにある点を取っていく。
多角形の候補がそろったら、そいつらの最適な組み合わせを探す。全探索+DP+greedy+山登りな感じで次のようにやった。
- 多角形を頂点の数が多い順から12個、それぞれを使う/使わないパターンを全探索して、結果のスコアが高い方から50通りくらいの状態を覚えておく
- スコアが高い方からだけじゃなくて、10通りくらいは少し低いところからもてきとーに取ってきた（おちゃめ機能）。意味がないことはなかったと思う
- 覚えた状態それぞれに対して、次の12個を全探索してまた上位50通りくらいを残す、を続けて最後まで
- これを、多角形の順番や残す個数をランダムに変化させつつ繰り返す
ここ、上位の人は焼きなましでやっているのが多い。
自分も最終日に焼きなましできないかと試してみたけれど、頭悪い近傍の取り方をしてしまって全然改善しなかったので捨ててしまった。
Nが中間（400〜1200くらい）の場合
可能な多角形を全部列挙するには時間が足りなくてスコアが落ちるくらいの問題サイズの場合は、見つかった多角形からすぐ使うようにした。
なので、その後のフェーズの最適な組み合わせを探すのはやらない。
探索の方法はNが小さい場合と同じ。ただし一度使った頂点はもう使わないようにする。
Nが大きい（1200以上くらい）の場合
さらにサイズが大きいと、この探索方法では多角形があるはずなのに見つからないことが増えるので、時間が足りないこと前提で、早い目に多角形が見つかるような探索をする。
テストケースの生成方法から、点の分布がある程度ドーナツ状に広がることがわかる（そんな強い傾向ではないけど）。
点が集中しているあたりの円周上を狙うと、頂点数が多い多角形を作れそう。
というわけで、いろんな中心点といろんな半径に対して、その円周上付近に点が何個あるかを数えて、点の数でソートして多いやつから順に調べた。
M角形を探すときには、角度360°/Mおきに円周上付近の点を候補点として、DFSする。これを始点の位置を少しずつ回転させて続ける。
候補点を列挙するのには、単にループ回すと遅いので、x軸方向へのスキップリスト的なものを作って高速化した。
調べるのは、円周をM等分した点から近いところにある点から順にやった方がいいかなぁとちょっと思ったけれど、結局やらなかった（なぜ…）。
基本的には、たくさん調べられるようになるほどたくさん点の数が多い多角形が見つかってスコアは伸びるので、枝刈りは色々頑張る。
- 一周回る探索は、候補点の数が少ない枠から開始する（早く枝が刈れるように）
- DFSを始める前に、隣り合った候補点グループ間での点の距離の最大値・最小値を出しておいて、辺の長さの制約を狭めるのに使う
最大何角形を調べるかは、問題のパラメタに応じて15とか17とか19とか決めうってたけど、これはいまいちだ。
wataさんが、「M角形が作れたらM+1角形を作りに行ってみる」とやっていて、巧いなーと思った。
反省点
- 大きめのケースでは時間が余っている場合が多い。4角形と3角形だけでも全列挙して最適な組み合わせを探す、というのがやれたら良かっだろうと思う
- これ終了間際に思いついたが実装する余裕がなかった
- 点の数が多くて見てもよく分からないので、ビジュアライザにはほとんど手をかけなかった。ちょこっと画像で出すようにしたくらい。それはまあ良かったと思う。
- かわりに重要だったのが、枝刈りが効くかどうかを見るため、プログラムのどこを何回通ってるかのカウントを色々やってたことだった
- けっこう早い段階からパラメタ調整によるチューニングをやってしまっていた。それは最終日でよいのでもっと良い方針はないかを考えることに時間をかけるべし。
- 期間の後半になると、動いているコードがたくさんある中それを大きく壊して新しい方針のを入れるのが面倒に感じてしまうけど、実際やるとそこまででもないからためらわない
- 早いうちにパラメタチューニングやってしまうと、アルゴリズムが局所最適に陥ってしまって他の方針を試したときに改善が分かりづらくなってしまうような感触もある
- 開始前から慢性的に睡眠不足気味だったので、期間中ずっと思考のキレがいまいちな感じだった。体調は重要。
- テストケースを問題のパラメタに応じて分割して管理するの、これまでやってなくて今回初めてやってみたけど、いまいちうまく取り回せなかった。これはやっていくたびに集計スクリプトも整備されて良くなっていくでしょう。
- とにかく初動が遅い。人によっては3時間くらいで70点あたりを出して通過してるけど、僕はそのスコア出すまでに30時間くらい使ってる…。終盤に時間が足りなくなってアイディアを全部試し切れてないのはこれが原因なのだろうけども一体どうしたらよいのか。
- 最初のうちは、仮の実装でよいのでとにかくたくさんの方針を試すことを優先する、とか？
結果
- 暫定スコア 86.77（100ケースの合計）
- 暫定順位 20位/222人
- 最終スコア 864.05（1000ケースの合計）
- 最終順位 14位
- レート 2094->2154
システムテストでやたら上がったのは、周囲の順位の人がちょこちょこ0点を出しちゃってたからのようだった。
Round3ではだいたい通過ラインと赤化ラインが同じくらいか
