Hatena::Grouptopcoder

横道にそれるTopCoder参加記録でもいいじゃないか

 | 

2018-04-27

MM100 SameColorPairs 参加記録

09:13 | MM100 SameColorPairs 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - MM100 SameColorPairs 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか

わりと順位が良かったので長くなる。


・greedyの前に、ちょっとだけ考察を…

土曜日。開封の儀式的にサンプルコードをvisualizerにかけてみる。それからサンプルコードにちょっとだけ手を入れてスコア計算式を確認。visualizerも読んでみると、同じ色のセルの個数が偶数になるように調整されている。

まずは消せるペアを見つけて消すgreedyを実装すべきだと考えたが、そのまえに考察したくなってペンとノートを取り出す。

今回の問題はグラフで考えやすそうだ。いつも二次元グリッドであることを忘れてグラフとして解けないか考えてしまう。そうしたら範囲外参照の問題とおさらばできる。

しかし今回も矩形領域を扱うので、完全に二次元グリッドを忘れることはできなそうだ。(x, yで操作する必要がでてくる)

依存関係が閉路になってると消せないなと絵を書いてみるものの、ノードを足したり引いたりしたとき、閉路検出を高速にできるデータ構造なんて知らない。


・greedyでルールの確認

考察を続けたいが我慢して、消せるペアを見つけて消すgreedyを実装した。visualizerにかけ、ルールの認識に間違いがないことを確認する。

ここで意外と消えてることに気づく。

これは前半はどう進めても問題ないやつかもしれない。

提出 4/21 10:34 471,408点 85th ローカルテストの絶対スコア0.9531


・データ構造を決める

トポロジカルソート的に解きたかったので、参照カウント(そのセルが消えていることに依存する操作の回数)を用意した。

するとこの参照カウントには任意の順番でunmoveしても性質が維持されるという好ましい性質があることがわかって嬉しくなった。

これでiとj-kをi-jとkというペアに変更する操作が可能になった。

提出 4/21 17:31 760,923点 42nd ローカルテストの絶対スコア0.9870


・ダミーをまく

ここからどうするかだが、とりあえず状態遷移がスムーズになるようダミーをまくのが良かろうということで、作ったペアを解消する操作を取り入れる。

提出 4/22 09:35 836,207点 17th ローカルテストの絶対スコア0.99707

ここで明らかに点数が良くなっているのに、greedyに4/100も負けているのに気づく。greedyはパーフェクトを取っていた。

これはパーフェクトを取らなくてはならないゲームなのでは?


中間状態をビジュアライズ

いままで面倒がってビジュアライザは与えられたものをそのまま使うことがほとんどだったが、Pillowというpythonのライブラリで動画gifを作ってみることにした。

意外とすぐ動いたが、どうもライブラリ選択は間違えたようだ。(フレームレートをあまり速くできない)

これでダミーの分量を目視で確認できるようになった。

そして提出したらびっくりの2位。

提出 4/22 13:43 871,086点 2nd ローカルテストの絶対スコア0.99598


・無駄骨だった高速化

操作可能か調べるためのデータ構造を半日かけて作るものの、全く速くならず。

唯一成果があったのが、ローカルテストを早くするための工夫。

パーフェクトになったら処理を中断するようにしたことと、ビジュアライザのデータ作成結果を保存してビジュアライザなしで評価するようにしたこと。(しかしこのせいで無効な解答をチェックできず投げつけて0点を取ってしまった)


・つらいチューニング

評価関数をためしたり、変化が起きやすくなるよう操作手順を工夫してみるものの、効果は上がらず。

結局効果があったのは、時間係数の変化をスムーズにした(それまで一画面操作するごとにだけ更新していた)ことと、ダミーをまく確率を調整したことくらい。

しかしローカルのテストではパーフェクト率が約95%から約97%に向上したので大きな違い。

制限時間を2秒→9秒にするとパーフェクト率は99.1%になったので、高速化できれば改善する余地はまだありそうだった。

それだけに、分割解法はなるほど!と大きな衝撃をうけた。分割すると問題が解きにくくなると考えて、無意識に棄却していたのでしょう。

 |