ゲノコン2021 問題Cの最高点解法

ゲノコンを頑張っていました。順位は5位で審査員特別賞を頂きました。
D問題については別途記事を書こうと思いますが、C問題で4人しかいない最高点を取れたので、解法を記しておきます。

atcoder.jp

問題

atcoder.jp

Largeで40個、長さ750の文字列をいい感じに合わせる（マルチプルアラインメント）という問題です。
サンプル1の入力、出力を見るとわかりやすいと思います。

解法の概略

  • ACGTのいずれかを1文字ずつ決めていくことで参照文字列Gを作るビームサーチを行う。
  • 参照文字列を作成する途中の文字列gに対する評価をDPで行う（詳細は後述）
  • 文字列gのi文字目の評価を行うとき、それまでのDP配列を用いて計算できるため、文字の追加ごとの計算量はO（文字列の個数 x 長さ）で済む。
    これを概ねビーム幅 x 文字列の長さの回数行うため、O（ビーム幅 x 文字列の個数 x 長さ x 長さ）で計算できる
  • 計算時間およびメモリはかなりタイトであり、ビーム幅4までしか発射できなかった。ただし、後述の工夫を使うことで、10倍くらいにできそう。

以下、ビーム幅をW、文字列の個数をM、文字列の長さをL、参照文字列の長さをL_G、文字列の長さをL_sとします。

ポイント１ - 参照文字列に対するスコア計算

まず、m本の文字列を一度に扱ってm対mにするより、1つ参照文字列を作って1対mにした方が効果的に思える。以下のようにすると、1対mの形で扱える。

参照文字列Gがあるとき、Gに各文字列をうまく対応させることによってできるマルチプルアラインメントのスコアは、
以下のようにDPで計算したGと各文字列sのアラインメントのスコアの総和で計算できる。

  • Gをi文字目まで使い、sをj文字目まで使ったときのコストを考える
  • DP[i, j]は、以下のうちもっとも小さいものとなる
    • DP[i-1, j-1] + 1 （Gのi文字目とsのj文字目が等しくない場合）
    • DP[i-1, j-1] （Gのi文字目とsのj文字目が等しい場合）
    • DP[i-1, j] + 1
    • DP[i-1, j-1] + 1
  • スコアは DP[L_G, L_s] となる

このDPを直感的に表すと以下のとおり：

  • Gのi文字目と文字列sのj文字目をマッチングさせ、等しければコスト0, 等しくなければコスト1とする
  • Gのi文字目をスキップし、コスト1とする（sに文字を挿入する操作になる）
  • sのj文字目をスキップし、コスト1とする（sの文字を削除する操作となる）

例を挙げると、参照文字列GがGAG、文字列sがGGAGCのとき、DPテーブルは以下のようになり、スコアは2となる。

f:id:threecourse:20211001022735p:plain

ここで、マルチプルアラインメントで複数の削除や挿入が重なることが気になるが、以下のとおり各文字列での削除・挿入コストの和で捉えて良さそうである。

複数の文字列で同じところを削除するときは、以下のようになる。
f:id:threecourse:20211001021823p:plain

複数の文字列で同じところに挿入するときは、以下のようになる。
f:id:threecourse:20211001022001p:plain

ポイント２ - 参照文字列の途中経過の評価

上記のスコアは、文字列sの余った部分がコストになってしまい、参照文字列Gを作成する途中の状態の評価としては適切でないため、ビームサーチの評価関数としては使えない。 ここで、ビームサーチの評価関数として適切な値を考える。

DP[L_G、j] (0 \leq j \leq L_s) の最小値は、各文字列に対してそのあとに理想的に参照文字列に文字を加えていった場合のスコアといえ、評価関数として良さそうである。

例を挙げると、参照文字列GがGAG、文字列sがGGAGCのとき、そのあとに理想的に参照文字列に文字を加えて得られるベストなスコアは1であり、下図のピンク部分の最小値である。

f:id:threecourse:20211001022950p:plain

つまり、評価関数としては DP[L_G、j] の最小値を使い、最終的な評価としては DP[L_G、L_s] を使うビームサーチとなる。

ポイント３ - ビームサーチでの効率的な計算

参照文字列と一つの文字列のアラインメントを求めるDPであっても、計算量はO(L^2)となってしまう。 これを毎回フルで各文字列に対して行うと10秒ではとても足りない。

ビームサーチでは、参照文字列の途中の文字列gまでの評価が既にある状態で、gに1文字足した場合の評価を求めれば良い。 これは、ポイント2のDP配列のピンク色の部分だけを計算すれば良いため、各ビームサーチで1文字加える部分での計算量は O(ML)で済む。

これらが揃うことで、無事ビームサーチの枠組みに持ち込める。 参照文字列の長さはこの問題では大体各文字列の長さと同じくらいになるので、ビームサーチのステップもL程度。計算量はO(WML^2)となり、なんとか計算可能になった。

さらなる計算量の改善

実は提供されたゲノコンD問題のスコアリングの関数がヒントになっている。 ゲノコンD問題は文字列の長さが30000もあり、素直に計算するとPCが爆発しそうでどうするんだ？と思った。コードをよく読んでみると、アラインメントを求めるときに文字列のずれを600程度に制限してスコア計算を行っている。

ある2つの文字列のアラインメントを完全に求める計算量はO(L^2)であるが、それらの2つの文字列の中のずれを幅Bまでしか許容しないとすれば、O(2LB)まで減らすことができる。 ゲノコンCにこれを適用すると、B = L/20とすることで、計算量を1/10にでき、ビーム幅が増やせる。なお、試していません。。

他の方の解法

他の最高得点の解法は結構違うようで、なかなか面白いですね。