■ [MM]Marathon Match 74 
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14672&pm=11585
問題概要
平面内に3〜10個の点がある。うち1つがスタート地点。これに追加でN個の点を置く。
置かれた点に対し、未訪問のうち一番近いところへ行くという戦略で全部の点を巡回する。
N個の点をうまく配置して、この巡回経路の長さを最大化せよ。
10<=N<=10000
自明解フェーズ
とりあえずランダムに置いてみる→短いパスばかりになってすごく弱そう
これなら等間隔に格子な感じで置いた方が良い
あとこれ焼きなましできるけど、点を移動したときの再計算が簡単じゃないからあまり焼きなましゲーにはならなさそう？
実行時間が余るようなら入れる、というくらいで
スタートラインとしては、等間隔の格子に置く→順番を入れ替えたりランダムな位置に移動させたりの焼きなまし あたりか
これで40-50点くらいは取れるのではないかと
あとNが大きいと、ツアーを計算するのにナイーブなO(N^2)では遅すぎるので空間分割的な何らかの方法を使うべし
はじめ50*50くらいのバケットに分ける方法でやったけど、あとで四分木に移行した。両者速度的にはそこまでの違いはなさそうだけど、まあ有名っぽいアルゴリズムを使ったほうが、というくらい
最終的にN=10000で800回くらいは再計算できた
思考フェーズ
最初格子は正方形でやってたけど正三角形のが密度高くていいですよねもちろん…。すぐ見えてなかったのが残念（1週間くらい気づいてなかった）
昔のMarathonでも出てきてたのに
長いパスがたくさんできるよう、点を後回しにできるような辿り方を考える。
かなり試行錯誤した結果、2つのパターンを使った。うち1つは次のような感じ。3層構造。
実線の矢印のようにずらすと破線の矢印のように辿れる。
√3が無理数なせいで厳密に正三角形にはできないが、どうせこの通りに辿っていくようちょっとずつずらして調整するので別によい。
どのくらい調整すれば相互に影響せず綺麗に辿っていけるかを決めるのが大変だった。
この2つのパターンから、固定点を考慮するために点の配置を回転したり鏡像反転したものについてスコアを計算して、一番良かったものを焼きなましのスタートとして使う。
ただし、Nが小さいときは初期状態にどれを使うかでかなり結果が異なり、焼きなましもけっこうすぐ収束してしまっていたので、上の2パターンに加えて単に正三角形に置いただけの計3パターンを少しずつ焼きなましてみて、一番良くなったものを残り時間さらに焼きなますようにした。
チューニングフェーズ
1位のスコアがかなり離れていたので、まだ見つけていない最強のパターンがあるだろうと思って探していたが見つからず、諦めて終了2日前くらいからチューニングに専念
こんなことをやった。
- スコアの再計算のときに点同士の二乗距離を頻繁に計算するので、Nが大きくない範囲では前もって計算しておいてテーブルに入れておく方が良い
- 4割くらい速くなった
- ある点の最近接点を探すとき、N回ループを回して訪問済みの点ではcontinueするのではなく、未訪問点だけのリンクリストを作ってループと条件分岐の回数を減らすようにした
- 1割くらい速くなった
- 4隅には常に点を置くようにして、焼きなましからも除外して固定してしまう
- 小さいケースで少し良い結果になる
- 四分木から最近接点を探すとき、前回のパスで次に辿ることになっていた点が今回の探索で未訪問だったら、そこまでの距離を良い上限として使う
- 四分木の各ノードで、子に含まれる点からバウンディングボックスを計算して随時更新し、枝刈りの条件をきつくするのに使う
あとC++化もやってみたが、単に書き換えただけでは前にやったとき（TCO11Round2）と同じく逆に遅くなってしまった（gettimeofdayの問題ではない）。JavaでもJITコンパイル効いてたらC++と遜色ないね
それからさらに細かい高速化を積み重ねていったら究極的にはJavaよりC++の方が良くなるのだろうが、ノウハウないしそこまでの時間もないしで結局最後までJavaでやった
ともかく、チューニングは最後！ と決めてやっていたので、序盤-中盤のうちに無駄にチューニングして時間を消費するのを避けられたのは良かったと思う
反省フェーズ
statisticsを見ると、サイズによるスコアの違いは意外と平均的だった。もっとNが小さいケースで盛大に負けていると思っていたのだが
焼きなましはランダムな場所に移動するのしかやってなかったけど、ちょこっとだけ動かすのも試したほうが良かったかもしれない（ainu7さんとかがやってる）
逆側から決めていくという発想はまったく出てこなかった。
Nが小さい場合はパターンが大して効かず、焼きなましの運ゲーになってスコアが安定してなかったから、ツアーの最後のほうの長いパスが出てくるところを固定して決められるこの方法を取り入れることができてればだいぶ良かったんじゃないかと思う
この「長いパスは最後の方によく出てくる」という点についての考察ができていなかった。
ビジュアライザの画像をよーく分析していたら見えていたかも
あとケースごとの相対評価なので、Nが小さいケースではスコアの違いが小さくても割合的には重要なのだけど、やっぱりスコアの数字見てると大きいケースでの改善の方が絶対値が大きくて良くなってるように見えるから、小さいケースの重要性を実際よりも低く認識していた
（10.0->10.2になるのと150->152になるのは前者の方がより重要）
スコア計算するところで、1点進むごとに距離を律儀に10^9で割ってたけど必要なかった…。Nが小さいとこれだけで1割くらい速くなる
結果
今回も着実にまずまずの成績を取れてRedになれたのは良かったが、1位との差が大きすぎる
これきっと通常マッチだからこの順位になれてるわけで、もしこれがTCOだったら20位台くらいなんじゃないかと思われる
画像
