北大&日立 新概念コンピューティングコンテスト2017 1st
この記事は、Kobe University Advent Calendar 2017の5日目の記事です。
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017で優勝しました。30万円もらいます。
1位：30万円
2位：5万円
3位：3万円
4～10位：北大及び日立グッズ
11～50位：記念品
51位～：抽選で記念の粗品
がもらえます。
問題概要
問題はこちらです。
グラフGとGembが与えられて、Gの頂点に対しGembの頂点を対応させて、Gで隣接した2つの頂点がGembでも隣接してればその辺の重みをもらえて、もらえる重みの総和を最大化する問題です。
やったこと
焼き鈍せばいいんでしょと思いつつ、まずランダムにGの頂点を二つ選んで隣接させるように動かす山登り
->95201点
低い...
焼き鈍しと枝刈り
->126739点
まだ低い...
中心付近に頂点を置いて初期解生成
GCCからClangに変更
->137635点
しばらく迷走
重み0の辺は無視する
参考論文にあったとおりに初期解生成
スコアの変化量を逐次計算せずに保持しておいて遷移したときに更新する
Gのある頂点を選ぶ(ランダムではなく順番に)、そして必ず変化が起こるような地点を選んでswapする
->159981点
ようやく上位に来れて安心
ここまでで3日
状態が変わらないのに遷移することがあったのでしないようにする
一定数swap先を選んで一番変化量が良い地点を選ぶ
->161968点
swap先を保持していたのをやめる
Gで隣接している頂点の中から辺の重みが大きいほど選びやすくして頂点を選ぶ、その頂点のGembの8方位の中からランダムにswap先を選ぶ
->162772点
ここまでで1週間くらい
Gの平均次数が低いとき枝刈りの値を変える
->163398点
ここから全く上がらなくなる
金曜日から試験期間が始まるがマラソンをする
土日にCodeFestival2017に行ってマラソンをする
CodeFestivalの帰りの新幹線の中で、横でシード値特定しようとしてたのにという話がなされてる中、真面目に考察してひらめく
隣接した地点をswapするときのスコア変化量の調整を逐次していたのをやめる
swap先を選ぶときの回数をその頂点の次数回にする
温度と枝刈りの値をなんとなく変える
->163563点
平均次数が8以下の時の温度を 下げる
->163.7k点
最終スコア：761063点
最終順位：1位
感想
優勝できて素直にうれしいです。
賞金はVRに投資します。
ところで第2回難しくないですか？考察フェーズから抜け出せないんですが。
