HxHMM1st参加記録

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017の参加記録です.

結果

システス前 15位
システス後 16位
順位表1ページ目(20位以内)に入ることが目標だったので,目標は達成できました.
 最終的な私の解法は「ビームサーチ+ちょっとした山登り」でしたが,ツイッターを見ると上位陣はほとんど辺の入れ替えで焼きなましをしていたみたいです.一度だけ点の入れ替えで焼きなましをしましたが,微妙だったので大して検討もせず「上位陣はもう少しいい感じにビームサーチしてるんだろう」と考えて焼きなましはそこで捨ててしまいました.
 途中でビジュアライザを作りそれを眺めていましたが,特に改善点が浮かばず結局どの問題でも当たり前にやること(重複除去とか高速化)を順当にやっていただけで終わってしまいました.
 文字だけだと味気ないので記事の一番下にランダムシード8の結果を張っておきます.辺は赤ほど重く青に行くほど軽くなります.

最終的な方針

  • 1つ目の頂点を G_{emb}の中央に置いてそこから幅 max(10,  \lfloor 0.2*|V| \rfloor)でビームサーチをする.
  • 評価は問題のスコアをそのまま使った.
  • 時間が余る場合は頂点を見る順番を変えてもう一度ビームサーチ.
  • 最後にビームサーチで1番良かった解を頂点移動,交換の操作で山登り.
  • 方針ではないがコンパイラはclangにした.gccより1.1~1.2倍ほど速かった.

点数の推移

  • 154598 貪欲に置いていく
  • 156796 頂点を見る順番をランダムにして時間いっぱい試すようにした
  • 158065 貪欲でできた解を頂点移動,交換で山登りするようにした
  • 159099 ビームサーチ化
  • 160256 重複除去を入れた
  • 161592 高速化 & パラメータ調整

f:id:shamal_ref:20171130221518p:plain
random seed: 8