Marathon Match 70

2年ぶりのマラソン。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&compid=16072&rd=14525 (要ログイン)

  • 一本のDNA(A,T,G,C からなる文字列)と酵素の集合が与えられる。
  • 酵素は固有のパターンを持っていて、そのパターンが現れた位置でDNAをカットする。
  • カット後のDNA片が与えられた条件を満たすような酵素の部分集合を求めよ。

条件は8種類。

  1. DNA片の数の最小値。
  2. DNA片の数の最大値。
  3. DNA片の長さの最小値。
  4. DNA片の長さの最大値。
  5. DNA片の長さの比の最小値。長さが近すぎる2つのDNA片があったらダメ。
  6. 酵素のパターン長の最小値。
  7. 酵素の数の最大値。
  8. DNA位置の範囲(0〜3つ)。指定された範囲内に少なくとも1つのカットが必要。

あとはDNAは環状になってるかもしれないとか、酵素は順方向と逆方向でマッチが可能とか細かいルールが色々。

得点

返した酵素の部分集合の数(最大100個)が得点となる。ただし、実行時間が0.3秒を超えると得点が減っていく。

解き方

前処理部分と探索部分に分けて考える。

前処理

条件6を満たすそれぞれの酵素に対して、DNAをカットする位置を求める。
パターンマッチは酵素ごとにDFAを作った。いくつかの酵素ワイルドカードが多くてDFAの状態数が膨大になるので、それらについてはナイーブな strstr的方法で。改善の余地はだいぶあるけど、どうせ前処理部全体で0.1秒以内で終わるのであまりここは凝らなかった。

また探索を高速化するために、いろいろ計算しておく。

  • カットの結果、条件2より多くのDNA片ができたら、その酵素は使えないので捨てる。
  • カットの結果、条件3より短いDNA片ができたら、その酵素は使えないので捨てる。
  • 酵素のペア (A, B) のカットの和集合が条件2, 3を満たさない場合、Aを選んだらBは使えない(その逆も)。すべての酵素についてこの関係を記録しておく。
探索

酵素をカットの数が多い順に並べて、深さ優先で探索していく。マラソンでDFSで解けるってかなり珍しいんじゃないだろうか。

改良

TopCoderの実行サーバーで0.3秒を超えると点数が下がるので、時間がかかるテストケースを探しては遅くなる原因を探して枝刈りを追加、というくり返し。

枝刈りの例を挙げると、以下のような場合に探索を打ち切るようにした。

  • 残りの酵素で条件8を満たせなくなった場合
  • 条件4より長いDNA片をすべてカットすると条件2を満たさなくなる場合
  • 残りの酵素で条件1と条件7を同時に満たせなくなった場合
  • 残りの酵素で目いっぱいカットしても、条件1または条件4を満たせなくなった場合

最終的には、手元の環境で 200,000 ケース実行して解があるケースで 0.1 秒以上かかるものは無し、解なしのケースでは0.2秒台が1つだけになった。

結果

http://www.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14525

1位! …だけど同点1位が16人というアレな結果に。
Forumを見ると100万件とかテストしてたりマッチングを超頑張ったりしてる人も居たけど、5000件程度の system test では差がつかなかったようだ。少々可哀想な気もする。

あと賞金貰うにはコードの解説を提出しないといけないらしい。めんどい…