daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

mm100にっき

問題のリンク↓
TopCoder


とりあえず問題を見る。
これは厄介そうだな〜〜というのが第一印象。
特に斜め方向であっても矩形領域に別の色が挟まっていなければそれを取り除けるというのが一番厄介でここをどう処理するかがポイントになる気がする。
この処理の計算に時間を使いそうなので毎回は斜めを考慮することは出来ないだろう。これの計算のオーダーを下げるいい方法がないか考えてみるがあまりいい方法は思いつかない。
とりあえずナイーブな方法を取ればいいかと開き直ることにした。

マスの取り除き方は結構いろいろあるので焼きなまし的なことが出来ないかを考える。
しかしmove列のどこかを別のmoveに差し替えると次のmoveに影響が出てしまうため単純には出来ない。
探索を考える。しかし最終状態まで探索をしないと行けないのは結構きつそうなのでボツ。
典型には落とし込めなさそうだなぁと思う。

とりあえず方眼ノートと色鉛筆を用意する。実際に手を動かしてよさ気なアルゴリズムを探そう。

いくつか思いついた方法で手を動かしてみる
手を動かしていると
違う色のタイルが密集しているとそれを取り除くのはかなり大変になる。
あと真ん中のあたりのタイルは矩形領域を作るときに邪魔になりやすい。端っこは邪魔になりにくい。
という知見が得られた。
そして思いついた方法の中で一番よさげだったのは「一つの色について取り除けるところを全部取り除いてから次の色に移る」という方法だった。
そしてこれをどのように実装していくか考える。
とりあえず最初は斜めを考えずに、右上のますから上下左右で取り除けるマスを列挙していき、ランダムにマスを取り除いていくことにする。
そして斜めを考えずに取り除けるマスがなくなってしまった時斜めに取り除けるマスをすべて取り除く、そしたらもう一度上下左右で取り除けるマスを列挙していき取り除いていくことにした。
これが完全に取り除けるマスがなくなるまで繰り返す。

この一連の操作にどれだけの時間がかかるかと思ったがH,Wが小さいケースではそんなに時間がかからなかったのでこれを何回か繰り返してベストとなるmove列を見つける。
ここでmove列の評価はどれだけマスを取り除けたかで評価するが、どれだけmove列が長いかを見ればそれがわかるので全マスループを回さなくてもSZ(move)で済む。
これがちゃんと提出したののうちの第一投目。

ここで焼きなまし的なことを思いつく10s中最初の5sはランダムに探して次の5sは今のところの最善のmove列の前半n個を取り出して来てその続きをランダムに決める。
これを最初のランダムに施行する時間を調整しながら試してみたところ最初の1回だけランダムで後は最善から作ったほうがスコアが良くなったのでこれを提出。
seed 3がTLEするようになって非常に苦しんだがとりあえずスコアは伸びた。

ここでH,Wが小さいケースでは1iterationにそんなに時間がかからなかったとあるが、
むしろ逆にH,Wが大きいケースまたは斜めをたくさん考えないと行けないケースではiterationの時間が非常に大きく数回しかiterationを回せていないということがザラだったのをなんとかしたい。
またこれとは別に最善のmove列から前半n個を取り出すところにおいてどれぐらいのnを取れば効率的なのか知りたいということが出てきたので、
nを適当に変えてみてその時のmove列の長さをプロットしてみる。
H,Wが小さい時はnが小さい時もスコアがコロコロ変わるがnが大きいとスコアが変わるのはnがかなり大きい時だということに気がついた。
まあnが大きいと後半をちょろっと変えるだけなのでもともとの長さがそこまで変わらないのでそれはそうだ。
後半をちょろっと変えるだけならH,Wが大きくてiterationに時間がかかる時でも大した時間をかけずに更新できる。
f:id:daruma3940:20180426214557p:plain
これでが第3投目。

nを適当に変えるところで最初はnを小さくとり、前のほうから変化させ、だんだん前のほうを固定する方法を考えるが
さっき取ったデータからこれはあんまり意味がないかと考える。

今完全ランダムにしてるところをもうちょっとまともにしたい。
違う色のタイルが密集しているとそれを取り除くのはかなり大変になる。
あと真ん中のあたりのタイルは矩形領域を作るときに邪魔になりやすい。端っこは邪魔になりにくい。
これを優先的に取り除くためにマスのペアにスコアをつけてそのようなマスを優先して取り除くことにする。
しかし全然ダメ。この方法には可能性を感じていたというかこれはスコアが上がらないとおかしいと思ったので結構いろいろ試したのだがスコアは全然伸びないむしろ下がっている。
まあ一回失敗してしまってもアイディアをもう一歩深化させることを考え続けるがスコアは全く伸びず下がる一方である。

ここで蟻本を読んでみてアイディアが降ってくるのを待つ。するとマッチング問題を思い出した。
色のペアを作るのをマッチング問題の要領で見つけ出すことは出来ないだろうか???
今回は一般マッチングっぽいので一般マッチングについて調べてみる....簡単には出来なさそうだ...
簡単にはできなさそうだがアイディアは活かせるのではないかと思ってアイディアを盗むため一般マッチングについてのスライドを読んでみるがどう生かせばいいのかさっぱりわからないし
内容もさっぱりなのであきらめる。
こういうのに嵌ってしまうと良くない。
できることをするしかない。

しかし前回はそんなの出来ないだろと最初に諦めてしまった方法を他の人は使っていて、出来なさそうに見えても考えることは大事かもしれないが....

出てくるアイディアがどんどん雑になってくる。
全く根拠のない「これでうまく行くはずだ!」が増えてきて根拠がないにもかかわらず失敗したら落ち込んでいる。
もっと1日目のような丁寧な考察をしないといけない。
5分後に私は天才になってるはずだと思いながら根気よく取り組む。

イデアを出して褒めまくるフェーズと
イデアの実装方法を考えるフェーズと
イデアを否定するフェーズに意識的に分けているのは前回の反省から。

またアイディアがうまく行かなくてもそれをもう一歩深化させることを心がけているのも前回の反省から。
順位表,Twitterを見るのを意識的に遠ざけて余計な煽りを受けないようにする。戦っているのはその人たちとではなく自分となのだから。(これも前回の反省から)

わりとしについて考える。
わりとしというと割と死にたいのことだと思うかもしれないがこれは罠で
虚無と交わり歳を取りたい
わりとC言語好きだよ
ひまわりとしんのすけ
くるみ割りと詩人
のどれかのことだ(いいえ)

ここで情報を詳しく書き出すことにする。
そうするとiteraionが大きく下がっていることに気がつく。
う〜〜んやはりどれだけiterationを回せるかのゲームなのか....?????
しかしCOM将でも強くなる時は遅くなる時ということばがあるように(meromさんがそう言っていただけのことをコンピューター将棋界にそういう言葉があるように言うのは主語を広げすぎ)
iterationが低くなっても強くなる方法はあるはずで他の人はそれに気がつけていると思うんだが.....
まあ2コマ関係から3コマ関係に変えた途端弱くなるソフトの作成者なのでこのあたり本当に苦手だ....
とりあえず速度を落とさず良くなるのではないかという方針として今は山登り的に命令列を計算しているので焼きなまし的にしてみる。しかしうまく行かない。
ちょっとパラメーターをいじってると以前と同程度(ちょっと低い)のスコアが出るプログラムが出来た。
これを提出する。思いっきり下がった。泣きそう。わりとし。
ナナメを最後に考えてるのがよくないのかもしれない。
色のついたマスが少なくなってきたらナナメも同時に考えるようにしたが結局iterationが下がってスコアは伸びない。
もう高速化して細かいスコアを手に入れるしかないのではと思い、とりあえずメルセンヌ・ツイスタを使っていたところをxor128で書き換える。
するとseed19が思いっきり下がった。ほんとにseed19,14,4が厄介で厄介で仕方ない。
というか擬似乱数生成器をちょっと変えただけで爆下がりしてるんだからこれほんと今のスコアoverfittingでしかないでしょ。
笑うしかない。システムテストで大幅下落する未来しか見えない死死s死
精も根も尽きた。まだ精は尽きていないのではないかと思ってとりあえず致そうとしてみるが駄目だった。精も尽きていた。



ーーーーー感想戦ーーーーー
工事中....
疲れていて他の人の方法を読む気力が残っていない....
疲れがひどいが無理矢理読んでいく。

hakomof.hatenablog.com
終了後焼き鈍しを使ったというツイートを見てもどのようにして焼き鈍したのかさっぱりわからんかったがこれを読んだらわかった。
すごいなこれ。

解となる操作列をそのまま焼き鈍したのでは順序関係が壊れてしまって焼なませない。
そこで消すペアと消す順番を分けて考える。
とりあえずこのマスとこのマスを消したい!というペアを消せるか消せないかにかかわらず作っておいて
この消すペアの集合を焼きなましの状態として、スコアはペアを貪欲をして消していった時にどれだけペアを消せるかになる。なるほど。
焼き鈍し方はよくわかったけどいかんせんアルゴのちからがないので依存グラフやトポロジカルソート、バイナリ空間分割の話はわからなかった。

github.com

SAT充足可能性問題。そんなのがあるんですか。
こちらも有効性判定述語とかよくわからないので途中で読むの投げてしまった。

そうか「消えにくいセルの性質はこうだ!」みたいな感じで優先条件を考えてたけど何回も試せるんだから試してみることでもっといい消えにくいセルの情報が手に入るのか。


知識不足なのでわからんがそういうデータ構造があるんですか。

TopCoder Forums
bestmove列以外のmove列もpoolに保持しておく方法ですか。
これMM97の時にやったことがあって、その時にスコアがちょっと伸びたんだけど結局ほかの人がしていた多点焼きなましに比べて弱かったのであんまりよくないと思ってしまっていた。
やはり問題によってあんまりよくなかった方法が有効になったりする感じですかね。

う~~ん
今回は失敗してもその失敗から知見を得て次の方針を得るということが出来なかったように思う。
次はそれを心掛けていこうな。
あとマラソンのシステムとかビジュアライザとかを整えていきたい感が強い。