MM119参加記

MM119に参加しました。

他の人と方針が違うようなので書きます。

URL

https://www.topcoder.com/challenges/30134026

問題概要

グリッド上にR台ロボットがある。各ロボットにはそれぞれT個のtargetマスが存在する。各ロボットごとにすべてのtargetを最低一回ずつ通るような最短パスを計算した時の総長を最大化するように壁マスを配置せよ

考えたこと

残り二日での参加だったので、実装が楽で失敗しなさそうな方法を選ぶように考えた。最初は単純にSAを考えたが、スコア計算が重いので回数が稼げるかわからないし、良い近傍を見つけるのが難しいと思った。やってみてダメだった時に再実装する時間があるかもわからないし、他の方法を考えた。実際のところSAでやってる人は多く、別にSAでもよかったっぽい。

実装が簡単な構築をパラメタライズして山登りするやつをやった。

dfs

開始targetと各マスの優先度を設定する。開始targetを起点にdfsする。

dfsで通ったところは白で塗る。白マスの連結成分はunion findで管理する。新しい白マスができるたびに、各隣接マスに対しそのマスを白マスにしたときサイクルができるなら黒で塗る、という操作を行う。サイクルの判定はUFを使って高速にできる（連結成分に含まれるtargetの集合をビットマスクで持って、隣接白マスのマスクがdistinctかを調べればよい）。隣接マスの未確定マスのうち、優先度の高いマスを選んで進む。

スコア計算

愚直にやるとそこそこ時間がかかるが、木とみなすことでTSPを線形時間で解くことが出来る。（全域木中の辺の数×２- startからtargetまでの最長距離）

山登り

dfsにおいて、開始targetとマスの優先度がパラメータとなっている。

開始targetは後述する多スタートに任せるとして、優先度を探索する。近傍は適当なサイズのサブグリッドを取って、その中でswapを数回行うことで生成する。

優先度の初期値は任意の順列から一様ランダムとした。外側の優先度を高くしたほうが最初は良い解は得やすいのだが、山登りを繰り返したときより良い解にたどり着くのは一様ランダムだった。この逆転はTLを9秒として初めて判明した。

多スタート

山登りを複数行う。開始targetはこの時点でランダムに決める。並列に探索させて、successive halvingで枝刈りを行う。最初128個持っておき、3のべき乗ステップ終わるごとに下位半分を消す。

考察

この解法はマスの塗り方を直接探索するわけではないので、全域性が欠けており、偏った領域を探索しているといえる。そのため小さいケースでも最適解を見落としがちだと思われる（実際seed1でも最適解は出ない）。この問題は探索空間に対して探索数が少ないので、そもそも最適解を狙いに行くようなタイプではないのでなんとかなってる。

seed=2, Score=7495

探索の結果を見るとわかるように、ほぼ全体で一つのパスとなるような解が出力されている。ほんとはstartから各targetまでが等距離になっているのが理想なのだが、アルゴリズム上仕方ない。
このままハイパラ調整をすれば1位は狙えそうだが、偏った領域を探索しているなどの理由から究極的に強い解法でもないと思っている。

感想

ここ最近の問題の中でも特に面白い問題だったと思う。問題設定に無理がなく、いろんな強い解法があったと思う。

今回は時間がなかったのでそんなに深いところまで考察はできず、多スタートとか外側の部分を使ってごり押したという感じ。暫定4位は解法ガチャ引き当てた感がある

MM118 参加ログ

MM118（5/21~5/28）の参加記ログです。

思ったことを書きなぐっただけでまとまってないです

5/22

問題文を読んだ。

ダンサーが何人かいると言っているが区間ごとに分けて考えれば良さそう。つまり「始点・終点・最大ステップ数のタプルが複数与えられる」という問題設定と考えて基本的にはいいはず。

衝突とかも考えなくて良いので探索しやすい性質をしている反面、目的が連結成分数の最小化なのでつらくもある。

グリッド上のパス上の最適化は"UL"<->"LU"とか"LR"<->""とかを遷移とする探索をするのが一般的だと思うし今回もそれでいいのではと思っている。というか他に思い付かん。

連結成分に関する計算が重くなりそうだけどそれなりに回数回るでしょと思っている。ダイコネとか使えるけどさすがこういうのは愚直が速いんじゃないかな

隣り合う同色の数を最大化する焼きなましであれば高速に回るはずだしそっちで初期解作ってという感じかな

この手の遷移の問題点として状態から状態への距離が遠くなりがちというのがあるのでそこに気を付けて探索を設計していくことになりそう

パスを丸ごと変えるという遷移もなくはないけど今回は無理そう

とりあえず、パスを局所的に変える遷移で①真の目的関数と②隣り合う同色最大化の二つを組む。

5/23

 考えてたやつを実装した。思ってた以上に①がうまく回らない。代わりに②はうまくいく。というか②の結果から①に移行すると解が悪くなったまま戻ってこないとかある。

ちなみにダイコネで殴ってる（実装楽だったので）。おそらく愚直の方が速い（少なくともNが小さいケースでは）のであとで実装する。

適当に100ケース回してみた。わりとスコア下界を達成しているケースもそれなりにある。順位表を見ると1位が75、2位が60とかでやばさを感じる。rawScore=1が可能なケースでrawScore=2を出したらそれだけでそのケースの得点は0.5なので、こういうケースがかなり重要になってくる。

出力をみると、真ん中の方にでかい連結成分があって周囲が全く色のそろってない状態になっているケースとかがある。移動の軌跡がマス全体を一様に被覆するようにできると良いのかもしれない。

下界を達成できるケースは全マスを一色にするのを目的関数に入れるのもありかもしれない。

f0 = (D*S)/(N*N*C)が問題の難易度の指標の一つになりそう（各マスで平均何順するか。大きいほど簡単）。ハイパラ調整に使えるかも

全マス一色にする焼きなましを書いた。f0>5のケースで使えそう？ただしほんの数パーセントの違い。->   f0>3でも使えそう

初期化を考える。外側が探索されないがちなので、外側に近いところを通るようにするパターンと、遷移の種類を多くとれるようにギザギザに進ませるパターンを用意。f0>1は前者、それ以外は後者という感じにしてみた。

初期化を複数作って初めて気づいたけど、初期解からあまり動けていないようだ（出力からどちらの初期化を使ったかが判別できる程度）。

隣接同色最大化の焼きなましで外側ほどスコアを高くするようにしたりしてみた。数パーセント改善する程度

Cが偶数でscore=1を狙う場合、パリティに注意しないと不可能になるケースがある。どの色にそろえに行くかは事前に決める。

微妙な改善しかできてないので、根本的に探索の方法を考え直さないといけない気がするけどアイディアがない…

一旦現状を纏める。

基本は経路を局所的に変更する遷移で焼きなまし。遷移は具体的に、"LR"<->"", "UL"<->"LU", "LR"<->"RL", "LR"<->"UD", "LUR"<->"U"とこれらを回転、反転したもの。操作列は双方向連結リストで持つ。遷移可能な箇所は追加削除ランダム取得がO(1)のsetで管理する。

目的関数として、1.真のスコア、2.隣接同色数最大化、3.特定の一色に染める　の3つを用意。score=1が狙えるくらいであれば3を、そうでなければ2で探索し、最後に1で探索する。

5/24

時間取れず

5/25

ちょっとだけやる。

とりあえずダイコネの部分を愚直に書き直した。速くなった。

いくつか実装案はあるが方向性を定めるためいったんTL3秒にして提出

->スコア62で4位、1位のスコアは69。TL9秒にすれば狙える範囲だと思う。とりあえず現状では方針を大きく外してはなさそう。時間もとれなさそうなので、細かい調整に入っていいかも知れない。

とりあえず盤面を一色に染める焼きなましの5回リスタートを組んだ。->1パーセントだけ改善

5/26

時間取れず

5/27

終了が28日午前2時なので実質最終日

時間がないので細かい調整に入る。

温度スケジュールとか焼きなましの種類・初期化の方法の選択基準をちゃんと調整した。放置してたハイパラを適当に調節した。ローカルで10％くらい上がった。

順位表のスコアを見ると、1回目の自分の提出が53に対して1位が75とか。

とりあえず提出->同じタイミングで上位2人が提出してて位置が分からん。おそらく1位まであと10％くらいだと思う。->提出結果3位で1位まで12%とかだった。いずれにせよ1位は無理。

しばらくハイパラ調整してたけどもうこれ以上は上がりそうにない。結局雑に焼きなましを書いて終わるいつものパターンになってしまった…

周りも上がってくるだろうし上位に残れるか険しい

TCO19 Marathon Match Round 1 参加記

TCO19 Marathon Match Round 1に参加しました。

順位表：http://cmap-leaders.topcoder.com/challenges/30092483?reviewTypeId=0d5b13d6-7562-4045-af35-d6a5cf62de31

問題設定

概要

N人の人がいる。人は0からN-1までの整数で番号付けられ、i番目の人の高さはH[i]である。最初、左からi番目にはi番目の人が立っている。この状態から並び順を変える操作をX回行う。このとき、できるだけ移動距離の総和を小さくしつつ、i回目の並び替えの直後に左からj番目に並ぶ人の高さをarrangement[i][j]に近づけたい。

スコアリング

i回目並び替えの直後に左からj番目に並ぶ人の番号をord[i][j]とし、i回目並び替えの直後のj番目の人の位置をpos[i][j]とする(pos[i][ord[i][j]] = j)。distをabs(pos[i][j] - pos[i-1][j])の総和とし、errを(H[ord[i][j]] - arrangement[i][j])^2の総和とするとき、スコアはdist+sqrt(err)と計算される。

テストケース生成

以下の範囲から一様ランダムに選ばれる。

は高さの上限を表す変数。が選ばれた後にが選ばれる。

解法

焼きなましました。

近傍設定

近傍は、「i番目の人とj番目の人の、a回目からb回目までの並び替えでの位置をそれぞれ入れ替える」と設定しました。i回目の並び替えでj番目にいる人が、i回目の並び替え以降でとおる場所のarrangementの合計値をsum[i][j]と書くと、errの更新は、

err +=  2 * (H[i] - H[j]) * (sum[a][pos[a][i]] - sum[b + 1][pos[b+1][i]]);

err +=  2 * (H[j] - H[i]) * (sum[a][pos[a][j]] - sum[b + 1][pos[b+1][j]]);

とO(1)で計算できます。実際に遷移が起きるとき、O(X)かけてsumの値を更新すれば、O(1)でスコア差分が求まり、O(1)で遷移判定を行うことができます。

distに関して、i番目とj番目の人の、「(a-1)回目からa回目」及び「b回目から(b+1)回目」の移動が変化しています。ただし、b=Xの時は「b回目から(b+1)回目」の移動が存在せず、この場合は変化する箇所が少なくなり、特別扱いします。

遷移提案

５０％の確率でb=Xとする。b=Xは状態の変化量が小さく、焼きなましの遷移としてよい性質を持っているといえるので、確率を大きくしておく。

a,iをランダムに選ぶ。a番目の順列の前後でi番目の人の近くにいる人をjの候補とする。候補の中でiから遠い位置にいる人から順に見ていき、遷移が受理される時点でイテレーションを終了する。

温度管理

温度そのものをスケジューリングするのではなく、最良スコアと現在の状態におけるスコアとの比が線形に減衰するように温度を調整するようにした。具体的には、線形に1から0に減る量をrとし、W=1+0.03rとしたときに、(それまでに見つかった最良スコア)×W>(現在のスコア)なら温度を上げ、そうでなければ温度を下げる、とした。

再スタート

時間を４分割してそれぞれで焼きなましを行った。Wの初期値は減衰させるようにした。

感想

久しぶりにまともに参加（といっても３日だけ）できて楽しかった。

COVE VS Reborn 参加記録

ゲームAIコンテスト「CODE VS Reborn」に参加し、予選６位、決勝３位でした。

https://codevs.jp/

決勝提出版アルゴリズム概要

カウンターを狙うため発火点を高めに構えた状態を維持しながら連鎖を延ばす。連鎖の探索はビームサーチ。左から２列目にお邪魔４つと１から９の数字ブロックをそれぞれ落としたとき発生する連鎖数を評価関数に含めた。

１８ターン目まで考える。最初はビーム幅4000くらい。最後の数ターンはビーム幅100くらいまで減らす。こうすることで、早い段階でのつぶしに強くなる。なぜなら、ビーム幅が広いと、「一時的に連鎖数が伸びていないが最終的に連鎖数を最大化できる」ような手を選んでしまい、連鎖数が伸びていないタイミングで相手に発火されるたときカウンターで返せる連鎖を作れなくなってしまうから。ビーム幅をあえて狭めることで、常にそこそこの連鎖数を維持しながら伸ばせるルートを見つける。

１８ターン目に近づいたら、「２ターン先まで全探索、３ターン先からビーム幅１００で５ターン先まで読む」に切り替える。相手が自分に合わせて連鎖をどんどん伸ばしてきたときにも対応できるようにした。

自分の解答にオリジナリティーがあるとしたら、ビーム幅をわざと狭めることでカウンタ―成功率を上げている点だと思う。相手の盤面を見る手を変えるなど、調整に時間がかかりそうなことをせずに決勝に行けたのは良かった。

経緯

最初と最後で５日ずつくらいしか時間がとれなかったので、いかにコスパの良い戦略を取るかが重要でした。最初の５日間で探索部分をほぼ完成させて、最後の５日間で戦略的な部分を頑張るという方針にしました。

残り５日の時点で上位陣の対戦記録を見ると、keraさんが明確なカウンター戦術を成功させており、僕も真似することにしました。すでに作ってある評価関数は、各位置に数字ブロックを落としたときの連鎖数を見ていたのですが、落ちる位置をnつ上にずらすだけでそれなりにカウンターの動作をするようになりました。

この時点で３０位くらいまで落ちていたのですが、上記の変更を加えるだけで一気に１３位あたりまで戻りました。

その後はひたすら自己対戦でパラメータ調整を行い、運よく予選６位に滑り込みました。

時間がなかったこともあり、ビット演算や並列化による高速化、相手の盤面を見て手を変えるなど、実装や調整のコストが大きそうなことには全く手を付けられませんでした。それでも予選通過できたのは、カウンター戦術を取り入れることができたことが多いと思います。

決勝では初撃の連鎖数をみんな大きくしてくるだろうという読みから、より大きな連鎖に対してもカウンターをできるよう、より受け身になりました。それ以外は特に変更してません。

決勝で学んだこと

評価関数にも人ごとに少しずつ差異があって面白かった。評価関数として８近傍に空白があるブロックを消してみたときの連鎖数を見ている人が多かったなか、tanzakuさんはすべてのブロックを消してみたときの連鎖数を見るということをしたらしい。これで一度発火点を埋めてから連鎖を延ばすみたいなパターンを検知できるらしい。また、ケイマ、大ゲイマの位置関係に消滅するブロックの対があるかパターンマッチを評価関数に入れている人が多かったが、keraさんは縦の段差をすべて見ている。

どのように連鎖力を評価するかという点も話に挙がった。僕は時間がなくて自己対戦でしか評価していなかったが、これは良くない。例えばビーム幅を増やすと連鎖力は上がるかもしれないが、カウンター発火の成功率は低くなる。連鎖力は連鎖力として量るべきだろう。ターン数固定でできる連鎖数を評価基準にしている人が多かった。また、y.sさんなどは、ツモを実際の試合からサンプリングしたようだ。公式の記述とは異なる分布から生成されているらしく、割と性能評価に影響があるらしい。

予選でサーバーを借りてやっている人、どうやってクライアントを動かしているんだと思っていたけど、ローカルでクライアントを立ち上げて、実行コマンドのところでsshすればよいというのをnyashikiさんに教わった。言われてみれば当たり前だけど全然気づかなかった。

TCO18 MM Lightning 2 KnightsAndPawns 参加記録

問題文：

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&compid=66697

順位表：

http://community.topcoder.com/longcontest/?module=ViewStandings&rd=17225

大学のテスト・レポートとかぶっていてだいぶつらい

問題概要

H*Wのボードにいくつかのポーンが置かれている。ここにいくつかのナイトを置いていく。このとき、すべてのナイトについて、攻撃できる駒の数がちょうど２でなくてはならない。置くコマ数を最大化せよ。

解法

　とにかく時間がないので実装が簡単でパラメータ調整でゴリおせそうなものを目指しました（パラメータ調整は大学のレポートなどと並行してできるので）。

一般的な考察

・ナイトのattack数が2ということは、attackしているナイト同士を結ぶとパスができて、パスは閉路であるかポーンを端点としていると言えます。

・3つ以上のポーンを攻撃するマスはそもそも考慮に入れる必要がありません。

validと準valid

　validな状態とは、非負スコアが得られる状態、すなわちすべてのナイトのattack数が2である状態です。これに対しすべてのナイトのattack数が2以下である状態を準validと呼ぶことにします。

焼きなまし

僕の解法が全体としてやっていることは焼きなましです。以下に示す状態遷移を繰り返して準validな状態を得た後、validな状態に直すところまでを一遷移として、焼きなましをします。

状態遷移

　状態が準validであるとします。基本的な考え方は、「新たにナイトを置いていきたいが、準validな状態を保持したい」です。

　attack数が1であるナイトを一つ選び、その近傍にナイトを一つ置きます。選んだナイトをA、Ａの近傍に置いたナイトをB、さらにＢの近傍にあってAでないもの（ナイトorポーン）をCとします。ＡとＢを設定すると、

1. そもそもＣが存在しない。
2. Ｃとして考えられるものがちょうど1つ存在する。
3. Ｃとして考えられるものが2つ以上存在する。

のどれかが成り立ちます。

　1の場合は簡単で、Aのattack数が2、Bのattack数が1、それ以外は影響なしなので準validな状態は保たれています。

　2の場合は、Aのattack数=2、Bのattack数=2、Cのattack数+=1、となります。Cのattack数が1増えるということは、attack数が3になる可能性があります。その場合、Ｃがナイトであれば準validでなくなってしまいます。そこでＣの近傍であってBでないもの2つのうち一つを消します。もし両方ともポーンであるならば、Ｃを消してしまいます。

 　3の場合は、そもそもBの候補として除外しておくことにします。　

　以上の挙動は、以下のように説明できます。

・ナイトが作るパスの端を伸ばしていって、ほかのパスにぶつかったらそのパスを切って切り口につなぐ。ほかのパスの端点とぶつかったら2つのパスをつないで一つのパスになる。

　この操作において、ナイトの数が減ることはありません。

　そもそもＡの候補がない場合ですが、適当な空きマスを選んでナイトを置き、上述の2の場合と同様な処理を施すことで、状態を変化させることができます。

準validからvalidを得る

準validな状態からattack数が1以下のものを消していくと、最終的にvalidになります。これは不完全なパスをすべて消すことに対応し、得られたvalidな状態は、消す順番などに依らず準validな状態に対して一意に定まります。

焼きなましの一遷移

焼きなましの一遷移は、「準valid保持の状態遷移を20回程度繰り返したのち、上述した方法でvalid解を得る」です。遷移回数は100万回ほどになりました。

細かい工夫

大学レポートと並行しながらやっていた関係で、なんでうまくいくか考察できていない部分が工夫点のほとんどになってしまいました。すべて挙げるときりがないので一部だけ書きます。

・一定期間ベストを更新しないときロールバック処理を行いました。ロールバック直後、ランダムなナイトの消去操作を何回か行いました。また、ロールバック直後の状態遷移の回数をマスの大きさぐらいまで増やしました。

・状態遷移において、低確率でattack数１のナイトを消去するようにしました。

example test

Example scores:
0) 15.0
1) 1335.0
2) 3457.0
3) 1426.0
4) 2001.0
5) 173.0
6) 1389.0
7) 258.0
8) 230.0
9) 1528.0

seed2

TCO18 MM R3 InvestmentAdvice 参加記録

問題文：

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17203&compid=65421

順位表：

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17203

最終日のみの参加になってしまった

問題内容

概要

Ｎ個のファンドがあり、それぞれ異なるexpertにより運用されている。毎round、各expertは次roundまでにリターン可能であると予測される利益の投資額に対する比を提示する。どれにいくら投資するかを決めて、利益を最大化せよ。

制約、条件

1roundで1つのexpertに投資できる額の上限は400000である。また、投資額の合計が所持金額を超えてはならない。これらの条件を満たせば、投資額は毎roundごと自由に決められる。投資したお金は必ず次のroundには清算される。利益は、各ファンドごとに投資額×真の利益比（小数点以下切り下げ）によって計算される。この値は次のroundにおいて知ることができる。

・最初から持ってるお金=1000000

・ファンド数 N=nextInt(10,50)

・全round数 R=nextInt(10,100)

・各ファンドの真の利益の比=平均0、標準偏差0.1の正規分布に従う。

・expertの提示する値：

確率Ａで平均が真の利益、標準偏差Sの正規分布に従う。

確率1-Aで平均0、標準偏差0.1の正規分布に従う。

ここでA,Sはexpertごとに持つパラメータで、

A=nextDouble()

S=nextDouble()*0.2

として決定される。これはroundごとに変化しない。

やったこと

平均a、標準偏差s、の正規分布の確率密度関数をf(x,a,s)と書くことにします。

基本方針

まず、毎roundの利益の期待値を最大化するには、各ファンドごとに利益率の期待値を求め、大きいところから順に、期待値が正である間、また所持金が残っている間、上限額（400000）ずつ投資していけばよいです。

もし全く投資しない場合、そのファンドの真の利益率についての情報が得られません。よって、情報を得るために期待値が低いところに投資することも考える必要があります。情報を得たいファンドについては一定の額を投資することとし、それ以外についてはそのroundの利益の期待値を最大化することを考えることにします。

期待値の計算

ベイズの定理とかで確率計算します。以降一つのファンドに注目して考えることにします。

あるroundにおいて、真の利益率がactual、提示された値がreportであったとします。

expertのパラメータの確率分布は、

p(A,S | actual,report) ∝ p(A,S)×p(report | actual,A,S)×p(actual | A,S)

です。p(report | actual,A,S)は、問題の制約において、真の値から提示する値を決定する部分がそのまま使えます。

p(actual | A,S)はそもそもA,Sに依らないので無くて良いです。したがって、

p(A,S | actual,report) ∝ p(A,S)×{A×f(report,actual,S)+(1-A)×f(report,0,0.1)}

投資したファンドについては前roundのactualの情報が分かるので、これを用いて確率計算します。投資しなかったファンドについては、

p(A,S | report) ∝ p(A,S)×p(report | A,S)

=p(A,S)×{A×f(report,0,sqrt(0.01 + S*S))+(1-A)×f(report,0,0.1)}と計算できると思いましたが、やるとスコアが悪くなるのでやってません。なんで

続いて、利益の期待値を計算します。さっきまでのactual,reportは直前roundの情報でしたが、これからは現roundのactual,reportです。actualに関しては予測値ですので、区別するためにXと書きます。

p(X | report) ∝ p(report | X)×p(X)

=∬p(report | X,A,S)×p(X,A,S) dAdS

=p(X)×∬p(report | X,A,S) dAdS

=f(X,0,0.1)×∬{A×f(report,X,S)+(1-A)×f(report,0,0.1)}dAdS

後は期待値ですが、

∫X×p(X | report)dXを計算すればよいです。

これらの計算は解析的にはできそうにありません。A,S,予測actualに関して標本化して計算しました。

情報を得るための投資

投資した回数が一定回数以下のexpertには、必ず40だけ投資するようにしました。この値は大きすぎるとそのroundに得られる利益の期待値が低くなる損が大きくなり、小さすぎると得られる情報の正確さが落ちます。

「一定回数」の決め方ですが、全ファンド数と全round数のみに依るものとして考えました。あらかじめいくつかの｛全ファンド数、全round数｝に対して「一定回数」として最善の値を求めておき、間の値は補完することでテストケースごとの「一定回数」を求めました。

この辺は改善の余地が大いにあると思うのですが、時間がなくてやってません。

TCO18 MM R2 CrystalLighting 参加記録

問題文：

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17179&compid=64279

 順位表：

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17179

 provisional8位でした。

記事にするようなことをしていないので一般的な話も含めて書きます。

やったこと

焼きなまし。

近傍

遷移は各アイテムを置くor消す、ランタンを自分の発する光が通るマスへ移動。

焼きなましの近傍の選び方の基本は、高速に動作すること、解空間が滑らかになること（遷移によるスコアの変化量が小さい、任意の状態から別の状態への遷移回数が少ない）。そもそも焼きなましが有用かはそういう近傍が存在するかで判断できると思う。

各アイテムを置くor消すは自然で思いつきやすい。移動が有用なことも焼きなましに慣れていれば割と思いつくと思う。光線に沿った移動は、基本的に変化が４方向（２光線の削除＋２光線の追加）になるので、設置、削除の近傍に劣る理由がほぼない。

評価関数

各アイテムのコストを０から真値に線形に変化させた。

一般に、焼きなましの評価値が真のスコアであるという保証はない。だから、設計の最初の段階でそれを意識した方が良い。意識しないと、「真のスコアで焼きなましてベストスコアを保持してロールバックしたりする」みたいな工夫をした後で、真のスコアでない値で焼きなましをしようと思った時に無駄に実装コストがかかるようになってしまう。

僕はこれが原因で、上位陣がやっていた、２色のうち一方のみで照らされるクリスタルのコストを変化させるということを試さなかった。正確には、試したけどスコアが改善しないと勘違いした。試したとき、実装上の都合でイテレーション回数の増加という副作用が起きていて、スコアが改善しなかった。この副作用は時間をかけて実装をやり直せば起こらないものだった。

遷移の実装

実装は、各マスを通る光線を愚直に（差分計算はするが）シミュレートするというもの。ランタンが置ける位置のリストなどを保持することができる。遷移回数は6千万程度になった。

反省

遷移の実装に関して、一本の光線が通るマスでグループ化し、各マスからある方向へ行ったらどこでぶつかるかを保持しておけばもっと高速に同じ遷移を達成できた。ランタンが置ける位置のリストを保持などはできないが、アイテムの移動が遷移として有用なので、遷移提案のオーバーヘッドはほとんどなくなると思う。

とりあえずのつもりで愚直な実装をしたら費やせる時間の9割を消費してしまい、これを試す余裕がなかった。最初、実装が思いとは思わなくて両方試せば良いと考えた（やってみるとややこしい要素が多い）。もっと最初に構想を練っておけば良かった。

使わないコードをほとんど書かなかった割に2000行とかになったので、今まで参加したＭＭの中で一番実装重かったかもしれない。

最初に思いついたことをコンテスト中に消化できなかった。コンテスト開始直後の自分に、実装する前に紙に書いて整理することと、めんどくさがらず考えたことを試すことをアドバイスしたい。