北大日立新概念コンテスト1stの僕の解法

北大日立コン1st,最終systest736571点,29位でした。以下、かいせつです。 僕の最終方針は、9秒間ビームサーチして、最後の1秒焼きなます方法です。 盤面に点を順番におくのをビームサーチして、最後の方は置く選択肢が少なくなってあまりよくない感じなので、焼きなましで仕上げを行った。 ビームサーチで置いた後、余った点を焼きなましで配置するということです。

11/15 17:07 145320点　貪欲に上から置いていった。ただし、GVの正方形をVぐらいのサイズの正方形の形に収めるようにした。(例えばGV=36,V=5のとき、

1,2,3,4,5,6
7
ではなく
1,2,3
4,5,6
7
にした。(これはビームサーチするときもこのようにおいてます) 11/15 18:08 149919点　焼きなまし法である点と点の交換を行ったが、焼きなまし温度をバグらせていて、温度が上昇してしまっていた。

11/16 17:06 141447点　貪欲をビームサーチにした。

11/16 18:11 154956点　焼きなまし法の温度管理のバグに気が付いた。(実はこのころはビームサーチの回数が固定なため、実質焼きなまし法onlyの点数) やらかし 実質焼きなまし法のスコアなのに、ビーム+焼きなましの成果だと誤認。焼きなましはパラメーター調整しかないと思っていたので、ビームサーチの改良に進んでしまった。

11/17 16:23 158173点　ビームサーチの時間を管理して、しっかり8秒まわすようにした。やっぱりビームサーチ最強!!(いいえ) このころのプログラムをビジュアライズすると、ビームサーチから焼きなましするときに、点は全部変わることにはなってなかったので、作戦通りにいっていた。

11/19 20:11 158978点　ビームサーチの手をソートするのがボトルネックだったため、高速化した。ついでに時間を9.8秒にした。頂点を置く順番を 01,02,03,04,29,30,31
05,06,07,08,32,33,34
09,10,11,12,35,36,37
13,14,15,16,38,39,40
17,18,19,20,41,42
21,22,23,24
25,26,27,28
のように,4個ずつおいた。
さらに、直前に置いた5個が全く同じ盤面は、重複として除去した。

11/20　テストケース生成器を適当に眺めていたら、辺のrandがおかしいことに気が付いて、質問を投げた。 辺の偏りは、焼きなましなら問題はないが、ビームサーチなら重要なことだ。序盤の方にたくさん辺を持つ点が選ばれて、後半はゴミみたいな点が集まるのは、あまりよくないことだからだ。

11/20 17:25 154934 点　たくさん辺を持つ頂点ばかりが最初に選ばれないように、そういう点をたくさん含む盤面の評価値をさげた。 ある頂点について、そこから伸びている辺の重みの合計をもとめておいて、それの合計*ペナルティ定数だけ評価値をさげた。 しかし、肝心のペナルティ係数の決め方がうまくいかなかった。(動的に変更しようとしていた)(現在の使っている頂点の辺の重みの合計と、平均の辺の重みの合計を比較して、あれこれしていたが、頂点を端の方から決めるために、それではダメだった)

1週間ぐらい、マラソンに飽きていた。 最終日　??????点(pretestの点数が残ってない) 結局ペナルティ係数を動的にするのはあきらめて、ExcelでVとE/Vのいろいろな値に対して実験して決めた。 systest 736571点,29位で終了した。 考察メモ落書きです。