半年ぶりにTDPCを全部埋めたので、個人用の解法メモを残しておきます。
問題に言及しますから、特にTDPCを今後解く予定の方はご了承ください。
使用言語はPythonです。
Typical DP Contest
A コンテスト
問題文はこちら
N個の数字からいくつか選びます。総和は何通りですか。
解法
PAST中級本に載っています。
DP[i][s]: i問目を解いた時点で、合計得点をsにできればTrue
で1年前は解いていましたが、雑にsetに入れても解けます。
B ゲーム
問題文はこちら
2つの山の上からものを取ります。先手番が得る最大価値を求めてください。
解法
山の上側は入力の左側です。
たとえばA: 1 2 3 4 5のとき、山Aの一番上のものの価値は1です。
DP[a][b]: (山A,山B)の残り個数が(a,b)のとき、先手番が得られる最大価値
現在の手番は (N+M)%2 == (a+b)%2 で判定できます。
C トーナメント
問題文はこちら
レートと勝率計算式を与えます。各人の優勝確率を求めてください。
解法
セグメント木めいた完全二分木を作り、下から上に更新します。
DP[i]: 部分木iについて、(人, レート, ここまで勝ち残る確率) のリスト
と定義し、左側から勝ち上がる人々と右側からの人々を戦わせてみましょう。
DPサイズを$2^{K+1}$、初期化は DP[i+pow(2,K)] = (i, Ri, 1) として、下側からforループを回せばよいです。
最終的に、各人の優勝率はDP[1]に格納されます。
DP[i][j]: 人iがj連勝する確率
と定義しても解けます。人iがj連勝しているとき、次の対戦相手kは
(i>>j<<j)^(1<<j) <= k < ((i>>j<<j)^(1<<j))+(1<<j)
の範囲から決まるようです。
提出例: 二分木, bit演算
D サイコロ
問題文はこちら
N回のサイコロの積がDの倍数になる確率を求めてください。
解法
$D=2^A × 3^B × 5^C$ と素因数分解しておきます。
DP[i][a][b][c]: サイコロをi回投げた時点で、積が 2^a * 3^b * 5^c となる確率
として、iの昇順にDPを埋めましょう。
DPテーブルが大きすぎるとMLEするので、各因数の次数で丸めましょう。
メモ化再帰でも解けます。
DP[i][a][b][c]: サイコロをi回投げた時点で、積が2^a * 3^b * 5^c のときの勝率
として、DP[x][A][B][C] = 1, DP[N][x][x][x] = 0 とします。
非再帰メモ化再帰で解く場合、Kiriさんの方式が便利です。
ただし、一回の再帰に必要な再帰量が増えるほど非再帰が不利になります。
提出例: forループ(132ms), メモ化再帰(144ms), 非再帰再帰(153ms)
E 数
問題文はこちら
N以下の正整数のうち、桁和がDの倍数となるものの個数を求めてください。
解法
DP[i][d][f]: 下位i桁目の桁和がd(mod D)で、現状N以下なら f=True の個数
として桁DPをします。下位の桁から決めるときは竹DPとも言うらしいです。
fはよく未満フラグと呼ばれますが、理解しづらかったので図を残します。
N : 6 7 8 9 のとき、3桁目を決めたときの遷移を考えます。
N(3): 7 8 9 特に、N(x)でNの下位x桁の数字 という意味で使います。
-----------------
9 x x
8 x x : 3桁目が8以上の場合、確定でN(3)を超えます。
7 9 0 : 3桁目が7の場合、N(2)との大小関係で決まります。
7 8 9 : 2桁目が89以下なら、3桁目が7でもN(3)以下です。
6 x x : 3桁目が6以下の場合、確定でN(3)以下です。
5 x x
F 準急
問題文はこちら
駅1から駅Nまで、連続K駅以上に止まらず移動する場合の数を求めてください。
解法
ここから急に難しくなります。
余事象数え上げをします。駅1から駅Nまで、 連続K駅以上に止まり 移動する方法を数えることにします。
まず、駅1と駅Nに止まる制約を無視した部分問題を考えます。
駅1と駅Nに止まらなくてもよいが、連続K駅以上に止まる場合
DP[i]: 総駅数がi駅ちょうどで、連続するK駅以上に止まるパターン数
と定義します。DPの計算は、$1\leq j\leq i-K+1$に対して「駅jから、はじめてK駅以上連続で止まる場合の数」の総和を取って求めます。
停車駅をo, 通過駅をx, どちらでもよい駅を?で表します。
はじめてK駅以上連続停車する駅jを全探索しましょう。
j=1 ooo????? j = 1 のとき、場合の数は 2^5 通りです。
j=2 xooo???? 2 <= j <= i-K+1 のとき、場合の数は 2^4 通りです。
j=3 ?xooo???
j=4 ??xooo??
j=5 oooxooo? ただし、特に j>K+1 のときはj駅目より前にK駅連続で
j=6 ????xooo 止まる配置にできるので除外しましょう。
$j>K+1$のとき、駅jより左側の?がj-2個、右側の?がi-K-j+1個あります。
従って左側の並べ方総数は$2^{j-2}$通りですが、うち制約違反(この区間でK駅以上連続して止まる場合)がDP[j-2]通りあります。
以上を踏まえると
DP[i] = \begin{cases} 0 & (i<K) \\ 1 & (i=K) \\ 2^{i-K} + \sum_{j=2}^{i-K+1}(2^{j-2}-DP[j-2])×2^{i-K-j+1} & (i>K) \end{cases}
となります(便宜上、DP[0]=0とします)。$i>K$の部分を整理して
DP[i] = 2^{i-K} + (i-K)×2^{i-K-1} - \sum_{j=0}^{i-K-1}(2^{i-K-j-1}×DP[j])
残ったΣの部分(DP[i]の制約違反数)をS[x]( x = i-K-1 )とすると、
S[0] = DP[0]=0, S[x] = 2×S[x-1] + DP[x]
が成り立ちます。DP[i]とS[i]の計算は同時に行えるので、結局
DP[i] = \begin{cases} 0 & (i<K) \\ 1 & (i=K) \\ (i-K+2)×2^{i-K-1} - S[i-K-1] & (i>K) \end{cases}
となります。DP遷移は$O(N)$です。
2の冪乗は前計算すれば$O(N)$・楽してpow関数に投げても$O(NlogN)$です。
S[x]の図示
具体例のほうがわかりやすいです。
DP[7] ooo???? 前半の?でK駅以上止まる制約違反の個数は
xooo??? DP[0] * 2^3 +
?xooo?? DP[1] * 2^2 +
??xooo? DP[2] * 2^1 +
???xooo DP[3] * 2^0 = S[3]
DP[8] ooo?????
xooo???? DP[0] * 2^4 +
?xooo??? DP[1] * 2^3 +
??xooo?? DP[2] * 2^2 +
???xooo? DP[3] * 2^1 + ･･･ ここまでで S[3] * 2
????xooo DP[4] * 2^0 = S[4]
$S[4] = 2×S[3]+DP[4]$が成立しています。(終)
駅1と駅Nに止まり、連続K駅以上に止まる場合
部分問題のDPが求まっていれば、包除原理で解けます。
N駅中K駅以上連続して止まる場合の数であって、
[a] 駅1は自由・駅Nは自由のもの : DP[N]
[b] 駅1は通過・駅Nは自由のもの : DP[N-1]
[c] 駅1は自由・駅Nは通過のもの : DP[N-1]
[d] 駅1は通過・駅Nは通過のもの : DP[N-2]
とすると、求める場合の数は [a] - ([b]+[c]) + [d] です。
駅1と駅Nに止まり、連続K駅以上には止まらない場合
本来の問題です。
(A)駅1と駅Nに止まり、残りN-2駅は自由に選ぶ場合の数 : $2^{N-2}$
(B)駅1と駅Nに止まり、連続K駅以上に止まる場合の数
とすると、求める場合の数は(A)-(B)です。
よって、 $2^{N-2} - (DP[N] - 2×DP[N-1] + DP[N-2])$ が答えです。
提出例
G 辞書順
問題文はこちら
文字列Sの非空部分列のうち、辞書順でK番目のものを求めてください。
解法
突出して難しいです。MLE解を作ってから高速化しましょう。
以下、N=len(S)とします。
愚直解法
DP: S[i]までで作れる文字列の集合
計算量は$O(2^N)$です。とりあえず書きました。
愚直解 コード
#入力受取
S=input(); K=int(input())
#TDPC-A コンテスト の要領でDPを更新
DP=set(); DP.add('')
for now in S:
newDP=set()
for word in DP: newDP.add(word+now)
DP|=newDP
#K番目の値を出力 DP[0]='' である点に注意
DP=sorted(DP); print(DP[K] if K<len(DP) else 'Eel')
MLE解法
典型006の再発明を行います。
たとえば S: abacのとき、部分列として13通りあり得ます。
($2^4$通りから、空文字列と、aとacの重複ぶんを減らした場合の数です)
この部分列数え上げは、文字列の後ろから貪欲マッチングを行えばできそうです。
以降、 1-indexed で扱います。
DP[i]: S[i:]で作れる部分列の個数のうち、S[i]をかならず使うものの集合
として、遷移例を書いてみます。
S : a b a c DP[4] = 'c'
a a _ a _ DP[3] = 'a', ['ac']
b _ b _ _ DP[2] = 'b', ['ba','bac'], ['bc']
c _ _ _ c DP[1] = 'a', ['aa','aac'], ['ab','aba','abac','abc'], ['ac']
DP[1] ← 'a', 'a'+DP[2], 'a'+DP[3], 'a'+DP[4]
という遷移規則を取ると、はじめてa, b, c, ･･･ が現れるものの和集合が
DP[1] | DP[2] | DP[4] = ('abac'の非空な部分列)
と一致します。
さらに考えると、この遷移規則なら集合ではなく個数を格納しても復元できます。
S : a b a c 接頭辞が'a' : 8個 → 1～8番目は'a'からはじまる
a 8 _ 2 _ 接頭辞が'b' : 4個 → 9番目は'b'で確定
b _ 4 _ _ 接頭辞が'ba' : 2個 → 10～11番目は'ba'からはじまる
c _ _ _ 1 接頭辞が'bb' : 0個
接頭辞が'bc' : 1個 → 12番目は'bc'で確定
以上の考察をDPに落とします。(DPの定義を変更します)
DP[i][s]: S[i:]のうち、頭文字がsからはじまるものの個数
Ps[i][s]: S[i]より後ではじめて現れる、文字sのindex
のふたつの配列を用意し、事前に後ろからDP計算をします。
DP内の値は解の復元に必要な範囲だけ保持すればよいので、Kを超過するものはK+1や$10^{18}+1$に丸めます。しないとTLE・MLEします。
解の構築は S[0]='' とみなし、辞書順で小さい文字から順に貪欲マッチを行います。既に辞書順で小さいことが確定した個数と、最後に採用した添字を保持して頑張りましょう。
時間計算量・空間計算量はともに$Θ(wN)$です。
提出例: MLE(1570ms, 660MB)
AC解法
MLE解法を省メモリ化します。
解の個数を保持するDPと、次の文字の位置を保持するPsを一次元化します。
解の構築は前から行うので、S[i]に来たときに直前のDP値を復元できればそれで十分です。
S[i]に到達したときに更新したい内容は、この2つです。
- DP[i+1][s] : S[i+1:]以降で、頭文字がS[i]からはじまる文字列の個数
- Ps[i][s] : S[i+1:]以降で、文字S[i]がはじめて出現する位置
下処理の段階でこの2個を別配列に格納し、尺取法で格納した値を回収・更新することにしましょう。
これで時間計算量が$O(wN)$(w: wordsize = 26)、空間計算量が$Θ(N)$に改善するのでACします。
ちなみに、尺取法の際に最後に拾った文字の位置を更新し忘れると、正解を出力する$O(wN^2)$のTLEコードが完成します。
本当にデバッグが大変でした。皆様もご注意ください。
提出例(510ms, 140MB)
H ナップザック
問題文はこちら
「荷物の色はC種類以下」の制約つきナップサック問題を解いてください。
解法
DP[i][c][w]: i種類目の色まで見て、既に色をc種類使ったとき、重さがwの最大価値
とします。荷物は色ごとにdefaultdictにしまっておきます。
- i種類目の色を使わない場合
DP[i][c][w] ← DP[i-1][c][w] - i種類目の色を使う場合
部分問題として、この色内でナップサック問題を解きます。
sub[j][c][w]: j番目の荷物まで見て、色をc種類使ったとき、重さがwの最大価値
初期化は「この色を使う」と決めた時点で1色増やしたとみなし、
sub[0][c][w] ← DP[i-1][c-1][w]とします。
あとはよくあるナップサックDPを行い、得た解を
DP[i][c][w] ← sub[-1][c][w]で反映させればよいです。
実装上はメモリ削減のため、部分問題のDPは二次元配列化が必須です。
重さが大きい側からsub配列の更新を行いましょう。提出例
I イウィ
問題文はこちら
iwiwii のようなi, wの文字列から、iwiを消せる最大回数を求めてください。
解法
PAST上級本に載っています。
DP[L][R]: S[L:R]から'iwi'の除去をしたときの最短文字列長
の区間DPを行います。
i---w---iのパターンは全消しか全残りかの二択なので注意。
非再帰メモ化再帰でも解けますが、方針次第では破滅します。
しかも普通にdef文で書くメモ化再帰よりもかなり遅いです。避けましょう。
提出例: forループ(197ms) , メモ化再帰(244ms) , 非再帰おすすめ版(448ms)
J ボール
問題文はこちら
ボールの左右ブレを考慮して、N本のピンを倒しきる期待値を求めてください。
解法
制約上$N\leq 16$なので、先に$2^{16}$個のbitDPを前計算しましょう。
DP[S]: ピンの位置が2進数表記でSのとき、ここから全部倒しきるための期待値
とします。各Sに対して、ボールを投げる位置を全探索します。
ボールを投げた後のピン状態をそれぞれ T, U, V とすると
DP[S] = \dfrac{DP[T]+DP[U]+DP[V]}{3}\\+1
となります。
ハズレ(DP[S]への遷移)がself個ある場合、ハズレの期待値を0として
\dfrac{3-self}{3}\\DP[S] = \dfrac{DP[T]+DP[U]+DP[V]}{3}\\+1
です。あとは投擲位置の全探索結果のうち、最良のものを採用してDPを埋めましょう。
K ターゲット
問題文はこちら
円列Cのうち、大円が小円を内包する円集合の最大サイズを求めてください。
解法
円の左端でソートすると、円の右端側が単調減少となる最長の部分列を求める問題になります。
これはLIS(最長増加部分列)のアルゴリズムを知っていれば解けます。
セグメント木に乗せるのが楽ですが、二分探索でも解けるようです。
提出例: SegTree
L 猫
問題文はこちら
近いと$f_{ij}$だけ幸福になる猫達の、幸福度総和の最大値を求めてください。
解法
猫iと距離1以内にいる最左の猫を猫jとすると、
猫i+1は距離1以内の最左の猫を、猫j～猫i+1から選べます。
DP[i][j]: 猫iまで決めたとき、猫iと距離1以内で最左が猫jのときの最大幸福度
として、DP[0][0] = 1 で初期化しましょう。
DP[i][j] ← max( DP[i-1][k] + sum(F[i][j:i]) for k in range(j+1) )
となるので、このままではfor i,j,kの$O(N^3)$です。
しかしsum(F[i][j:i])の部分がkによらない点に注目して
DP[i][j] ← max(DP[i-1][:j+1]) + sum(F[i][j:i])
と変形すると、maxの項はDP[i][j]の更新と並行処理ができます。
sumの項はFの累積和を$O(N^2)$で前計算すればよいです。
提出例
M 家
問題文はこちら
同じ部屋を通らず、コピペ館のH階から1階に降りる経路数を求めてください。
解法
PAST上級本に載っています。
DP[i][S]: 現在地が部屋iで、通過済の部屋が2進数表記でSとなる場合の数
の巡回セールスマン問題を解くことで同階移動の経路数を求めておき、H回の階段移動部分は行列累乗で高速化しましょう。
計算量は$O(R^32^R + R^3logH)$です。
行列累乗をnumpyで行う場合、メモリ制限に注意してください。
numpy 行列累乗とメモリの話
2023年夏のAtCoder言語アップデートでPyPy3でもnumpyが使えるようになりました。
しかしこれが曲者で、メモリを食いまくったりオーバーフローしたりと一筋縄ではいきません。
大変ですが、自作の行列累乗ライブラリを作ることをおすすめします。
行列累乗ライブラリ(自作)
自作なのでバグがあると思います。(終)
#行列累乗 1行N列の行列は[[1, 2, ...]] と2重括弧に自動変換するので注意
class matrix_pow:
def __init__(self,MOD=998244353): self._MOD=MOD
def eye(self,N): #単位行列の作成
return [[1 if i==j else 0 for j in range(N)] for i in range(N)]
def add(self,A,B): #行列の加算
if isinstance(A[0],int): A=[A]
if isinstance(B[0],int): B=[B]
assert len(A) ==len(B), 'not same size'
assert len(A[0])==len(B[0]), 'not same size'
nG=[[0]*max(len(A[i]) for i in range(len(A))) for _ in range(len(A))]
for h in range(len(nG)):
for w in range(len(nG[h])):
if len(A[h])<w: nG[h][w]+=A[h][w]
if len(B[h])<w: nG[h][w]+=B[h][w]
nG[h][w]%=self._MOD
return nG
def mul(self,A,B): #行列積 L行M列 * M行N列 = L行N列
if isinstance(A[0],int): A=[A]
if isinstance(B[0],int): B=[B]
assert len(A[0])==len(B), 'cannot calcurate'
nG=[[0]*max(len(B[i]) for i in range(len(B))) for _ in range(len(A))]
for h in range(len(nG)):
for w in range(len(nG[0])):
for x in range(len(A[0])):
nG[h][w]+=A[h][x]*B[x][w]%self._MOD; nG[h][w]%=self._MOD
return nG
numpy 行列累乗の罠
numpyはデータ型を選べますが、object型にしないと一瞬で壊れます。
import numpy as np
MOD=998244353
#int64(符号あり64ビット整数型)の場合
A=np.array([MOD-1]*10, dtype='int64')
B=np.array([[MOD-1] for _ in range(10)], dtype='int64')
print(A@B) #array([-8481826210710552576], dtype=int64)
#uint64(符号なし64ビット整数型の場合
score=[]
for N in [18,19]:
A=np.array([MOD-1]*N, dtype='uint64')
B=np.array([[MOD-1] for _ in range(N)], dtype='uint64')
score.append((A@B)[0])
print(score) #[17936852153398198272, 486599865988546560]
print(score[0] < score[1]) #False
とはいえデータ型を制限すれば早くなる、というわけでもないようです。
numpyは難しいですね。(終)
提出例: int64(2726ms, 270MB), uint64(2781ms, 270MB), object(2736ms, 290MB)
numpy メモリの罠
numpyで行列累乗を行うと、なぜかやたらとメモリを食います。
提出例: 自作ライブラリ(2247ms, 220MB), numpy(2751ms, 290MB)
現代のAtCoderではメモリ制限が大抵1024MBなので大丈夫ですが、過去問やJOIを埋めるときは省メモリ化が必要になるかもしれません。
numpyを避けて自作の行列累乗を使うことが一番ですが、それ以外の部分で省メモリ化を行う方法を考えましょう。
実験したところ、メモリは配列を宣言するたびに消費するようです。
なのでリストの宣言を減らし、既存のリストを使い回すことで省メモリ化できます。
提出例: 毎回DPを宣言(290MB), del DP(290MB), ゼロ配列で初期化(290MB), ゼロ代入で初期化(170MB)
#毎回DPを宣言(MLE), del DP(MLE)
for start in range(R): #最初の部屋を決めて巡回セールスマン問題
DP = [[0]*(1<<R) for _ in range(R)] #DPを宣言
#ここで問題を解く
del DP #ほぼ意味なし
#ゼロ配列で初期化(MLE)
DP = [[0]*(1<<R) for _ in range(R)] #事前にDPを宣言
for start in range(R):
#forループの開始前に初期化
for i in range(R): DP[i] = [0]*(1<<R) #毎回ゼロ配列を宣言している？
#ゼロ代入で初期化(AC)
DP = [[0]*(1<<R) for _ in range(R)]
for start in range(R):
for i in range(R):
for S in range(1<<R): DP[i][S] = 0
そのぶん実行時間は悪化するので、メモリ制限と比べながら実装しましょう。(終)
N 木
問題文はこちら
Prim法で全域木を描く方法は何通りありますか。
解法
最初に描く辺を決めて、辺を持ち上げてみましょう。
すると両端から部分木がぶら下がる形になり、急に木DPで解ける見た目になります。
今回のようにすべての辺・すべての頂点について解が必要な場合、全方位木DPを行うとよいです。
最悪行わなくてもよいです。
木DP
$N \leq 10^3$なので、$O(N^2)$でも余裕を持って間に合います。
最初に描く辺を固定すると、両端の頂点を根とした2つの部分木に対して「辺の追加順の場合の数は？」という部分問題を解けばよいと分かります。
これは子の部分木の(辺の並べ方の総数, 辺の本数)が分かっていれば解けます。
たとえば親から2本の辺が出ており、各辺ごとに(並べ方総数, 辺本数) = $(S_1, E_1), (S_2, E_2)$ だと分かっているとします。
するとこの部分木における辺の書き順の総数は、「互いに区別できない赤玉$E_1$個・白玉$E_2$個を一列に並べてから、赤玉内で$S_1$通り・白玉内で$S_2$通りの採番を行う場合の数」と同義です。
なので ${}_{E_1 + E_2} \mathrm{C} _{E_1} × S_1 ×S_2$ 通りとなります。提出例
全方位木DP
全方位木DPの詳細はkeymoonさんの解説が勉強になりました。
https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
$Θ(N)$で解きます。
各辺ごとに「この方向に辺をたどった先の、(辺の並べ方総数, 辺本数)」を調べ上げ、最後に辺ごとに答えの寄与を調べます。
まず先述の木DPの要領で頂点0を根としたときの解を求めてから、BFS行きがけ順に他の頂点に辺情報を波及させましょう。
この際、「自身以外の辺の結果」が必要になりますが、ここで累積和を使うことで$O(N^2)$から$O(N)$に落とせます。提出例
O 文字列
問題文はこちら
同じ文字が隣接しないよう、アルファベットを並べる方法は何通りありますか。
解法
Kiriさんのユーザ解説の通りです。
DP[s][x]: 文字sまでを挿入したとき、同じ文字の隣接箇所がx個残っている場合の数
とします。次の文字をどこに挿入するか、文字s同士で隣り合う個数がいくつかを全探索します。
- 隣接箇所の減少
挿入前の文字数をSとすると、挿入箇所は(両端を含めて)S+1個あります。
このうち同じ文字の隣接箇所はx箇所で、ここに挿入することで隣接個数が減少します。
文字sを挿入する箇所をk箇所、k個のうちL個はx個ある隣接箇所に挿入することとすると、寄与は$ {}_x \mathrm{C}_L × {} _{S+1-x} \mathrm{C} _{k-L} $です。 - 隣接箇所の増加
文字sを挿入する箇所をk箇所とすると、F[s] - k 個は文字sの隣に挿入することになり、そのぶん隣接箇所が増加します。
k箇所の挿入箇所に、ボールを合計F[s]-k個入れる場合の数を考えればよいです。
k箇所の挿入箇所をk-1個の仕切りと考えればよく、結局寄与は$ {} _{(k-1) + ( F_s -k )} \mathrm{C} _{k-1} $です。
計算量は$O(w × max(F)^2 × sum(F))$ (w: wordsize = 26)です。提出例
P うなぎ
問題文はこちら
木にK本の非連結パスを書く場合の数を求めてください。
解法
URLの tdpc_eel のeelって「うなぎ」の意味なんですね。
木にK本の「うなぎ」を並べる方法を数える問題です。
ただしうなぎ同士でまたいだり、頭と尻尾が他のうなぎに触れてはいけません。
DP[i][k][f]: 頂点iを含む部分木において、うなぎの本数がk本、頂点iをまたぐ辺がf本の場合の数
として木DPをします。特に頂点iのうなぎの通過状態で場合分けが必要です。
f = 1 ならうなぎの頭か尻尾が頂点iにあり、f = 2 ならうなぎが頂点iをまたぎます。
遷移は辺ごとに「頂点iにうなぎをのばす or のばさない」がありえて、さらにfの値ごとに採用したうなぎの本数が変化します。
場合分けが複雑なので、補助配列を定義したほうが整理できると思います。
sub[j][k][f]: 頂点iのj番目の辺までで、採用したうなぎがk本、頂点iで止まるうなぎがf本の場合の数
とすると、部分ナップサック問題に帰着できます。
計算量は$O(NK^2)$です。提出例(587ms)
(追記)
マージ時に部分木のサイズを超えたら打ち切れば、$O(NK)$です。
原理はsnukeさんのブログが詳細です。提出例(151ms)
Q 連結
問題文はこちら
N個の01列の組み合わせで、長さLの文字列を作る場合の数は何通りありますか。
解法
Kiriさんのユーザ解説の通りです。
DP[i][S][T]: 文字列全長をi, 直近8文字の末尾がS, 直近9箇所の仕切り状態がTの場合の数
とします。この定義だと末尾と仕切り状態が1文字ぶん余計なので、合計で計算量が4倍悪化しますが間に合います。
DPの遷移ルールは、「手前の仕切りからマッチする文字列があれば、かならず仕切りを加える」とします。
[o]は良い遷移例、[x]は悪い遷移例を示します。
[o] 00000000| 初期状態は S=0, T=1(0文字前だけが仕切られている)。
[o] 000000|1 1| 11と追加すると、ちょうどマッチしたので仕切りを追加。
[o] 00000|1 1|1 111 だとマッチしないので仕切りは足さない。
[x] 00000|1 1|0 110 の遷移を考える。|11|0 と考えると遷移はできないが･･･
[o] 00000|1 1|0| ひとつまえの仕切り、|110 を見ると遷移ができた。
[x] 00000|1 1 0| 仕切りは「マッチしたなら必ず入れる」ルールなので、これはNG。
[o] 000|1 1|0|1 1| 11011とマッチするのはこの形になる。
[x] 000|1 1 0|1 1| 110 + 11 だからといって、このような仕切りになったり･･･
[x] 000|1 1 0 1 1| 11011 だからといって、このような仕切りにしてはいけない。
S,Tの組ごとに、次の末尾が0と1のときの遷移先の前計算が必要です。
bit演算で処理できますが、2進数で処理する際は1と01が同じ1として処理されないよう、桁数ごとに分けるか文字列型での比較を行いましょう。
この実装の場合、計算量は$O(L × 2^{2M+2})$(M: 最大文字列長 = 8)です。
提出例: 末尾8文字を保持(1108ms)
R グラフ
問題文はこちら
有向グラフを2回通ることで通過できる頂点数は最大で何個ですか。
解法
フローで解きました･･･。
最初にSCCを行い、重み付きのDAG(サイクルがないグラフ)にします。
SCC 実装方針
numpyとscipyを用いたSCCが簡潔です。
KosarajuのアルゴリズムはDFSが2回必要ですが、実装が簡単です。
非再帰DFSで書くと実行速度も多少マシになります。
https://manabitimes.jp/math/1250
Tarjanのアルゴリズムであれば、DFS1回で済むので高速です。
非再帰にするとLibrary Contestで1000ms切りを達成できるようです。
いつか実装したいです。(終)
SCCのグループごとに頂点数で重み付けし、新しくグラフを作り直します。
その後は頂点を倍加し、重み付きグラフに流量2のフローを流せばよいです。
これは最小費用流のアルゴリズムを正負反転して行うことで達成できます。
具体的には流量1・コストが頂点数の辺と、流量1・コスト0の辺を1本ずつ、入頂点→出頂点 の方向に張ればよいです。提出例
S マス目
問題文はこちら
H行W列のグリッドを数え上げお姉さん塗りする場合の数を求めてください。
解法
数え上げお姉さんについては日本科学未来館のサイトをご覧ください。
実装の都合上、H「列」W「行」の縦長のマス目を考えます。
1行ごとのマス目の状態で場合分けします。
塗り方の状態ごとの接続可否を前計算で判定しておけば、あとは行列演算をW回行えば答えが出せます。
問題は塗り方の状態数と接続の列挙の部分です。ここが大変です。
$H \leq 6$の制約から、H列のマス目の状態数は高々4個です。
0. 塗らない
1. 塗られており、かつ左上のマスと連結
2. 塗られているが、左上のマスと非連結
3. 塗られているが、1. , 2. のどちらとも非連結
この4状態を4進数表記やtuple型で管理しましょう。
1を含まない状態は常に非連結になるので除去してよいです。
塗り方を決めたときの遷移判定はBFSで可能です。
1マス以上が塗られる$2^H -1$通りを接続してみて、塗り分けた先に遷移すればよいです。
塗り分け結果を座標圧縮する際、0と1を潰さないように注意しましょう。提出例
実装諸注意
初期状態は (1,0,0,0,0) のように、左上だけ塗られているマスを0行目としてみなすと安全です。
代案として「validな状態のうち、左上に1を含むものを状態数1とする」として1行目から遷移開始しても解けますが、この場合は (1,0,2,0,3) と (1,0,3,0,2) で重複しないよう注意が必要です。
遷移判定は以下のパターンを見落としやすいので注意してください。
接続先のマスのうち、塗る予定だが番号が未定のものをxとします。
■塗り残し
接続先に塗り残しがある場合、新しく2,3と採番が必要です。
塗り忘れたまま座標圧縮すると、各番号がずれるのでWAします。
1, 0, 0, 0, 0 : 接続元
1, 0, x, 0, x : 接続先
■塗り忘れ
接続元の連結判定が甘いと、このように「飛び地」の塗り忘れが生じます。
1, 0, 2, 0, 2
1, 1, 1, 0, 2 : 正しくは (1, 1, 1, 0, 1)
メモリ使用量にも注意が必要です。
特にnumpyを使う場合、PyPy3だとAC困難です。
Pythonで提出するか、自作の行列累乗ライブラリを使いましょう。
提出例: numpy PyPy3(4640ms, 340MB), CPython(477ms, 35MB)
T フィボナッチ
問題文はこちら
隣接K項間・Kィボナッチ数列の第N項を求めてください。
解法
行列累乗だとTLEするので、kitamasa法で$O(K^2 logN)に落とします。
kitamasa法はyosupoさんのブログが詳しいです。
現代だとBostan-Mori法のほうが簡潔かつ高速かもしれません。
提出例(kitamasa法)
kitamasa法 個人用メモ
初項を$a_0$とする、0-indexedで考えます。
k項間漸化式の係数を$d_i$とした以下の式を考えます。
$a_i = d_0a_{i-k} + d_1a_{i-k+1} + ･･･ + d_{k-1}a_{i-1}$ ･･･(1)
特に $i = k$の場合が見慣れた形になると思います。
$a_k = d_0a_0 + d_1a_1 + ･･･ + d_{k-1}a_{k-1}$ ･･･(2)
さて、(1)は隣接k項間漸化式なので、再帰的にすべての項を$a_0$から$a_{k-1}$で表現することが可能です。係数を$P_i$とすると、
$a_i = P_{i0}a_0 + P_{i1}a_1 + ･･･ + P_{i(k-1)}a_{k-1}$ ･･･(3)
となります。この係数組を特に$F_i$として管理します。
$F_i = [P_{i0}, P_{i1}, ･･･ , P_{i(k-1)}]$ ･･･(4)
とすると、list型で保持できます。
さて、現在$a_n$の値が分かっており、式として
$a_n = P_{n0}a_0 + P_{n1}a_1 + ･･･ + P_{n(k-1)}a_{k-1}$ ･･･(5)
$F_n = [P_{n0}, P_{n1}, ･･･ , P_{n(k-1)}]$ ･･･(6)
と与えられるとします。
- $a_{n+1}$への遷移
(5)はk項間漸化式なので、$a_i$の添字を一度に1ずらしても成立します。
$a_{n+1} = P_{n0}a_1 + P_{n1}a_2 + ･･･ + P_{n(k-1)}a_k$ ･･･(7)
(7)に(2)を代入すると、$a_{n+1}$を$a_0$から$a_{k-1}$で表現できました。 - $a_{2n}$への遷移
(5)の$a_i$の添字を一度にnずらしても式が成立します。
$a_{2n} = P_{n0}a_{n} + P_{n1}a_{n+1} + ･･･ + P_{n(k-1)}a_{n+k-1}$ ･･･(8)
ここで1. をk-1回行うことで、(8)に含まれる$a_n$から$a_{n+k-1}$までが展開できます。これにより、$a_{2n}$を$a_0$から$a_{k-1}$で表現できました。
以上の遷移を繰り返し二乗法の要領で反復して、求めたい$a_i$の係数組$F_i$を求めればよいです。
なお、本問では$a_0$から$a_{k-1}$までが与えられていますが、他の問題では愚直なDPで求める必要があります。(終)
おわりに
おわりです。
たくさんもんだいがあっておもしろいなとおもいました。