AtCoder Heuristic Contest 004に参加しました。
問題はAlien's Genome Assembly。
大量の部分情報から、全体の情報を推定する問題です。
提出者622人中104位でした。
問題
20x20のトーラス(縦横それぞれの端同士で循環する構造)があり、各セルにA～H(8種類)のいずれかが設定されています。縦横いずれかの連続したセルから2～12文字を測定したデータ(本記事上ではヒントと呼びます)が400～800件あります。辻褄が合うようにトーラス全体のデータを作成してください。*1測定データと合致する件数が多いほど高得点です。
考察
400セルに対してヒントが400～800件*長さ2～12あるので、同じセルに対する情報が多い。完全に部分文字列になっているものもありそうというところから始まり、重複文字が多いヒントは同じ場所から切り取った可能性が高そう、という考えに至る。登場する特定の長さのパターン数は最大400セル*縦横2方向で800パターンに対して、8^3が512、8^4が4096ということで、一致長が4～5あれば大体同じ場所から切り取ったと言えそう。*2
これで長さ20のヒントを2N本作れたら完全復元も可能だけど、運良く正確に準備できたとき専用の処理になりそうなので、それを頑張りすぎて他の実装が間に合わないと破滅しそう。
あとは縦横で組み合わせて上手く敷き詰めたい。完全回答の場合は空きスペースが多いほど高得点らしいけど、何処まで点が取れるか直感的に全く分からない。とりあえず完全回答は出来ない前提で進める。
貪欲を頑張るか、山登り系統か。スコア計算速度が絡むので両立は厳しそう。初期解が悪いと変形を頑張ってもスコア伸びなさそうな気がするし、貪欲かなー。
やったこと
前処理
ヒントのうち、完全に部分列になっているものを統合する。
それとは別に、2つの先頭と末尾で8文字以上一致するものを結合する。本来は5文字一致で良いのだけど、下記の理由により8文字となった。
・考察ミスでチキった
・再帰的に動くので、更に短いものから始めるとタイムオーバーするケースがあった
・長い文字列を作ったはいいけど、配置が隙間だらけになって点が落ちるケースがあった
この辺りは愚直にやったうえ、後者は1つ結合する度に最初から再判定したのでとても重い。seed78のような重いケースだとこれで時間オーバーしてしまうので、本番ケースにタイムオーバーが無かったのは運が良いとしか言えない。それでもヒント情報が長いケースだと、貪欲を1周回しきれずに途中で出力しているものがあるかも…。
これの対策は、文字列を結合すると長くなるという性質を使って、短いものから順番に処理すれば最初から再判定するコストはかなり削れそうな気がする。本番中にそれを実装すると嫌な時間切れの仕方をしそうだったので断念。
貪欲
最初に一番長いヒントを左上に横向きに配置する。
その後はヒント同士で重なる文字数が多いように貪欲に配置。タイブレークでヒントが長い順にした。ヒントが長いものは隙間に入れにくいうえ、複数のヒントが結合されているので価値が高い。それでも同着ならランダム。
終わったら、時間がある限り最初から貪欲を繰り返して、一番いいものを採用。大根005とMM126で貪欲を1回だけして時間を余らせて悔しい思いをしたので、ここはもう失敗しないよう意識した。
やらなかったこと
検索を高速化するためのKMP法とかビット演算とか。
あとは、実はスペースとして使われている'.'は正規表現の任意1文字マッチの文字で、トーラスから切り取った文字列でヒント側に対して検索することも可能そうだった。*3
いずれも縦横それぞれ考えると重実装になりそうだった。
感想
今回は貪欲・焼き鈍し・ビームサーチという基本解法のみの人が多く、知識や発想の方針コンテストというより、実装力コンテストだったように思います。実装力にしても、WAで殺しにくるというよりは、高速化出来れば点に繋がるよという感じ。ただ実行時間制限がきつくて、愚直解法だと本番ケースは通るけどMと部分文字列長が最大のケースは通らないとか、はまりそうなポイントはありました。言語差もあるだろうけど、愚直解は最悪ケースでも通るようにしてほしかったかな。
文字列の連結や敷き詰めパートを高速に処理したいというと、高速なアルゴリズムを短時間で正確に実装する能力が問われるので、6時間という微妙…絶妙？な時間もあって、個人的にはアルゴコンテスト感も強く感じました。
何をするにも実装時間が微妙で逆に手持ち無沙汰になってしまったところがありますが、 はまりポイントだけ乗り越えれば解きやすくて楽しかったです。
