TopCoder の MarathonMatch 130 に参加しました。
問題はGraphLabeling。同名の既存問題です。
事前テストは66人中31位でした。
問題
グラフの各ノード（頂点）にUniqueな値を割り振って、
ついでに辺で繋がったノード同士の差もUniqueにしてね。
頂点に割り振る値の最大値を最小化してね。
最終的にやったこと
貪欲で一番小さい値を置き続ける以外に現実的な実装が思いつかない。あとは順番をどうするかしか無さそう。
大きい値と大きい値に大きい差が付くと値が跳ね上がる。後で置く場所≒大きい値を置く場所なので、後で置く場所同士の隣接を減らせると良い？
→1秒間焼きなましで順番の積の総和を最小化。
やったけど没にした方針
全連結されたグループを探して最初に埋める。全連結の組合せ最適を得るのが難しい。速度を出すのも難しい。
順番をDFS風にしたりBFS風にしたり。最初に作ったお気持ち評価が強すぎて改善できない。
大グループと小グループに分けて、双方向に伸ばしたり、双方向から間に向かって伸ばしたり。前者は両グループに隣接するノードがあると上手く行かない。後者は上手く隙間が埋まれば良さそうに感じるけど、実際のところ埋まらない。
他の人の解法
最小値を貪欲に置く方針は大体皆一緒らしい。
差が出たのは連結密度が高くて値が跳ね上がるケース。ゴロム定規という既存の解（？）があり、検索→解を生成して貼り付けるのでseed2で100倍差が付くらしい。
感想
既存の解法を参考に何かを作ろうとか、自分で考えたものを埋め込むならまだマラソンらしさがあるのだけど、既存のものを丸々埋め込むだけはちょっと楽しめない。
マラソンの形は色々あるし、好みじゃないものも認めていきたいけど、うーむ。
あとはローカルPC上だとseed=2は余裕だったけど、提出上だと全然通る気配が無かった。時間が厳しくて枝刈りも出来ない系の問題だとどうしようもなく…。*1
あらゆる楽しめない要素がこれでもかと詰め込まれていたので、一旦全てを忘れたいです…。
