Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017参加記
概要
AtCoderで開催されたマラソンマッチに参加してみた。
phyllo-algo.hatenablog.com
1stの方は比較的時間取れて取り組めたけど、2ndの方は時間がほとんど確保できず、だいたい2.5日分ぐらいしかできなかったと思われる。。
最終順位は6,961,040点で73位。
WAが2つ出てて、Timelimitを10秒で計算してるという大ポカ。
問題
重みなし無向グラフGが与えられる。そのグラフの頂点をG_embの連結な部分頂点集合に対応させる。
基礎点として5000点が与えられる。
G_embの方で部分頂点集合同士で隣接していた場合、+100点となる。
G_embの方で、ある部分頂点集合s(v)の頂点数が|s(v)|である場合、-Σ_v (|s(v)|-1)となる。
Gのすべての辺がG_emb側で隣接状態になっていた場合、ボーナスとして+100000点となる。
連結でない頂点集合だったり、不正な場合は0点となる。
最終得点が最大となるよう対応付けを求めよ。
最終的に提出したアプローチ
- 初期配置は、Gの頂点の近傍ができるだけ近くなるようにランダム配置し、それをできるだけランダムに伸ばせるだけ伸ばしたもの
- G_embの頂点を1つランダムに選び、その8近傍どれかにコピーする焼きなまし
時系列での振り返り
今回は考察重視で行きたいと思ってたけど、何が重要なポイントかは手を動かして見つけないとやっぱりダメだった。
初日～8日目(1日分ぐらい)
- HHMM1とだいたい似ていて、焼きなましが有効そうな形をしていたので、HHMM1の反省をしつつ焼きなましをちゃんと書こうと考えた
- 焼きなましについて勉強&&HHMM1の復習
- おそらく、全部焼きなましに任せるとアレなので、HHMM1と同じように「形を固定化して割り当て問題」か、「近傍のうまい定義」をすればひとまずよさそうか、とか考えていた
- 忙しかったり、体調不良であまり手を動かせず
10日目～12日目(1.5日分ぐらい)
- ひとまず、HHMM1復習のコードを流用してHHMM2用に書き直して様子見
- 実装が適当すぎて、スコアが差分計算できていないので、そこがボトルネックで回数稼げてないコードを作成
- ビジュアライザーは、テキスト出力の簡素なモノしか用意してなかった
- で、どうも、回数稼ぐよりも、初期配置が重要そうな感じだったので、初期配置を中心に考えることにしたが、前半「形の固定化して割り当て問題」を考えていた時のアイデアとか完全に忘れてて、0ベースで考え直し
- 斜めだと、線をまたぐことができるので、平面グラフ的でなくても連結にすることができそうなので、斜めが肝っぽい
- 前半の時の紙を見るに、形状のアイデアとしては、斜め直線型やダイヤモンド型をうまく配置させられれば多くの頂点に絡みそうと考えたらしい
- 直線型よりもうにゃうにゃ絡み合う方が期待できそうな気もするので、ランダムに線を伸ばす感じのコードを作成(最終提出のやつ)
- で、ここで(なぜか)ボーナス点を取りに行っていないことが気になって、上位とはそこが差になっていると考えたため、できるだけちゃんと辺をつなぎに行くような方法を考える方に走った
- グラフが大きくなってもG_emb側で全連結になるよう辺をつなぎに行けるうまい方法が思いつけず、結局時間を無駄にしてしまって終了
13日目
- あきらめて、書いてたコードを提出
- 14日目は時間取れないのがわかっていたのでここで終了
