Marathon Match 49 - MegaParty

TopCoder

初参加。Categories: Geometry, Graph Theoryらしいので暗号系とかよりはたぶん自分向き。
赤Coderが異様に少なかった。

だいたい同じことが書いてありそうなので、こことかをご参考に。
http://d.hatena.ne.jp/chokudai/20090220/1235125554

問題概要

  • 10〜1000人の人がいて、パーティーを開くらしい。人を配置しなさい。
  • 部屋は長方形。
  • ある人から距離10以内に他の人や壁があってはいけません。
  • 距離e1以内に好きな人がいると嬉しさが1点増え、距離e2以内に嫌いな人がいると嬉しさが1点減る。10 <= e1,e2 <= 100
  • 好き嫌い普通の関係は対称的。また、unstableなtriple(好好嫌または嫌嫌嫌な3人組)はテストデータ生成時にできるだけ除去される。
  • 人には重要度(10以下の非負整数)が設定されていて、その人のスコアは、(嬉しさ)×(重要度)
  • (各人のスコアの和)/(部屋の面積)が得点。
  • 相対評価。you/best
  • 制限時間20000MS。

以下自分の方針など

さいしょ

人の重要度とか言っているが、人uとvについて、好きなら(u+v)、嫌いなら-(u+v)、普通なら0で辺uvの価値を定めてしまえばよいことがすぐわかる。

とりあえず嫌いな人を距離e2に置かないように、中心のほうから適当な優先順をつけて適当に置いていったら正の得点が出たのでsubmitしてみたが、20%とかそんなもんで困る。

基本方針

まずe1>e2のとき。
一辺10ちょっとの正三角形格子状に適当に詰めていけば実はかなりの高得点。サンプルのうち3つしかこういうケースがなかったために今回気づけるかどうかのポイント。
部屋のサイズは面積最小のものをO(N)で求めてみた。
中心のほうから、なんか適当な重みをつけて頂点順を考えながら詰める。
実はこっちのケースだけの得点で60%超えたりして面白い。

e1

Swapping

上位に入るための超本質。
とりあえずある配置を作ったあと、ランダム2点を選んで入れ替えてスコアがよくなるなら入れ替える、という単純なことをひたすら繰り返す。
ランダムに重みをつけてもいいかとも思ったが、定数倍とかが重要なので実装を極限まで軽くするため本当にランダムにしてみた。

N個の位置に対してe1とかe2とかの隣接リストを作っておけば、uとvを入れ替えたときのスコアの増分の計算はO(deg(u)+deg(v))とかでできる(これはe1やe2が小さいときはやばいくらい速い)ので、20秒以内に500万回とか、楽なケースだと2000万回とか余裕でできてしまう。

これだけだと結構収束が早いので、どうしようかと思っていたところ、バグを発見。
入れ替えたときにスコアが下がるときがあって、ただそのバグを直すともっと収束が早くなることも発見。
ということで、適当に入れ替えてしまえばさらにいい感じになるのではないか、という発想を保留。

さらに思いついたのが、2点を入れ替えるのではなく3点を入れ替える方法。問題文のunstable tripleのところがヒントになったのかも。
ランダムに3点u,v,w選んで、3!通りのうち最もよいものにする。これもO(deg(u)+deg(v)+deg(w))とかでできるが、この3点が隣接していたりすると多少めんどい。
そこで3点が隣接していたりするときの処理をわざと省き、ときどきスコアを低下させてみる。すると結構伸び、例えばseed7みたいなデータでたぶんbestを取れた。

最終的には、15秒くらいまで10000回くらいずつで3点交換を繰り返して最も良かったときを保存→時間ぎりぎりまで2点交換を繰り返す、というものをsubmitした。

終了後

e1

結果

Provisional Score: 90.86 (4位)
Final Score: 1,789.04 (4位)
MM 0→1803

system testでやっぱりACRushに抜かれたorz
が、jlahdを抜けたので4位フィニッシュ。
赤とかがいないせいでimpressive debutsに載れず。残念。

http://forums.topcoder.com/?module=Thread&threadID=634410&start=0
↑これによればbestは結構取れていたようだがzeroを10個出していて残念。原因は調べていないが、もしかしたらTLEかも？

まあ、緑を目標に黄色になれたのでよし。