Alice in Foxland ～狐の国のアリス～ 原案: 荒木 担当: 林崎、末松 英文: 平野 解説: 林崎

背景 (1) 世界はきつねでできています 世界のどんなカケラの中にも きつねはいます そんな世界にいる研究者 Aliceさんの ためにプログラムを書きましょう なんて本番中にストーリー追ってる人なんて いませんよね

背景 (2) DNA(Defoxyrenardnucleic Acid)と RNA(Renardnucleic Acid)は、 ‘a’～‘z’の核酸塩基の配列からなります 実世界のDNA, RNAとは綴りが違います 特定の部分配列C(例えば“fox”)を含むDNAは触媒として働きます 研究者のAliceさんは、Cを含む、 できるだけ長いDNAを合成したい

背景 (3) DNAの合成には以下の手順を踏みます 材料としてDNA X, Yを用意する Xの配列をコピーして RNA X’ を合成する Yも同様に RNA Y’’ を作る ここで、X’’ と Y’’ の配列が一致するようにする RNA X’’, Y’’ を使って DNA Z を合成する

要するに 文字列 X, Y, C が与えられる 1600文字以内 XとYのCommon Subsequenceのうち Cを(substringとして)含む 最長の文字列Zを求めよ 複数ある場合は任意の一つ 存在しなければ Impossible

基本的なアイデア (1) “fox” の各文字のX,Y内のマッチ位置は、 先頭が決まれば後はgreedyに詰めて良い C = “fox” として以下解説 X: aaaafaaoaoaxxaoaxaaa Z: aaafoxaaaa Y: aaafaaaaaaoaaxaaaa

基本的なアイデア (2) 下図黒線のようにマッチさせればよい fが決まったら、それ以外は全て左に詰める 紫線のようにマッチさせても損するだけ X: aaaafaaoaoaxxaoaxaaa Z: aaafoxaaaa Y: aaafaaaaaaoaaxaaaa

解法1 (1) DP Longest Common Subsequenceの改造 DP[i][j][0] = (Xのi文字目以降)と(Yのj文字目以降)との Common Subsequenceのうち最長の長さ DP[i][j][1] = (Xのi文字目以降)と(Yのj文字目以降)との Common Subsequenceのうち Cを含むものの最長の長さ

解法1 (2) 基本的にLCS DP[i][j][0] = max{ DP[i+1][j][0], DP[i][j+1][0], DP[i+1][j+1][0]+1 (X[i]==Y[j]のみ) }; これはLCSそのもの

解法1 (3) 基本的にLCS DP[i][j][1] = max{ DP[i+1][j][1], DP[i][j+1][1], DP[i+1][j+1][1]+1,(X[i]==Y[j]のみ) DP[i’+1][j’+1][0] + Clen (ここが違う; 次スライド) }; Clen: Cの長さ DP[0][0][1]が求める最長配列の長さ

解法1 (4) DP[i’+1][j’+1][0] + Clen i’/j’: X/Yのi/j文字目以降をgreedyに“fox”とマッチングさせた場合の最後の文字の位置 i i’ X: aaaa faaoaoax xaoaxaaa Z: aaafoxaaaa Y: aaa faaaaaaoaax aaaa j j’

解法1 (5) Xのi～i’文字目, Yのj～j’文字目を“fox”に マッチング(Clen文字; 水色枠) + 残りを普通にLCS (灰色枠) i i’ X: aaaa faaoaoax xaoaxaaa Z: aaafoxaaaa Y: aaa faaaaaaoaax aaaa j j’

解法1 (6) 計算量 (n:X,Yの長さ m:Cの長さ) i→i’は事前計算してテーブル引きする DPのステート数はO(n2) 工夫するとO(nm)になる DPのステート数はO(n2) 1ステートあたり計算量はO(1) 全体計算量はO(n2) テーブル引きしないとO(n3)で TLE

解法2 (1) 本質的にあまり変わらない Cの最初の文字のマッチング位置(i,j)を決める 最後の文字のマッチング位置(i’,j’)が決まる i i’ X: aaaa faaoaoax xaoaxaaa Z: aaafoxaaaa Y: aaa faaaaaaoaax aaaa j j’

解法2 (2) (i,j)以前と(i’,j’)以降(図の灰色枠部分)は それぞれ単なるLCS それらのLCSとCをつなぐ i i’ X: aaaa faaoaoax xaoaxaaa Z: aaafoxaaaa Y: aaa faaaaaaoaax aaaa LCS + “fox” + LCS j j’

解法2 (3) これを全ての(i,j)の組について調べて 最大長を取る 計算量: O(n2) あらかじめLCSを実行して、 (Xの最初/最後i文字)と(Yの最初/最後j文字)のLCS長のテーブルを作っておく i→i’, j→j’のテーブルも作っておく 計算量: O(n2) テーブル作成、全(i,j)の検査共にO(n2)

ダメな解法 DP[i][j][k]: (Xのi文字目以降)と(Yのj文字目以降)のCommon Subsequenceのうち、 (Cのk文字目以降)を(prefixとして)含むものの最大長、的なDP O(n3)=16003=40億 TLEの前にMLE

Judges’ solutions 110～140行 実行時間: 6秒～24秒

Statistics Submit: 42 (15 teams) Accept: 13 First Accept: 104min (echizen.bat)

おまけ:問題文ネタ解説 きつね担当: 林崎

どうみてもネタ問題文です “people with watchful eyes will find foxes in every fragment of the world.” 「よく見ると、世界の断片の一つひとつに きつねがかくれているものだ。」 この文の通り、問題文にもきつねが たくさん隠れていました。 いくつ気づいたでしょうか。

きつね (1) Defoxyrenardnucleic Acid (DNA), Renardnucleic Acid (RNA) Professor Fuchs Fuchs: 狐(ドイツ語) Professor Hu (胡) 化狐のよく使う姓。中国語で狐の発音はhu

きつね (2) In 2323, ... In 2369, ... ふさふさ。別に狐に限らないけど。 A-Zを0-9にマッピングして電話番号を文字列表記する方法を使うと A FOX → 2369 参考: PKU 1002

きつね (3) DNAs can be easily obtained by extraction from some plants such as glory lilies. 和名キツネユリ Tail Environmental Natural Catalyst Organization TENCO(天狐)。あと尻尾。

きつね (4) Sample Input内 czujthebdgfoliskax fennec oinarisama xiaorong 狐(チェコ語) fennec oinarisama xiaorong 順にフェネック(狐の一種), お稲荷様, 小栄 (聊斎志異「嬰寧」に見える狐の少女の名) 縦読みで fox