TopcoderのMarathonMatch132に参加しました。
問題はBouncingBalls。セル・オートマトンみがある最長路的な問題でした。
結果は提出43人中、暫定14位、システスも14位でした。
問題
グリッド外から直進するボールをB個入れるよ。
"＼"や"／"のパネルを置いて直角に反射させて、ボールが1個でもグリッド外に出るまでの反射回数を多くしてね。ついでにボールを入れる位置も自分で決めてね。
ただし配置が固定のセルもあるよ。
あと自分が置いたパネルは、ボールを反射させると90度回転するよ。（最重要）
考察
なんも分からん。
／＼
／＼
こういう道の間を通すと、
＼／
＼／
こうなる。以後ループ。
ん－、セル・オートマトン？
でも常に間を通せるわけではないし、回転しないパネルがあったり、複数のボールが同時に動き回るので、良型を探すのはかなり苦しそうに見える。ただ、2x2単位で考えるという発想はあり？
2x2は一旦置いといて、始点だけ決めてしまえば、シミュレートしながら未確定セルに着いたら中央側へ打ち返すという挙動ができる。
（ここから下はDFS実装後に気付いたこと）
角を考えたとき、例えば始点が左上の隅に無い場合に左上に"＼"があると、必ず右や下から入り、画面外に弾き出されてしまう。よって固定で"／"となるが、これも一度反射してしまうと"＼"に変化する。角のパネルは一度しか使えないということ。*1内側から順に"内側に跳ね返す力"を消費していく一方で、外側のセルは自身の力で内側に跳ね返しながら、内側の跳ね返す力を回復させていく。*22進数の繰り上がりみたいな感じ？ただこれは菱形に働く力なので、グリッドが矩形と考えるとどこまで有効な考えかは分からない。
ボールを外周から中央に運ぶとき、その経路は後から編集できないウィークポイントになる。実際DFSでも浅い詰みを回避するのを除けば、探索できているのは8層程度か？なので、ボールは中央に運ぶがパネルの状態は臨機応変に後から変えられるという仕組みに出来ると強そう。もしくはルールベースで良い入り方や序盤の指針を埋め込んだり。
実装
とりあえずDFS。
始点をランダムや全走査で決めて、シミュレートしながら未確定セルに着いたらパネルを置いたり置かなかったりする。『内側に弾く＞外側に弾く＞置かない』の優先順とした。*3
これで始点を400パターンで10msずつ回して、上位20件を更に時間いっぱい回した。*4始点の多さ、探索の深さがそれぞれ得点に響くケースがあり、更に10msで上位でないものが後半で伸びるケースもあるため、これをパラメータ調整しようとすると地獄の気配がした。*5
ここで期間的には半分くらいだが、他に出来る事と言えば上手く回る探索順やルール、パラメータなどを探すくらいしか思いつかない。そこで2x2で管理する方法を試してみることにした。
（結果的には上手く行かず、これが最終方針となった）
没実装
結果的には振るわなかったが、調整次第ではまだ可能性があったこと、使い方次第では応用が利くことから解法を晒してみる。
まず、2x2の領域に分断する。奇数の場合、間に1x2、2x1、1x1の領域を作る。
イメージとしてはこんな感じ。
①→②→⑤→④→⑦→⑧→⑤→⑥と移動しているものとする。
また、固定パネルが無い前提で説明する。*6
まずは①の左上から下方向に侵入し、右下から右方向に出る。
パターンとしては、
＼＼
？＼
や
□？
＼□
がありえる。（"□"は空白、"？"は不定。）ただこの時点では決定せず、両方の可能性を残す。
このまま、破綻しないよう各ブロックの入口と出口の情報だけを残していく。
⑤には2回進入しているが、
□□
□／
は1回目は成立するが、2回目は成立しない。*7
／／
／／
ここで⑤の内容は上記パターンに確定する。
こんな感じで、"良い場所に移動させる"と"可能性を保つ"を両立させて探索すれば、普通のDFSなら詰んでいるところを更に粘れるので、同じくらい探索できるならば普通のDFSよりも良い結果が出そう。
しかし問題はあって、例えば②の場所を通過するときに
？？
□＼
と
／＼
／ □
では通過にかかる時間が違う。これで何が困るかというと、複数のボールが同時に動いているので時系列シミュレーションが出来なくなる。そもそも複数のボールが同じブロックに同時に侵入したら？という問題もあり、ほぼB=1専用となる。
あとはシミュレーションに時間がかかるなどの問題もあり、残念ながら1x1DFSより優秀なレベルまで漕ぎつけることはできなかった。
高速化をサボって最低限組み上げた状態でseed=126(N=6, B=1)で1x1DFSの95%程度のスコアにはなったので、調整次第では1x1DFSより良い結果が出そうな気がする。*8
とはいえ今回の問題ではやはり苦しい感じがある。序盤の悪手をリカバリーする手段としてこういう方法もあるよ、くらいの与太話として残しておく。
他の人の解法を見て
ビームサーチやchokudai サーチをしている人が強かった。
DFSだと悪手を打ったまま瀕死で生き繋いでしまうので、そもそも悪手を察知して良い状態を保てる複数手読みの方が優れているということだろうか。
焼き鈍しでも自分より上のスコアは出るっぽい。
パターン埋め込みが強いのは、まぁ、はい。*9セル・オートマトン感の強いパターンだけど、探索は力業っぽい。
感想
何か面白いことが出来そうだけど出来ずにぐぬぬ…となる問題でした。
上位は赤コーダーが固まる一方で中位程度なら色々な解法が通用するようで、問題としてはとても良い問題だったのではと思います。
最近は思考が閉塞しているせいで当たり方針が引けないので、すっきりしたいなぁ。
