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行とかになったので、今まで参加したＭＭの中で一番実装重かったかもしれない。
最初に思いついたことをコンテスト中に消化できなかった。コンテスト開始直後の自分に、実装する前に紙に書いて整理することと、めんどくさがらず考えたことを試すことをアドバイスしたい。
