atcoder abc_122【We Like AGC】D問題 を解いてみた(python3)
今回初めてD問題を解いたので、記念に記事を残したくなりました。
この記事は私のような初心者が、初心者に向けて考え方を発信します。
拙い文章ではありますが誰かの参考になったら幸いです。
chokudauさんの解説（C++）をpython3で書き直しています。
-問題文
問題ページ【D - We Like AGC】
整数 N が与えられます。次の条件を満たす長さ N の文字列の数を 10^9+7 で割った余りを求めてください。
- A, C, G, T 以外の文字を含まない。
- AGC を部分文字列として含まない。
- 隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。
【注記】
文字列 T の部分文字列とは、T の先頭と末尾から 0 文字以上を取り去って得られる文字列です。
例えば、' ATCODER ' の部分文字列には' TCO ', ' AT ',' CODER ',' ATCODER ', (空文字列) が含まれ、' AC 'は含まれません。
【制約】3≤N≤100
-問題文の意味
問題文の意味が難しかったのですが、解説してくださっていたのでここでもまとめてみます。
条件文 2 について
例えば長さ 6 の文字列を作成したとき、
T A G C A C
という文字列には ' A G C ' が含まれているので条件を満たす文字列の数には含まれません。
T T G C A C
これならOK。
ここで、
A G C T ↓ ↓ ↓ ↓ 0 1 2 3
と置き換えさせてもらいます。つまり ' A G C ' → ' 0 1 2 ' と書き表します。
さて、条件文 3 を見るとちょっと難しいことが書いてあります。
どういう事かというと「作成した文字列の一箇所をswapして ' 0 1 2 ' が出来たら条件違反」ということ。
例を見たほうがわかりやすいですね。sawpして ' 0 1 2 ' が出来るということは、
# ? は 0 1 2 3 のどれか 1 0 2 --swap→ 0 1 2 0 2 1 --swap→ 0 1 2 0 ? 1 2 --swap→ ? 0 1 2 0 1 ? 2 --swap→ 0 1 2 ?
ということ。つまり作成した文字列の中に
0 1 2 1 0 2 0 2 1 0 ? 1 2 0 1 ? 2
が入っていると条件違反ということになります。
-アルゴリズム
条件文の意味が理解できたのでアルゴリズムについて考えていきます。
ここで条件を満たしている文字列を S と置きます。
そして S の後ろに新しい文字 a を足して新しい文字列を作ります。
例えば S = . . . . 3 0 1 とする。
後ろに a を足して出来る文字列を nextS とすると
a = 0 nextS = S + a = . . . . 3 0 1 + 0 =. . . . 3 0 1 0 a = 1 nextS = . . . . 3 0 1 1 a = 2 nextS = . . . . 3 0 1 2 ← a = 3 nextS = . . . . 3 0 1 3
4つの nextS が出来ました。ですが、 a = 2 の nextS の最後 3 文字に注目してください。
条件違反となる文字列 ' 0 1 2 ' が出来てしまいました。
つまり、新しい文字列 nextS を作成する際は、 S の最後の 3 文字に注目して条件違反にならないか確認しながら作りましょう。
それより前の文字列は条件を満たしていれば何でもいいです。
このように条件を満たす文字列を増やして一つ一つ保存して、入力 N で与えられた文字数の文字列の個数を数えれたば答えが出ます。
これはすごく時間がかかりそう・・・。
ここで DP（動的計画法）の出番です。
-DP（動的計画法）を使ってみる
DPについて初心者に優しく解説してくださってる記事があります。下からどうぞ。
qiita.com
- DP 配列全体を「DP の種類に応じた初期値」で初期化
- 初期条件を入力
- ループを回す
- テーブルから解を得て出力
これに従って今回の問題をDPに落とし込んで考えていきます。
先程の章で条件を満たした文字列で重要な部分は、最後の 3 文字と文字列長ということが分かりました。
今回注目するべき変数は 4 つあるので 4 次元配列をDP配列とします。
そして条件を満たしているとき 1 、条件を違反しているとき 0 が代入されるようにします。
len = 文字列長 c3 = 最後から 3 番めの文字 c2 = 最後から 2 番めの文字 c1 = 最後から 1 番めの文字 dp[len][c3][c2][c1]
あとはforループをたくさん回します。
「ある文字列」 に a を足したときの最後 3 文字が条件を満たしている場合、
「ある文字列」 から 「ある文字列 + a」 へ 1 or 0 が引き継がれます。
こうしてDP配列に値が代入された、DPテーブルができます。
あとはDPテーブルから文字列長が N のときの値を足していくと、条件を満たしている文字列数が得られるということです。
-プログラム
# -*- coding: utf-8 -*- N = int(input()) # A C G T を # 0 1 2 3 と置く dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(101)] dp[0][3][3][3] = 1 mod = 10**9+7 #文字列の文字数 for len in range(N): #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): #新しく追加する文字 for a in range(4): if c2 == 0 and c1 == 1 and a == 2 : #012 continue if c2 == 1 and c1 == 0 and a == 2 : #102 continue if c2 == 0 and c1 == 2 and a == 1 : #021 continue if c3 == 0 and c1 == 1 and a == 2 : #0?12 continue if c3 == 0 and c2 == 1 and a == 2 : #01?2 continue dp[len + 1][c2][c1][a] += dp[len][c3][c2][c1] ans = 0 #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): ans += dp[N][c3][c2][c1] ans %= mod print(ans)
分解してみますね。
dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(101)]
今回は 0 で初期化します。
4 次元配列のみため、ものすげえです。
dp[0][3][3][3] = 1
長さ0、最後から 3 文字目 ' 3 ' 、最後から 2 文字目 ' 3 ' 、最後から 1 文字目 ' 3 ' は、
条件を満たしているということにします。
こうしておくと、 a を足したときに 長さ 1 、 文字列 = 3 3 3 a となる。
つまり、3 3 3 の部分は無視できて a から長さをカウント出来る。
（ややこしくなってすみません）
#文字列の文字数 for len in range(N): #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4):
ここで 5 重ループのうち最初の4 重ループで、 dp[0][0][0][0] ~ dp[N][3][3][3] まで虱潰しに調べていきます。
for a in range(4): if c2 == 0 and c1 == 1 and a == 2 : #012 continue if c2 == 1 and c1 == 0 and a == 2 : #102 continue if c2 == 0 and c1 == 2 and a == 1 : #021 continue if c3 == 0 and c1 == 1 and a == 2 : #0?12 continue if c3 == 0 and c2 == 1 and a == 2 : #01?2 continue dp[len + 1][c2][c1][a] += dp[len][c3][c2][c1]
最後のループで文字列の最後につける a を回します。
中では「ある文字列」に a を足したときに条件違反になるかを調べています。
条件に引っかかると、「ある文字列 + a」 は0のままになり、条件を抜けると「ある文字列」の値を引き継ぎます。
ans = 0 #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): ans += dp[N][c3][c2][c1] ans %= mod
ここの 3 重ループで先程作ったDPテーブルから、文字列長が N のときの値をすべて抜き出して足してきます。
ans %= mod
オーバーフローする可能性があるので、毎回忘れずに10^9+7で割っておきます。
-最後に
ここまで見てくださって、ありがとうございました。
間違っていたり、変えたほうがいいところがあったらどうか教えてください。
つよつよの人はこれを10分くらいで実装するんですよね、すごいです。
私もいつかスラスラ解けるように精進します。
