TopCoder Marathon Match 137 "StoneSeries"

参加しながら考えたこと試したことの源泉かけ流し。

最終的な方針は まとめ にまとめてあります。

問題概要

www.topcoder.com

N×N のグリッドがある。あなたは以下のルールに従い、空のセルに数が書かれた石を置いていく。

  • 8近傍(縦横斜め)のセルに石が一つも置かれていなければ、1 が書かれた石を置ける。
  • 8近傍のセルに 2 個以上石が置かれていれば、それらの石に書かれている数の和が書かれた石を置ける。ただし、その和を V とすると、V-1 が書かれた石が既にグリッド上のどこかに置かれていなければならない。

グリッド上に配置した石に書かれた数の和を最大化せよ。

1 日目

問題を読む。...めっちゃ面白そうだな!?!?
ここ数日こどげで特定の戦略を実現する if 文ばっかり書いてたから、アプローチの仕方がいろいろありそうな問題をみるとワクワクしちゃう! やるぞ!!!!オイ!!!!

ひとまず貪欲解について考えてみる。
上から順に埋めていくと...多分 V-1 が既に配置済みでないといけない制約から配置できないセルができそうな気がする。
そうなると最終的にはサンプル gif みたいにいろんなところから埋めていく形になるのか?

サンプル gif 見て明らかに損してるな〜と分かるのが、周囲の空きセルが 1 つしかないセルを早めに埋めちゃってるところ。
周囲の空きセルが 1 つなら、そのセルには最後に近傍セルの値 +1 を配置できるので、後回しにした方が得な気がする。
...嘘吐いた!V>1 の場合は 2 個以上近傍セルがないと配置できないんだ。じゃあ何も考えずに 1 を配置で良いね。(追記:そんなことはないよ)

今気付いたけど盤面サイズの最大値 40?でけ〜。ちゃんとやらないと相対スコア極小になって終わりそうだな。
そんで壁の割合は最小 5% か...。めっちゃスッカスカの盤面もあるんだなぁ。う〜ん。
近傍が 8 セルだから、スッカスカだと近傍の和クソデカになって配置するの大変そうだなぁ...。

うお〜〜問題読んでパッと良さげな解法が思いつかないこの感じ、いいですね!楽しいです!!

あっっっテスタにマニュアルモードついてますね!!助かる〜〜〜〜。あ〜〜これ楽し〜〜〜〜〜。

手で遊んでたらこういうのをずっと繋げていけるというのが分かった。

スカスカクソデカ盤面だとこういうのをなが〜く這わせる感じになるのかなぁ?
それとも細かいのをできるだけ敷き詰めていった方が良いのか。う〜〜〜む。
スカスカクソデカ盤面がどれくらいあるのかも怪しいし。
それかスカスカじゃなくても這わせる感じになる?

少なくとも seed=1 だと這わせらんないね。まぁこれは壁 40% なので...。
てか手でやって分かったけどサンプル gif 結構賢いな...。
これ MM95 Circle Mix のときも同じこと思ってた気がする。あの時は結局 gif より賢いのできたから、きっと勝てるよね。押忍

壁 20% で手で遊んでたけど、これ全然余裕でぐねぐね這わせられるな...。やっぱりぐねぐねゲーだ、これは。
意外とぐねぐねの柔軟性が高くてそこそこ壁があっても割と隙間を通せるっぽい。
長いパスを作るのなら AHC002 とか AHC010 とかでやったようにとりあえず DFS が有効で、そこから一歩進めると途中の一部分を切り離して別のパスを見つけて繋ぎ変える焼き鈍しかな。
このぐねぐねでそれやるのつらそ〜。あと壁多い盤面だと他のアプローチも考えないとサンプル gif に勝てない。

いやしかし、長いパス作る系の問題ってパスの長さがスコアになることが多いけど、この問題だとぐねぐねの長さの二乗が大体のスコアになるんだよなぁ。エグいよ。

あと、長いパス作ることによってデカい数が解禁されて他所でも使えるようになるので、やっぱり長いパス作ることが重要なんだろうね。

んー、これパスを分岐することも結構簡単にできそうだな。考えることが多い...。
まぁパスの分岐は長いパス見つけた後に生やしていけば良いか。

パス作った後空いたセルを埋めていくロジックも考えないといけないよね。
ただこれは汎用的なロジックにしておくと、壁が多くてぐねぐねがあまり作れなかったときにもこれを適用することでひとまず逃げることができそう。
ぐねぐね可能なケースの割合も多そうだし、ひとまずぐねぐねを形にする方針で進めてみようかな。

2 日目

ぐねぐねを DFS で伸ばしていきます。
8 近傍の探索順序はとりあえず右方向から反時計回りにぐるりと回してみる。


実装途中の動作確認も兼ねて置けるところに置く貪欲を書いてみたら想像以上にしっかり埋まってくれた。へー!

じゃあ汎用的配置ロジックはとりあえずこれで良いな。ぐねぐね生成が煮詰まってきたらそこも詰めよう。


ぐねぐね DFS 書けた!

a

いいですね!後は貪欲に埋めて...

こうじゃ!
それはそうなんだけど下の方は割と空セルが増えちゃうねぇ。まぁ仕方ないか。

ここらで提出してみっか!


55.57392 で BEST の更新もナシ。ふーむ。

...貪欲の置き方が少し甘かったな。今は盤面を上から舐めて置けるとこに置いてってたけど、置ける石のうち大きいものから配置して行った方が良いに決まっている。

あとぐねぐねの開始地点も壁じゃない限り (0, 0) とかにしていて壁に囲まれた小部屋を選んでることがあったので、一番広い空間の端っこを選ぶようにしてみた。

-> 67.57727!イイネ!


ぐねぐねの要素を眺めていたら、もうちょっと繋ぎの 1 の石を共有した方がスペースを有効活用できるんじゃないかなという気がしてきた。
ので、1 の石はできるだけ下から優先的に配置を試してみるようにした。

あと次のセルの探索順序を

432
5*1
678

から

412
5*3
876

に変えてみた。今基本上の方から詰めてるので、ぐねぐね途中で上が空いてたら上に行って欲しい、次いで右、みたいな気持ちの表現。

ぐねぐね後の貪欲実行する前でこんな感じ。前より空いてるスペース減ってる。イイネ!
右上あたりとか 1 の石をとても共有できていて cool.

提出して 77.56237。他人のスコアが気持ち減少したのも確認したので方針は間違ってなさそうだ。

うーん、しかしここまで割と無駄なく詰められるならぐねぐねの分岐はあまり考えなくても良さそう...?
それよりは絶対スコアが小さい、あまりぐねぐねさせられずぐねぐね以外のパートの比重が重いケースのケアをするべきだ。 例えば seed=1 はサンプル gif でスコア 152 出てるけど、自分の解法だと 112 しか出てない。

サンプル gif 眺めてると、ぐねぐねじゃなく、中心から広がっていく感じで外側ほど番号が大きくなっていくみたいな感じに見える。
なるほど、そういうのもあるんだなぁ...。
これは大きい盤面でも応用できる?端がデカい数になってくるとデカい数同士では新しい数を作れなくなってくるのでちょっと厳しい?

うーん、ビームサーチ書いてみる...?それとも賢い貪欲がある?
現在の最大値+1を作れる最短手を探してそれを採用していく?いやそれは結局ぐねぐねになるのでは?

...とりまいつもの、盤面回転させて 4 つ解作ってベストなやつ選ぶやつやるか。。


スコアが 722 -> 1247 とかに伸びたケースもあったので、ぐねぐねで爆死したケースの救済にはなり得たらしい。
4708 -> 39198 とかもある。これはひどい
見てみたら

....
###.

みたいなのの左上からぐねぐねを出発してるパターンだった。なるほどね。

提出して 83.18113!


ビームサーチ、どうなんだろうなぁ...。
なんかデカい石を置けた盤面が幅を利かせそうな気がしてなぁ。どうだろう。
いやデカい石を置けた盤面は良い盤面だからそれで良いのか?

サンプル gif、上方の塊で 7 を作らずに別のところで作ってるのが賢いんだよな。こういうのどうすれば実現できるんだ?
上の塊でも 7 作ろうと思えば作れるから、なんか雑にやるとそうなっちゃう気がするんだよ。
でもかと言って 2 つの塊を作るよう評価関数に人の手を入れるのは違う気がするし。う〜〜〜ん。

後はあれか、ここにこの数字を置きたい!から逆算して周囲に辻褄の合う小さい石を置いていくとか?
できる?わからん...。

乱択でもやってみるか...?


乱択で seed=1 スコア 253 出たあ...!乱択かあ...!
ちなみに乱択で次に置くとこ決めるときは、その時置ける最大の数字の石の中からランダムに選んでいる。

あ〜でも改善したの(seed=1 を含めて)100 ケース中 6 ケースだけだ。
あんまりスコアへの影響は大きくないかも。残念。

ちなみに seed=1 はこんな感じ。19 まで作れるんだねえ。

提出してみたら 0.4 点くらい伸びた。

3 日目

貪欲より乱択をたくさんの方が強いということが分かったので、ぐねぐね作った後の貪欲も乱択たくさんに変えてみる。
-> 提出して +1.5 点!


...ん、置ける最大の石をランダムに選ぶ乱択が有効なら、普通にビームサーチでいいのでは...?


盤面の構造体を直接 priority_queue に突っ込む高速化の余地アリアリな chokudai サーチを書いてみたけど、これでもテストケースによっては乱択に勝てるっぽい。うんうん。


priority_queue に突っ込むのを遷移の情報にして次の盤面はいざ見るぞって時に生成するようにした。
これでだいぶ高速化されて、ほぼほぼ乱択に勝てるようになった。
こうなると今まで乱択たくさん回してたところを chokudai サーチ 1 回にまるっと置き換えても OK そう。

これを提出して 81.576 -> 82.82989。


chokudai サーチ書いてスコアが伸びたケースを眺めてみる。これとかいいね。

これは多分ぐねぐねの後 chokudai サーチパターンなんだけど、38 でぐねぐねが終わった後、ぐねぐねの割と最初の方から新しく 37 が生えてその後 53 まで伸びている。
こういうの勝手にやってくれるなら最初の方に少し考えてたぐねぐねの分岐が〜みたいな話はやんなくてよさそう?


さて、まだ高速化の余地はあるんだけど、正直トップとの差を考えると何か別のアイデアが必要そうな気がする。
実際 chokudai サーチ部分だけ 2 倍の時間やるようにしてみても、伸びなくはないんだけど本番スコアはせいぜい +1 あるかないかぐらいの感じだった。う〜ん。

4 日目

現時点での最大の石 +1 の石を置こうとすると、事前に 1 の石を置かないといけないので、二手かかる。
なので、chokudai サーチ中も 1 の石を置く動作込みの 2 手をキューに突っ込んでみたらどうだろう?


実装してみたけどダメっぽかった...。
いや、chokudai サーチのみでできるぐねぐねの長さは格段に伸びててそこは期待通りだったんだけど、DFS でのぐねぐねには敵わず、かといって小さいケースではぐねぐね作るより広がっていく感じにホイした方が良いのでそっちもダメになった感じ。
ムズ〜。


ダメ元でぐねぐね DFS 中の 1 の石を置く優先順位を弄ったら有意に伸びた。

こんな感じ。前回より直線に進む部分が増えた?

提出してみて 81.35152 -> 83.75755。うんうん。


イデア出ないので高速化に手を出してしまった...。やったのは主に

  • DFS 中の経過時間取得を 1/100 に減らす。
  • 盤面重複で unordered_set 使うのやめる。

DFS は新たな盤面生成とかがなくて相対的に時間取得がネックになってたんだねえ。

提出して 85.0119。


今は制限時間の 9 割をぐねぐね DFS + chokudai サーチ、残りの 1 割を最初から chokudai サーチの解に使ってるんだけど、小さい盤面では後者に時間を割いてあげた方が良さそう。

100 ケースでどっちの解使ってるか眺めたところ、最初の空セルの数が 100 以下くらいなら最初から chokudai サーチに軍配が上がるようだったので、それらはぐねぐね試さないようにした。

84.71134 -> 85.02358


ふと気になって本番サーバ上でのビーム幅出力してみたんだけど、手元の 20% くらいしか回ってない。
手元だと制限時間 3 秒でやってるんだけど...。

chrono 使ったのがマズかった?と思って rdtsc 使ったやつに書き直して出してみたけどあんま変わんない。
M1 チップが速すぎるんかな。

まぁ chrono で良さそうというのは良い発見かも。


ぐねぐね作らない場合、なんかこう初期位置を中心にばぁ〜って広がっていくイメージだったので、なんか初期位置は真ん中に近い方が良い?という天啓が降ってきて、一手目は中央固定にしてみたら、大体のケースでは少し下がるんだけど、2095 -> 2536 みたいな伸び方するケースもあった。
うーん、無視できない伸びしろ。。

これですね。真ん中固定じゃないビームを撃つと普通に右下スタートになって Maximum:47 とかで終わっちゃうみたい。ムムム。


...もしかして、ぐねぐね作ってる最中に、次の数字を既存のぐねぐねの脇とかで作れるならそっちで作って、別のところからぐねぐね続行みたいなことすると良かったりする?
うーんどうだろう。アリな気はするけど。

5 日目

別なところからぐねぐね続行すると大きめの空白がぽつぽつできてダメだった。
じゃあ次の数字を脇に作った後、元のぐねぐねに +2 の石を付けて伸ばしていく?


これうまくいったっぽい!

ちょっと分かりづらいけど、12->14 とか 35->37->39 とかが 1 つ飛ばしになっている。
この後空きスペース埋めてくやつをやると 2400 台くらいには乗った!

手元では 100 ケース平均 3% くらい伸びて、本番では 82.01561 -> 85.29355。


あ、そういえば長いパスは一部分をちぎって再構築する焼き鈍しみたいなのが最終形みたいな話最初の方にしてたな。
今回でもちぎって再構築はできそうだけど...いや、さっきやった 1 つ飛ばしと相性が悪いな。再構築した部分が長くなるとその先にある 1 つ飛ばし部分の数がズレるので。
なら 1 つ飛ばしナシでパス生成 -> ちぎって再構築 -> 根本から順に 1 つ飛ばしにできる箇所をそうする の順?
とりあえず 1 つ飛ばしナシでパス生成 -> 根本から順に 1 つ飛ばしにできる箇所をそうする を実装してみるか。
これだけでワンチャン伸びてくんないかな〜。


うーん、実装前に seed=2 のぐねぐねを眺めてるんだけど、これぐねぐね生成後に 1 つ飛ばしにするために新しく 1 の石置くのかなり厳しくないか...?
あと結構キツキツに詰まってるように見えるから部分的に再構築やる余地もないように見えるんよ。


じゃこういうのは? 2 ずつ進めていく 2 本のぐねぐね。

じ、実装ダルそ〜〜〜。
いや、多分 DFS 書くのはまだなんとかなって、どの優先順位で進ませれば空きスペースができにくいのかがよくわかんない。
新しい一本を今のと逆の優先順位で配置していけば良い感じになるのか?わからない。

いや、冷静に考えたらこれ二つのぐねぐね繋げたら元のぐねぐねと同じ長さになるわけで、余計に 1 の石置かないといけない分ダメだな...。
ボツで。

6 日目

石の数が小さいうちは ↓ みたいな感じで比較的小さい範囲で 1 をあまり使わずに置けたりする。

ので、ぐねぐねの最初だけ全探索なりして 1 の石を少なく抑えてぐねぐね開始するってのはどうだろう?
まぁ、最初がちょっと改善されるだけなのでどれだけ効果があるかは怪しいところ。
小さい盤面なら有効?

あと、DFS ずっと回してもぐねぐねの先の方がちょろちょろ変わるだけだから、一定時間経ったらがっつり巻き戻して別の方向に進めて再開してみるというアイデアもある。
ただこれもそんな派手にスコアが変わるかというと、基本ベストと思われる方向に進んでいるはずなので、う〜ん...。

あと2、思ったんだけど seed=1 みたいなケースって 1 の石の個数の上限決め打ちすれば全探索できたりしない?どうすか?
とりあえずこれから検証しますか。


いや全然だめだ...。1 の石 4 つでもう一生結果が帰ってこない。
一人ぼっちの 1 は最初に置かないみたいな枝刈りすりゃもう少し速くはなるんだろうけど、どうも筋違いな気がしてきた。

でも逆に言うと 3 つだと空セル 39 個のフィールドでも間に合うくらいだったので、ぐねぐねの先頭小さい範囲で全探索はまぁできそうということは分かった。
次それやってみる?


ぐねぐねのスタート地点が左上付近になるケースでは、左上 5x5 マス内で(80msだけ)全探索して、外側に一番デカい数が露出したパターンからぐねぐね開始するようにしてみた。
が、伸びるケースもあれば縮むケースもあって、全体平均で 1.3% 減くらい。う〜〜〜ん...。

すごい伸びたケースだと 13% くらい伸びてるんだよなぁ。


いや、このスコアのブレ方は左上付近で全探索したからというより、単純にぐねぐねの形が変わったからというのが大きいのでは。
つまり、左上付近でごにょごにょするより、単純にいろんなぐねぐねを試した方が良さそうな気がする。

...盤面回転に鏡像を加えた 8 通りでぐねぐね試してみるか。


1% 伸びた...!そんで本番では 83.73241 -> 83.89754。
手元の伸び具合的にもう少し本番でもスコア伸びそうな気がしたけど、実行速度遅いから効果薄いとか?

ん、example のログみたらなんかぐねぐねを試さず chokudai サーチだけするケースでビーム幅が十分すぎるくらい大きくなってるのに手元とスコアが違ってて、なんか怪しい。

あ〜、スコアが同じ場合の順序定義してないからそこで差が出てるのかな?

じゃあスコアが同じ場合には hash 値で比較して...をするとスコア微妙に下がるな。同じ盤面固まりやすくなるのか?

じゃあスコアに乱数足して...をしてもスコア微妙に下がるな...。なにこれ?

んま〜〜本番サーバで十分ループ回ってるならあまり気にしなくて良いか。


いや、それよりログ見ると本番サーバ上でぐねぐね生成 DFS が手元の 1/3 倍くらいの速度なのに対し、chokudai サーチ部分が 1/8 倍くらいの速度なのが気になる。

7 日目

やることなくて困り果てていたところ、回転鏡像の 8 盤面 × {左上, 右上} スタートの 16 通りでぐねぐね作るようにしたら 2% くらい伸びた。
やはり多様性...!! 多様性は全てを解決する...!!


多様性の話ならやっぱり「一定時間経ったらがっつり巻き戻して別の方向に進めて再開」は有効なんじゃないか?実装そんな重くないしやってみよか。


あの、めっちゃ伸びました...!巻き戻し間隔とか、どのあたりまで巻き戻すかを調整して合計 3% くらい伸びた。やっぱ焼き鈍しできない時は解を適当にぶち壊すに限るな。

ちなみに本番スコアの差分メモり忘れちゃったんですが、手元で平均 1% 伸びたら本番スコアが 1 上がるくらいの感じです。
最終日までスコア伸ばし続けられたのはエラいよ。エライワシ

ちなみに2、seed=2 のぐねぐねは最終的に 662 の石まで伸ばせました。

...あっ!!これ見たら部分的に壊して再構築で伸ばせそうなスペース空いてんじゃん!!!やっぱ試してみるべきだったかなぁ...。

まとめ

暫定順位 / スコア

7 位 / 86.76664

方針
  • 空セルの数が 100 以下なら、時間いっぱい特に捻りのない chokudai サーチ。
  • 空セルの数が 100 より多ければ、DFS でできるだけ長いぐねぐねを作って、残ったセルは chokudai サーチで埋める。
    • DFS で一定回数ループしたら強制的にある程度巻き戻し、違う方向に進めた後また DFS する。その中で見つけた最長ぐねぐねの盤面に対し choukdai サーチする。
    • DFSは盤面の回転(4パターン) × 盤面の左右反転(2パターン) × {左上,右上}スタート の 16 パターン試す。