■ [MM]Marathon Match49 
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13709&pm=10032
友達を大量に集めてパーティを開きたいんだけど、各人の間に仲の良し悪しがあるので、仲がいいやつ同士を近くに、悪いやつ同士を遠くに配置してみんなをハッピーにしましょう、という課題。
アプローチ1
まずN人の順番をシャッフルする。
1人ずつ、ランダムな位置に仮置き→スコアを計算 を何回か行ってスコアが最良だった試行を採用、としながら全員を配置していく。
これを時間制限じゅう繰り返して、もっともスコアが良かったものを採用する。
この時点でスコア20くらい
アプローチ2
まず、アプローチ1と同じ方法で1度N人の配置を作る。
それから1人ずつ取り出して、別の場所に移動したらスコアが上がるかを調べて、上がるなら移動する、というのを時間制限じゅう繰り返す。
（マラソンでよく聞く「焼きなまし法」ってこれのことなのかな？）
この時点でスコア35くらい
アプローチ3
何回かアプローチ1の方法でN人の配置を作り、その中で1番スコアが良かったものをアプローチ2にかける。
この時点でスコア40くらい
アプローチ4
人を配置する位置をこれまでは小数で扱っていたが、一辺10の正六角形を並べた蜂の巣状座標の格子点だけに配置するようにした。
メリットは、
- 座標が小数から整数になるので計算する量が減る
- 実数座標を離散化して整数インデックスで扱うことにより計算量を実行可能な量に落とすというのは、SRMでもけっこう出てくる手法か
- 人どうしが近すぎないかを確認する手間が減る
- （たぶん）最密構造なので、全体の面積が小さくなる
この時点でスコア60くらい
アプローチ5
最初に並べるときの順番を工夫しようとした。
- 入力の友達関係はある程度クラスタ化されているはずなので、仲良しグループを検出してそいつらを最初に並べる
- 重要人物を先に並べる
- 友達が多いやつを先に並べる
…など試したけれども、結果はかんばしくなかった。ランダムの方がいいスコアになるとは。
結果
スコア 60.33 （最良を100とした相対評価）
暫定順位 27/111
前回は真ん中ちょい上あたりだったのが、上位1/4になれました。
今回は賞金付きではなかったので強い人の参加が少なかったのでしょうか。
感想
配置するにあたって面積が小さくなることはそれほど重視していませんでしたが、仲が悪い人が多い状況では、全体を細長ーい形状にして面積を小さくすることがかなり効いてくるようです。また、細長い形状だと、正方形に近い形状に比べて人どうしの平均距離が伸びるので、仲が悪い人どうしが近い位置に配置されることによるマイナスも小さくなりそう。
これらを考慮に入れていなかったので、僕の結果を上位の人のと比べるとテストデータによってはスコアが20倍くらい違っています。数学的考察重要だなあ。
今回は問題が比較的シンプルだったので、後半はできることが無くなってしまってスコアが全然上がらず苦しかったです。
というか前回がかなりいい問題だったのか。
