Document

Alice in Foxland
～狐の国のアリス～
原案: 荒木
担当: 林崎、末松
英文: 平野
解説: 林崎
背景 (1)



世界はきつねでできています
世界のどんなカケラの中にも
きつねはいます
そんな世界にいる研究者 Aliceさんの
ためにプログラムを書きましょう
□ なんて本番中にストーリー追ってる人なんて
いませんよね
背景 (2)

DNA(Defoxyrenardnucleic Acid)と
RNA(Renardnucleic Acid)は、
‘a’～‘z’の核酸塩基の配列からなります
□ 実世界のDNA,


RNAとは綴りが違います
特定の部分配列C(例えば“fox”)を含む
DNAは触媒として働きます
研究者のAliceさんは、Cを含む、
できるだけ長いDNAを合成したい
背景 (3)

DNAの合成には以下の手順を踏みます
X, Yを用意する
□ Xの配列をコピーして RNA X’ を合成する
□ X’ から0個以上の塩基を削除して
RNA X’’ とする
□ Yも同様に RNA Y’’ を作る
□ 材料としてDNA

ここで、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’は事前計算してテーブル引きする
単純に全部調べても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
“fox” +
LCS
Z: LCS + aaafoxaaaa
Y: aaa faaaaaaoaax aaaa
j
j’
解法2 (3)

これを全ての(i,j)の組について調べて
最大長を取る
□ あらかじめ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)
□ fox:
狐(英語); 他にも多数回出現
□ renard: 狐(フランス語)

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
順にフェネック(狐の一種), お稲荷様,
小栄 (聊斎志異「嬰寧」に見える狐の少女の名)
 縦読みで fox


Download Report