Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017にて33位でフィニッシュした
このコンテスト50位以内だと何か記念品等というのをもらえるらしく、つまり記念品等に当選した
この当選は参加者が少ないおかげで実現した感じ
(Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017のほうでも50位以内に記念品等がもらえるというのがあったけどこちらは結果94位と全然届かなかった…参加者が多かったため強い人が多かったので…)
Hokkaido Univ. & Hitachi New-concept Computing Contest 2017を開催します:研究開発:日立
Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017のコンテストページ
hokudai-hitachi2017-2.contest.atcoder.jp
Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017での最終提出コード
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017のコンテストページ
hokudai-hitachi2017-1.contest.atcoder.jp
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017での最終提出コード
あー、まぁ一応書くか、方針
今回はどちらもRustを使って書いた
2ndのほうは
2個を斜めに繋いだ辺を1つの集合の単位として
綺麗に並べて入力のグラフの頂点を辺に割り当てて
総当りで2辺を選んでスコアが上がるよう交換していくって感じ
焼きなまし法(?)っぽい感じでたまにスコア下がる交換も交えて29sec間交換しつづけ
残り時間1secでスコア上がる交換だけをするって感じ
(1secがギリギリすぎたっため最終提出のは1つのケースでタイムリミットを超えてしまった…)
1stのほうは
出力先のグラフの中央付近から入力グラフの頂点をスコアが高くなるように貪欲法的に配置したあと
2頂点をランダムに選らんで焼きなまし法(?)っぽい感じでたまにスコア下がる交換も交えて9.8sec間交換しつづけただけ
(焼きなまし時のスコア計算が間違っていたことにコンテスト終了数日後に気がついたが時すでに遅しだった)