暫定201,809点、169位。システムテスト後は8,566,178点、165位。
Seed 0から7の結果。
コンテスト開始前
1位の方の回答がTシャツに！？
1位の方の回答がTシャツに！？ これは欲しい。ということは、「映える」ようの結果が出てくる問題なのだろうな。どんなのなんだろう。
8月9日～8月14日
コミケが忙しかった。 問題は見ていたけど、特に考えてはいなかった。
考察
後から参加する人の特権として、順位表から得られる情報が考察に使える。 順位とスコアをグラフにプロットしてみる。
順位表をそのままExcelに貼り付けたらセルが結合されていて面倒そうだったので、JSONを保存してPythonでゴニョゴニョ。 AtCoderのスコアって、内部的には実際のスコアを100倍した整数なのか。
25万点のところでグラフが折れ曲がっている。 25万点というスコアは、1種類のコンピューターを全てクラスタにしたときに得られるスコア。 そこから2種類目のクラスタを大きくできるかどうかに壁がある？ 5000点でも曲がっている。 これは……なんだろうね。
クラスタに他の種類のコンピューターを混ぜるべきかどうかで、やることがだいぶ変わりそう。 スコアを考えてみると、50台のコンピュータのクラスタ2台よりは、間に他の種類のコンピュータを混ぜてでも繋げたほうが得だな。
ヒューリスティックコンテストと言えば、手法は焼き鈍しかビームサーチ。 移動にちょっとビームサーチっぽさを感じるけど、そんなに動かせないし、焼き鈍し一択だろう （貪欲的な解法は完全に発想から抜け落ちていた。結果的にそっちのほうが正解だったっぽい）。
接続と移動の合計がコンピューター数。 ということは、クラスタの個数だけコンピュータを移動することができる。 この問題設定の意味は……？ とか考えていた。
焼き鈍し
まずは、移動は無しで、接続を切ったり繋げたりで焼き鈍し。 本当は、クラスタの構成を変えずに繋げ直す（一度ループを作って別の場所を切る）というのができると良いのだろうな。 切って繋げては一度スコアの谷を下りることになるので、遷移がしづらい。 でも、時間が無いからそんなのの実装は無理。
10台のクラスタを11台にするのと、90台のクラスタを91台にするのとでは、スコアの上がり方が全然違う。 これを同じ温度で扱うのは無理があるだろう。 どうするかな……。 スコアは台数の2乗に比例するので、スコアの平方根を使えば良いか。 時間が無いので、ちゃんと検証はしていない。 適当。
91,223点
上位陣が30万点であることを思うと、まずまずのスコア。 方針は合っていそうだな（合っていなかった）。
線を繋ぐときに交差する線を切る
横の赤線が配線済みで、縦の青線を配線しようとするとき、今まで単に諦めていた。 焼き鈍しの過程で、赤線が切れた後に、青線が繋がることを期待するしかない。 それは無茶なので、線が交差していたら、諦めるのではなくその線を切るようにしてみた。
99,082点
サーバーの移動
そろそろ移動を考えるか。
移動の回数について。
これは、ローカルテスターに入っていた100個のテストケースから今の実装で得られた結果について、Kの値でグラフを分け、Nの値を横軸に、配線が終わった後の残り手数を縦軸に取っている。 サーバーを移動したことによって配線しやすくなることを考慮して、このグラフのちょっと下あたりの回数を移動に割り当てれば良いだろう。 本当は移動回数を色々と変えて、どのくらいを割り当てるのが最適なのかを検証するべきだろうが、そんな時間は無い。
移動の方法について。 移動の順序まで考えないといけないのは面倒。 ビジュアライザの結果を見るに、1マス移動するだけでもだいぶマシになりそう。 で、さらに、他のサーバーの元の位置も現在の位置も移動先には選択しないとすれば、互いに干渉しなくなって楽になるはず。
移動の結果の評価について。 上下左右を見て、最初にぶつかるサーバーが同種なら+1で良いだろ。 時間が無いので適当。
最初に移動。その後で配線をするという作戦である。 これは良くなくて、配線をしながら「ここにサーバーがあったらなぁ」というのを考えながら移動をするべきだろうが……どうやったら良いのか分からん。
184,088点
だいぶ良い感じになってきた。
種類によって重み付け
上位陣のスコアを見るに、全ての種類のサーバーで大きなクラスタを作るのは無理である。 各種類がそこそこの大きさよりは、特定の種類だけ大きなクラスタになっているほうが良い。 移動の段階で種類1だけ、スコアを5倍にしてみる。
201,809点
20万点を超えたし、運が良ければ景品をもらえる順位である200位以内にも入った。 満足。 終わり。
