参加しながら考えたこと試したことの源泉かけ流し。
最終的な方針は まとめ にまとめてあります。
問題概要
~ 開始 40 分後
問題を読む。ふむふむ。
まず気になるのが、満点のときのボーナス点がもらえるタイプの問題であること。満点までは線形に点が増えて、ボーナス点は、うーんこれどの程度なんだろう。まあそれはいいや。とりあえず満点出せる可能性が示唆されていることだけ頭に留めておく。
入力ジェネレータ落として動かして作業開始。
ひとまずランダム解を作って入出力の誤りが無いかやスクリプト類が期待通り動くかを確認する。
-> 書いた。問題なさそうだ。
さて、解法としてまず思いつくのは将来的には焼き鈍しを睨みつつ、行列のうち一箇所を別の文字に試しに変えてみてスコアが上がれば採用する山登り。とりあえず動くものならそんなに実装重くないし、書いてみる。動けばいいのでスコア関数もナイーブに O(MLN2) のやつを書く。
-> ランダム解に毛が生えた程度のスコアしか出ない。ひどいケースだと 0 点まである。んー…？と思いながら山登りの試行回数を見てみたら時間いっぱい回して 300 回程度しか回ってない。あらら。さすがにスコア関数重すぎか。
近傍を工夫する（例えば与えられた部分列をドンと当てはめてみるとか？）ことで同じ試行回数でももう少しスコアは伸ばせるだろうが、300 回じゃどうにもならない。スコアの差分計算…は初手で書くには重すぎる。この方針は無理。一旦捨てよう。
~ 開始 1 時間 10 分後
焼き鈍しがダメなら、与えられた部分列を順番に置いていくしかない。長い部分列ほど後から置きにくいそうなので与えられた部分列を長い順にソートして、順に置いていく。置く際は、既に配置済みのアルファベットと一番重複する場所に置くことにする。とりあえずここまで書いて手元で 50 ケース試してみると、提出後 4.4G 点くらいが見込めそうな感じ。1 ページ目載れそう？いいね。
後は計算時間が余ってるので、部分列の順番をシャッフルして山登りを時間いっぱいたくさん試して、一番たくさんの部分列を置けたものを採用するようにする。が、スコアは変わらず。部分列シャッフルしたので 2 回目以降の山登りでは長い順じゃなくなってるんだけど、たくさんのそれらより長い順山登り 1 回の方が良いスコアなので、なるほど長い順で置いていく方針は正しそう。ということで、同じ長さの部分列内でのみ順番をシャッフルするようにして時間いっぱい回して、これはしっかりスコアも伸びた。提出して 4.8G 点の 7 位。いいね！
~ 開始 2 時間後
L が大きいケースだと、かなり部分列の重複がありそうな気がする。例えば L=10, M=400 だと、行列が 400 文字に対して部分列の情報は 4000 文字くらいあるわけで、こんなん絶対被りまくってる。繋げられる箇所は事前に繋げておくと何か変化が起こるかもしれないので、試してみる。
何文字重複してたら繋げちゃっていいだろう。5 文字くらい？ 5 文字の部分列のパターン数は 85 = 32768 通り。ん〜まぁこれくらいパターン数多けりゃ偶然違うところが繋がる事故も少ないだろう。
部分列の全ペアについて前後が 5 文字以上重複するかを調べて、重複した場合それらを合体させて新しい部分列にして、古い 2 つの部分列は削除して、また最初っから全ペアのチェックを回し始める。ちょっと雑すぎかな？と思ったけど 0.5 秒くらいで終わってくれてるように見えるからまあ良し。ちなみに繋いだ結果 20 文字を超える場合はちゃんと 20 文字の輪っかになってるか確認しないとなんだけど、微妙に面倒だったのでサボって 20 文字を超える場合は繋がないようにしてる。で、問題のスコアはと言うと…劇的に伸びている！え、これ暫定 1 位に匹敵するスコアに見える…と思いながら提出すると暫定 1 位が取れた。6.38G。ここで一踊り。
— iwashi31 (@iwashi31) June 26, 2021
5 文字の重複で繋げてたところを 4 文字や 6 文字に変えるとスコアが落ちた。どうも、最適パラメータの審美眼を持っている男です。
~ 開始 3 時間後
ある部分列について、それが他の部分列にそのまま含まれるなら、その部分列は削除しても良さそう。と思って削除してみたら、スコアが落ちた。え？
…まあいいや、さっきサボってた繋いで 20 文字以上になる場合は 20 文字の輪っかになってるか確認して、なってたら繋いで 20 文字の部分列として扱うやつをやろう。書いた。スコアが落ちた。え？？
改善しないだけなら分かるけど何もスコア落ちることはないんじゃないか。反抗期か？
で、うんうん悩んでて気付いたんだけど、今って山登り結果の評価を置けた部分列の数でしか評価してなくて、それって真のスコアと少し乖離があるんじゃない？繋げた部分列には 2 つ分の部分列の価値があるわけだから、部分列の数で数えるのは少しマズそう。うんうん。違いない。
というわけで、繋げた後の部分列について、それが何個分の部分列なのかの情報を保持して、置けた部分列についてその数値を足し合わせた値を山登りの評価値としてあげた。これは流石に伸びる！と思ったが、スコアは落ちた。あー？？
キレながら上の変更をゴミブランチに捨てコミットして、代わりに各山登りの終わりに O(MLN2) ナイーブスコア計算をするようにした。これにより山登りの試行回数は 1000 回くらい回ってたのが 300 回程度に減っちゃうわけだが、さすがにこれは素直に伸びてくれた。提出して 6.47G の暫定 3 位。
~ 開始 3 時間 30 分後
今は部分列を長い順で置けるなら必ず置いているわけだけど、dropout っぽい気持ちで低確率で置かないみたいなことしたらどうだろう？と思ったが、誤差くらいのスコア変動しかしなかった。一応提出してみたが微減した。
あと山登りのアイデアとして、次の操作のうち最善の手を探して採用していくというアイデアもある。いわゆる貪欲か。今はソート済みの部分列を順に配置していってるわけだが、これをその時点で一番いい感じの部分列を探して選んでそれを配置するという風に変える。その時点で一番いい感じとはつまり、配置済みのアルファベットと最も重複する、とかか。試してみたが、少し重い！ 1 回の山登りで最大 2 秒ほどかかる。ただ、どうやらそれでも L <= 5 のケースではスコアがかなり改善している。L = 6 だと良くなったり悪くなったり。L >= 7 だと全体的に悪くなってる。ということで、L <= 6 のケースではこっちの方針を採用することにした。提出して 6.56G の 5 位。
ちなみにこういう入力パラメータごとの傾向は、スコアをスプレッドシートで管理して Filter View でパラメータについてソートすると人力でも比較的把握しやすい。
~ 開始 5 時間 50 分後
20 文字以上の輪っか処理とか他の部分列にそのまま含まれる部分列は削除する処理とか、もっかい試してみたら部分列こそ減れど前ほどスコアの減少はしなくなった？
で、部分列繋ぐ前処理した後の部分列の数について眺めていたら、L が大きいケースでは 40 個近くまで減ってることに気がついた。ん、これ各行各列の文字列特定できてるのでは？？え、これもしかして L が大きいケースでは 40 個の文字列特定してそれらをガチャガチャして復元して満点狙うゲーム？ぐえ〜アルゴじゃん〜〜。これちゃんとやった人が終盤ぶっちぎっていくのは確実なので、この先生きのこるには自分も書き上げないといけない。できるかなああ。
41 個まで絞れてあとそれとそれ繋ぐだけじゃん！目視で分かるよ！（ただし共通部分は 5 文字未満）みたいなケースがちらほらあったので、とりあえず 5 文字で繋いだ後 4 文字、3 文字でも繋ぐようにしたらオマケでスコアも微増した。そんなのはどうでも良くて今は 40 個の部分列から盤面を復元する処理だ。
思うのが、3 行分くらい決め打ちしたら、その 3 行の縦 3 文字に合致する部分列を探して持ってきて、全列揃えば完成させられるんじゃないか？ 1 行目は適当で良くて、2 行目 3 行目の部分列がそれぞれ 2N 種類くらいずつ、2 行目 3 行目の部分列の開始位置がそれぞれ N 種類ずつの O(N4) × 縦チェックくらい？全部の列に合致する部分列が見つかればそれはもはや正解な気がするので、行はチェックせずに見つかった時点で出力させてみる。はい実行！お、時間内に答えが見つかったっぽい…けど、満点ではない…？むしろちょっとスコア下がった…？ビジュアライザを見るとこんな感じになっていて、上 3 行以外は横の整合性が取れてないことが分かる。うーむ、正解じゃなくても全列合致しちゃうのか。
ということで、時間内に見つかったうち一番スコアの高いものを出力させてみるも、微妙なスコアのまま。というか時間いっぱい回しても正解がヒットしない。あれ？？
試しに上 3 行全探索のところを 4 行全探索にしてみつつバグを修正したりすると 30 分くらいかけて正解を見つけるやつができた。じゃあこれを 3 行にして…ってするとやっぱり正解がヒットしない。いや、何？？
そうこうしているうちに残り時間が 15 分くらいになってしまった。仕方がないので
5 文字で繋いだ後 4 文字、3 文字でも繋ぐようにしたらオマケでスコアも微増した。
この修正だけ含めて提出して 6.62G の暫定 12 位。
~ コンテスト終了
終盤なだけあって今までより速い勢いで順位が落ちていく。あと 2 回提出チャンスあるけど何かできることは…。
あ！あの 4 文字、3 文字でも繋ぐようにする処理って部分列を 40 個に絞りきりたい気持ちで書いたやつだから、部分列がたくさん残ってるときはやらなくていいかも！部分列が 50 個以上残ってたらやらないようにして、提出！6.52G 。ほげ〜。
もう本当に何もアイデアがないので、最後の 1 回は乱数ガチャということで開幕乱数を 100 回空打ちするように（wikipedia からコピペしてきた xorshift のシード弄って大丈夫かどうか知らないので…）して提出した。あまり期待はしてなかったが、これはそれまでの最高スコアから 0.01G 伸びて、最終順位を 16 位から 14 位に押し上げた。やってみるもんだね。
まとめ
順位 / スコア
14 位 / 6,631,433,081
方針
- L が 7 以上の場合
- 部分列を長い順にソートして、順番に配置していく。
- 配置するときは、既に配置済みのアルファベットと最も重複するように置く。配置できないならパス。
- 一通り終わったら、同じ長さの部分列内で順番をシャッフルして上記の処理を一からやる。これを時間いっぱいやって一番スコアが良かったものを出力する。
- L が 6 以下の場合
- 既に配置済みのアルファベットと最も重複する部分列から順番に配置していく。
- 余った時間は L が 7 以上の場合と同様のことをする。
- 前処理として、長さ 5 以上の共通部分を持つ部分列のペアは合体させておく。
