こんばんは。特に何もすることなく春休みが終わっていくことに嘆くとーです。
今日から解くに至った問題は記録しないことにします。めんどいので。
AGC031B
いつもお世話になっているじゅっぴーダイアリーを読んで、自分なりに考えたことをまとめる
類似の問題で取り上げられていた
Sの連続した部分列のうち、同じ文字が含まれない取り出し方は？
という問題の解き方は
①基本的に前の方から後ろに向けて、文字列を伸ばしていく
②今持っている文字列の中に、次に見る文字が含まれていなければ、(今持っている文字列の長さ+1)だけ足す
(例)
abcという文字列で、今見ている文字列がab、次に見る文字がcであれば、cはabの中に含まれていないので、cを付加することによりカウントされる文字列はc,bc,abcの3つ
③今持っている文字列の中に、次に見る文字が含まれていたら、文字列中のその文字が含まれなくなるまで文字列を短縮し、それから次の文字を入れ、（今持っている文字列の長さ+1）だけ足す
(例)
abcaという文字列で、今見ている文字列がabc、次に見る文字がaであれば、aはすでに文字列に含まれているので、aを落としてbcに縮め、それから再びaをくっつける。新たにカウントされる文字列はa,ca,bcaの3つ
を繰り返していくという感じ
この動きを管理する漸化式を立てるとき、
「これまでに見た文字列の中で、既出の文字がどのインデックスで出てきたか」を格納するリストが必要で、これと「一番最後に見た文字」を照らし合わせる
さらに、「今持っている文字列の一番最後のインデックスがどこにあるか」という情報も必要になる
これは、次に見る文字に対して新たに何個の文字列ができるかということを考えたとき、
①次の文字が、今見ている文字列の最後（インデックス的に言えば0に近い方）のインデックスよりも前のインデックスで一度以上出現していた→文字列に付加しても文字列が縮まることはない
②①ではない→その文字の所まで文字列を縮める必要がある
ということがあるからだ
だから、答えのコードに説明をつけると、
n = int(input()) #文字数 s = list(input()) mod = 10**9+7 def f(x): return ord(x) - 97 used = [-1]*26 #ここに文字ごとにその文字が使われた直近のインデックスが入る tank = -1 #文字列の末尾を示す res = 0 for i in range(n): res += (i - max(used[f(s[i])],tank))%mod #新たに増える文字列がいくつあるか tank = max(tank,used[f(s[i])]) #文字列の末尾を更新する（同じまま推移することもある） used[f(s[i])] = i #今見た文字の直近のインデックスを更新 print(res)
となる
これを今回のAGCのB問題に応用すると、
①隣り合っている同色の石は（隣り合っていること自体）無意味なので一つにまとめてよい
②i番目の石までの並べ方はdp[i] = dp[i-1]+dp[used[i]]とできる i-1番目までの色の並べ方に「i番目の石と同じ色の石で、最もi番目に近い石までの並べ方」を足せばよい理由は、その「最もi番目に近い石までの並べ方」をj番目とすると、「i~j番目の石をすべてその色で塗る」という行為で増える色の分＝増やすべき要素数（逆に、これまでに登場しない色であれば、その間を塗ることで増える場合の数はない）となるからである
ということを使っていけばよい（②で考える分、類似問題のように「現在見ている文字列の、先頭に近い（ケツの）文字の情報」を保持しておく必要はない）
python3によるコード
N = int(input()) K = [] for i in range(N): K.append(int(input())) L = [K[0]] for j in range(1,N): if K[j] != L[len(L)-1]: #ダブり解消 L.append(K[j]) dp = [0]*len(L) dp[0] = 1 #最初は1通りからスタート used = [-1]*(max(L)+1) #used[i] == iとする（1インデックスぽい） used[L[0]] = 0 #リストの最初の数字を見た for i in range(1,len(L)): if used[L[i]] == -1: dp[i] = dp[i-1] else: dp[i] = (dp[i-1]+dp[used[L[i]]])%(10**9+7) used[L[i]] = i print(dp[len(L)-1])
ABC113D
あみだくじの問題
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは何通り作れますかという趣旨の問題
まず、この問題を解くうえで一番重要なのは、「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
高さh、棒jに至る経路の総数をdp[h][j]とすれば、高さh-1からこの位置に至ることができるのは、棒j-1,j,j+1のいずれかしかない
さらに、そこに至る経路数というのは結局「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
例えば、dp[h-1][j]を見てみる これは、同じ棒から下ってくることを意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」ということである
つまり、この高さにおける横棒の架かり方というのは「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の二パターンしかないということになる
ある高さにおける横棒のかかり方も漸化式で求められる 高さhにおける(横一列にかけ橋が並んでいる状況を考える）、n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)
と書くことができる
これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである
だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、j-1本の棒の間にかかる橋の場合の数f(j-1)と、W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる これと同様に、残り二本に対してもいくつかければよいかを考えて、dp[h][j]]に対する漸化式を立てればよい
以下はpython3による解答
H,W,K = map(int,input().split()) dp = [] for i in range(H+1): #高さ0の分を余分に持っておく L = [0]*W dp.append(L) fb = [1,1] #フィボナッチ（f(n)=f(n-1)+f(n-2)） for i in range(W-2): fb.append(fb[i]+fb[i+1]) dp[0][0] = 1 #左端の棒の高さ0は初期位置なので1に if W != 1: #棒が一本以上あるときは for i in range(1,H+1): for j in range(W): #棒が左端、右端、それ以外で場合分け if 1 <= j <= W-2: dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2] elif j == 0: dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2] else: dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2] else: dp[H][0] = 1 print(dp[H][K-1]%(10**9+7)) #高さH（一番下）、K-1番目の棒を調べる
EDPC H
迷路の経路の総数（右、下移動のみ）を求めるときにDPが使える
