phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

TCO18 MM R2 CrystalLighting

概要

レートのわりに順位がよくて、目標の1つの「1pt以上ゲット(できればTシャツ)」を達成できた:D

最終順位は41位(127人参加)でした。

問題

http://www.topcoder.com/contest/problem/CrystalLighting/1.png

HxWのセル上にクリスタルまたは障害物が置かれており、各クリスタルには、光らせたい色(原色:青/黄/赤、二次色:緑/紫/橙の6色)が与えられる。
今、空のセルに以下のオブジェクトを置くことができる

  • 上下左右にビームが伸びるライト(色は原色の青、黄、赤の3色のみ)
  • ビームを反射するミラー(ただし、斜めに置き、ビームを90度回転させる)
  • 障害物

二次色クリスタルを光らせるには、2種類のライトのビームで光らされていなければいけない。
スコアを、「(光っているクリスタルについて、色が、正しく原色で光っている場合+20、正しく二次色で光っている場合+30、違う色で光っている場合-10としたときの合計値) - (各オブジェクトを置くコスト)」としたとき、これを最大化せよ。

最終的に提出したアプローチ

  • 焼きなまし
  • 近傍は、ランダムにセルを選んで、それが空マスなら「85%でライトを置く、5%ずつでミラーまたは障害物を置く」、オブジェクトを置いているマスなら「4近傍1マスに移動」または「そのオブジェクトを消す」
  • 評価関数は、前半を二次色が1色には当たっている場合-3にしたもの、後半はスコア通り
  • あるマスの4近傍を探索する部分は、探索も更新もO(N)だけど、ちょっとだけキャッシュに残すようにしてみた
  • 初期値として、二次色のクリスタルだったらその1マスとなりの4近傍にライトおけたらおいておいたもの、にしておいた

振り返り

今回は方針とか方向性は良かった感じで、1週間の割にはいろいろ入れられた気もする。

方針

単純にスコア計算の差分ができそうなので、焼きなましは有効そうということで、ここのところまでの焼きなましの反省を活かそうと焼きなまし方針にした。
直前にやってたyukicoderマラソンで「変化量の小さい近傍が作れれば、探索空間がなめらかになって探索しやすい」ということを見ていたので、そこら辺を意識。

近傍

最初は単純に「置く」「取り除く」でやっていたけど、これだと「スコア高い→低い→高い」みたいな感じで滑らかじゃないので、それ以外を考えた。
「クリスタルを照らすライトの位置や色をシャッフルする」とか「近くにランダムに移動」とか試してみたけど、初期実装だとスコアがあまり上がらず、結局「隣接4マスどれかに移動」だけを追加した。

高速化

重いところは「あるマスposの方向kに進んだときにぶつかるマスの位置」を求めるところで、最初、set使ってO(logN)な探索がいいかなと思って書いてみたけど、単純にマスをたどるO(N)な方が速くて、O(1)はバグりそうだったので後回しにしてたら結局最後まで手を付けられなかった。
同じマスに結構アクセスしがちなのでキャッシュ的なモノを用意してみたけど付け焼き刃ぐらいだった。

二次色の「0→-10→30」の不連続性

二次色の30点はおいしいのでできるだけおさえておきたかったので、いくつか工夫を考えて入れた。


近傍として「2つ同時置き」とか試してみたけど、試したときはあまりスコア的な効果が見られなかった。。。
回転数が少なかったので、初期状態として「30点をおさえられるならその4近傍にライトを先に置く」をいれておいた。
最初の方は二次色の1色ライトで光っている場合-10点なのを緩和するために、時間の前半分の時はスコアを-3点ぐらいにして、後ろ半分は通常スコアで計算した。

Round1の反省

TCO18 MM R1 RoadsAndJunctions - phyllo’s algorithm note
Round1の反省で、「コードの書き方や管理方法」を工夫する予定だったけど、結局雑に書きすぎてしまった。
インクリメンタルに実装を追加したり消したりするせいで、どんどん継ぎ接ぎになるし、めんどくさがって関数を長くして書き直すつもりをそのままにしたりとひどかった。。。
高速化も、十分できていなかった。
可視化も、結局なにも行わず、公式Testerだけだった。(焼きなましのデバッグに文字列で出力はしたぐらい)

引き続き反省orz。

反省

フォーラムや感想戦見てて得られるものが多かったのでまとめとく。

TCO18 MM R2 - Togetter
TopCoderでプログラムしてみた 第2394回 (TCO 18 Marathon Match Round 2 直後放送) - YouTube
TopCoder Forums

近傍

「ライトの移動」のところは、「ビームライン上に移動」が無駄なく変化量が小さい良い近傍だったもよう。



採用してた「ライトの1マス移動」は一応変化量を小さい移動を含んでいたけど、不十分だったかも。
また、ビームライン上にランダム移動ではなく、探索して一番いい位置に移動、とか近傍の候補にすら入れられてなかった、、、


ここらへん、適当に近傍案を考えてみて変化量の小さそうなものを使う、としてしまったけど、考察から導出できるようにしたい。

高速化

焼きなましのループ回数は1000万ぐらいを目標にしてたけど、上位陣は1億回ぐらい回っていたらしく、文字通り桁が違ってた。


高速化で重要そうだったのは、診断人さんの放送で議論されている、

  • 4近傍の探索をO(1)にする (更新はO(N)でもよい)
  • 焼きなましの更新の仕方を「状態更新→スコア計算→悪化なら状態戻す」ではなく「スコア計算→良化なら状態更新」にする

ところだった模様。


「4近傍の探索O(1)」は、考えてたけどバグりそうで後回しにして結局手を付けられなかった。
けど、ミラーを考慮した厳密なO(1)ではなく、なんかのオブジェクトにぶつかる位置を保持して、ミラーなら何回かたどる「ほぼO(1)」で十分だったよう(ミラーを含むビームの数が少ないため)。


「焼きなましの更新の仕方」は、これまで「状態更新→スコア計算→悪化なら状態戻す」しか書いていなかったので、その先の「スコア計算→良化なら状態更新」があるのは初知見だった。(受理率が悪い場合、ほとんどが悪化して状態を戻す操作をしてしまうので、効果的)

評価関数の変化

二次色の1色だけ光っている場合について、そのまま計算すると「0→-10→+30」となって谷を超えないといけない。
自分は「スコア」を保持して差分を計算してしまっていたため、1色だけ光っているときの悪化を徐々に変化させる方法がうまく取り込めなかった。
ただ、これは簡単に修正できそうで、「スコア」ではなく「クリスタルの状態ごとの個数」を保持してスコア計算を都度行えば、そんなに計算時間かけずに再計算できそうだった。(期間中はこれに気づけず、前半後半にわけるしか思いつかなかった)

その他の工夫
  • 最上位陣は、マス全体の焼きなましの他に、小さいエリアの焼きなましを行っていたらしい
    • 小さいエリアの焼きなましの場合は、改善するものだけ保持し続けることがキモ?
    • 回転数を稼げたり、キャッシュフレンドリに行えたりもする
    • 細かい部分での改善が多かったので、小さいエリアで考えるのがよかったよう
  • 小さいときの多点スタート
    • 試したけど回転数が足りておらず、あまり改善が見られなかったので不採用してたけど、最終結果見ると小さいケースでも探索しきれてなさそうなスコアだったので、ちゃんと検証すべきだったかも
  • ビジュアライザの仕方工夫
    • 焼きなましのデバッグが辛かったので簡易にできるもの用意しておきたい
  • パラメータチューニング工夫
  • 評価関数のなだらかな変化