主食は米

主に競プロ備忘録

日経コン 2019 E - Erasure (700)

解法

dp[ i ][ j ] := #( [0,j) のみ消されていて, i-1 開始の区間を列挙し終えた )
として, i 開始の区間を考える.
半開区間で考えているので消す区間 [l,r) の満たす条件は r-l >= K+1.

新しく [0,x) から [0,j) ( x < j ) まで消す場合
[ i, j ) は必ず選ばなければならず, (よって j - i >= K+1 )
残りの [ i, i+K+1 ), ..., [ i, j-1 ) の j-i-K-1 は自由に決められるので
dp[ i+1 ][ j ] += ( sum _ { i <= x < j } dp[ i ][ x ] ) * 2j-i-K-1

一方, dp[ i ][ j ] から dp[ i+1 ][ j ] に遷移する場合は
i から始まる区間が j を超えてしまう場合( j < i+K+1 )は
dp[ i+1 ][ j ] += dp[ i ][ j ]
超えない場合は [ i, i+K+1 ), ... , [ i, j ) を自由に選べるので
dp[ i+1 ][ j ] += dp[ i ][ j ] * 2j-i-K

これを単に累積和で処理してやればいい.

メモ

簡単なはずなんだけどこんがらがってしまった..

コード

ARC 094 F - Normalization (700)

解法

n文字からなる文字列の変換の典型として,
'a' -> 0, 'b' -> 1, 'c' -> 2 に変換して総和のmod3に注目する

この場合でも総和のmod3は保存されることがわかる.

この非自明な必要条件が本質.
更に実験すればわかるが,1回以上の操作によって a[i] == a[i+1] なる i ができる.

ここまで得た必要条件を列挙すると,できうる文字列は
(1) mod3 の総和が s と等しい (2) 1回以上の操作を経由すると a[i]==a[i+1] なる i がある
となる.
後は 必要条件を列挙が実は必要十分条件になっている というAtCoderの典型パターン.
実は (1) (2) を満たす文字列は N>=4で全部作ることができるらしい(証明してない)

後はDPで数え上げる. dp[ i ][ j ][ k ][ l ]
:= ( i 文字からなる文字列で, j=1なら(2)を満たすi'が存在し, 末尾の文字がk, 総和mod3がl ) として, 次の文字によって遷移する. O(N).

メモ

これすごい.

DPでやろうとしたら無理なのには気づいた. 例えば両端の文字を持っておいて区間dpをやろうとしても [l,x) と [x,r) -> [l,r) と遷移した後でも, s[x],s[x+1] を変化させたら再び [l,x) の範囲で操作ができるようになる可能性がある.
なのでこの方針は諦めてできる文字列の必要条件を列挙するべきだった.

コード

KEYENCE Programming Contest 2019 D - Double Landscape

反省

解法は解説見ればわかるのでなんで反省点のみ.

  • {a}, {b} をsortして右下から入れていこうとしていた

-> 明らかに煩雑. 典型要素として perm を考えるときには挿入/数字が入る場所から決めていく
-> 上の数字から入れていくのを

  • a_i = b_j = x なる i, j があるならば (i, j) は一意に定まる

-> これは実験でわかった.

  • 上から入れていく

-> これは考察できていたけどふわっとしていた.
x が入ることができるマスは y (<x) も入ることができる単調性があることを考えるとこれしかなさそう
ただし, y が一意に定まる a_i = b_j = y なる i, jが存在しないケースに限る(これのせいで混乱した)

まとめ

順列は数字の入る場所から考えていく
ただし単調性があるような順番に入れていくのが良い.
今回のような入ることのできる場所を掛けていくような場合には,
入れる候補が今まで入れた場所を含んでいるという性質が重要.

Educational DP Contest / DP まとめコンテスト 復習

メモ

17完. 解けない問題いっぱいあるなあ
集めるDPの方がバグらせにくくて(当社比),メモ化にもしやすいのでほぼそっちで書いた.
簡潔なまとめはプロのツイッターを見るのが良い.

A

dp[ i ] := min( dp[i-1] + cost(i-1,i), dp[i-2] + cost(i-2,i) )
cost(i,j) = abs( h_i - h_j )
O(N).

Submission #3936500 - Educational DP Contest

B

dp[ i ] := min_{ i-K <= j < i } ( dp[ j ] + cost(j,i) )
cost(i,j) = abs( h_i - h_j )
O(NK).

Submission #3937040 - Educational DP Contest

C

dp[ i ][ j ] := max( 現在 i-1 日目 で 前日に j 番目の活動をした時の幸福度 )
dp[ i ][ j ] = max_{ k != j }( dp[ i-1 ][ k ] + h[ i ][ k ] )
h[ i ] = { a_i, b_i, c_i }
O(N).

Submission #3937463 - Educational DP Contest

D

dp[ i ][ j ] := max( i-1 番目まで入れるか決めて重さ j の時の価値の総和) dp[ i ][ j ] = max( dp[ i-1 ][ j ], ( j - w_i >= 0 ? dp[ i-1 ][ j - w_i ] : -INF) )
O(NW).

Submission #3937463 - Educational DP Contest

E

dp[ i ][ j ] := min( i-1 番目まで入れるか決めて価値 j の時の重さ)
dp[ i ][ j ] = min( dp[ i-1 ][ j ], ( j -v_i >= 0 ? dp[ i-1 ][ j -v_i ]: INF ) )
O(N sum(v_i )).

Submission #3938707 - Educational DP Contest

F

N = |s|, M = |t|
dp[ i ][ j ] := max( s[0,i) , t[0,j) の LCS(最長共通部分列) )
dp[ i ][ j ] = max( dp[ i-1 ][ j ], dp[ i ][ j-1 ], dp[ i-1 ][ j-1 ]+ (s[ i-1 ] == t[ j-1 ] ? 1 : 0) )

復元は dp[ N ][ M ] からスタートして ans = (空文字列)とし,
今 dp[ i ][ j ] を見ているとして
if s[ i-1 ] == t[ j-1 ] ans += s[ i-1 ]
else ( i-1, j-1 ), ( i-1, j ), ( i, j-1 ) のうち dpが等しい所に遷移.
i-1 < 0 or j-1 < 0 になったら ans を reverseして終了.
dp[ i-1 ][ j-1 ] + 1 == dp[ i ][ j ] でも s[ i-1 ] == t[ j-1 ] とは限らないので注意 (他の所から遷移してきたかもしれない)
O(NM).

Submission #3940676 - Educational DP Contest

G

dp[ u ] := max( uに至るパスの総長 )
トポロジカルソートをしてその順に
dp[ u ] = max( dp[ u ], dp[ v ] + 1 ) if v->u のパスが存在
さすがに配るDPの方が自然な気がする.
O(N).

Submission #3941322 - Educational DP Contest

H

dp[ i ][ j ] := sum( ( i, j ) に至る経路 ) dp[ 1 ][ 1 ] = 1, ans は dp[ H ][ W ]
if ( i, j ) が壁でない dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ]
else dp[ i ][ j ] = 0
O(HW).

Submission #3941908 - Educational DP Contest

I

dp[ i ][ j ] := prob( i 枚目まで投げて j 回表)
dp[ i ][ j ] = p * dp[ i-1 ][ j-1 ] + (1-p) * dp[ i-1 ][ j ]
dp[ 0 ][ 0 ] = 1
ans = sum{ i > floor(N/2) } ( dp[ N ][ i ] )
テストケース,結構誤差とかに気を使いそう.(こどふぉだとmodでやるよね)
O(N2).

Submission #3942299 - Educational DP Contest

J

dp( i, j, k ) := ( 寿司が1,2,3個乗った皿が i, j, k 枚あるまでの期待値 )
次に1,2,3,0個乗った皿をとる確率をp,q,r,sとすると
p = i / N, q = j / N, r = k / N, s = 1 - ( p + q + r )
p,q,r,s それぞれの確率で,その後に何回かかるかの期待値は
dp( i-1,j,k ), dp( i+1,j-1,k ), dp( i,j+1,k-1 ), dp( i,j,k ) になり,
それぞれで必ず1回は試行が増加するので
dp( i, j, k ) = p * dp( i-1,j,k ) + q * dp( i+1,j-1,k ) + r * dp( i,j+1,k-1 ) + s * dp( i,j,k ) + 1
の式が成り立つ.
dp( i, j, k ) の項を移行してメモ化再帰で解く
一瞬ループがないか気になってしまうが, まあよく考えればないことがわかる
期待値漸化式は けんちょんさんのブログ

Submission #4704505 - Educational DP Contest

K

a_i は1回しか使えないのかと誤読していた.
dp[ i ][ j ] := ( i 個石が残っている, j = (先手番 ?) の時、値が1なら先手勝ち )
として再帰してやればいい.
O(K).

Submission #4095737 - Educational DP Contest

L

dp[ i ][ j ] := ( a[ i, j ) からゲームを始めた時の得点. j - i = N mod 2 なら先手番なのでmax, 後手番ならmin )

if 先手番 dp[ i ][ j ] = max( dp[ i-1 ][ j ] + a_i, dp[ i ][ j-1 ] + a_j )
else dp[ i ][ j ] = max( dp[ i-1 ][ j ] - a_i, dp[ i ][ j-1 ] - a_j )

O(N2).

区間DP/ゲームはメモ化がやりやすいね

Submission #3945707 - Educational DP Contest

M

dp[ i ][ j ] := sum( i 人までに j 個を配る )
dp[ i+1 ][ j + k ] += dp[ i ][ j ] ( 0 <= k <= a_i )
そのままやると O(NK2) でTLEなので imos法を使う.
(集めるDPなら累積和)
O(NK).

Submission #3946111 - Educational DP Contest

N

dp[ l ][ r ] := min( [ l, r ) スライムを合体させるコスト )
最後に [ l, x ) と [ x, r ) から各々できるスライムを合体させるとしたら,
各々は a[ l, x ) , a[ x, r ) なので
dp[ l ][ r ] = min_{ l < x < r} ( dp[ l ][ x ] + dp[ x ][ r ] + a[ l, x ) + a[ x, r ) )
aは累積和をとっておこう.
O(N3).

Submission #3947535 - Educational DP Contest

アルゴリズムイントロダクションに乗ってる連鎖行列積とほとんど一緒だなあと思った.
このスライドの44ページ目から.

O

dp[ i ][ s ] := ( i 人目までの男性をマッチングさせて, 女性集合 s が残っている )
dp[ i ][ s ] = sum_{ j in s } ( dp[ i-1 ][ s \ j ] )
O( N2 2N ).

Submission #3947997 - Educational DP Contest

P

0を勝手に根として,
dp[ u ][ i ] := sum( u 以下を塗り, u は i==1 ? 黒 : 白 とする塗り方 )
dp[ u ][ 0 ] = prod _ { v in child( u ) } ( dp[ v ][ 0 ] + dp[ v ][ 1 ] )
dp[ u ][ 1 ] = prod _ { v in child( u ) } ( dp[ v ][ 0 ] )
どちらも子がない場合は 1.
ans = dp[ 0 ][ 0 ] + dp[ 0 ][ 1 ]
O(N).

Submission #3948387 - Educational DP Contest

和と積がこっちゃになる人は和集合(Or),積集合(And)を考えるとわかりやすいかも

Q

そのまま式を立てると
dp[ i ][ j ] := max( 左から i 本目まで見て一番高い花が j 本目の時の美しさの総和 )
dp[ i+1 ][ i+1 ] = max _ { h j < h_i } ( dp[ i ][ j ] ) + a_i
dp[ i ]の列は1つの値しか更新しなくて良いことに気づくので1次元にしよう.
( ( i, k) -> ( i+1, l) , ( i, l ) -> ( i+1, m) のような更新があると1次元では困る )
すると dp[ i ] := max( 一番高い花が i 本目である時の美しさの総和 ) となる.
遷移は
dp[ i ] = max
{ j < i, h _ j < h _ i }( dp[ j ] ) + a_i
左から更新していくと j < i は常に満たされるので h_j < h_i なるものの中から max をとってやれば良い.
これは h_i をDPのキーとして持ってやればSegmentTreeでできる.
h_i が大きいと座圧してやる必要があるけど,これは順列になっているのでそのままできる.
よってDPテーブルをSegmentTreeで作って,
dp[ k ] := max( 一番高い花の高さがk の美しさ )
dp[ k ] = max_{0 <= j < k} ( dp[ j ] )

O(N logN).

Submission #3948747 - Educational DP Contest

R

これ数理情報学の院試で見たやつだ
A = (隣接行列) として Ak _{i, j} = ( i -> j の総長 k のパスの本数 ) になる.
これ自体知ってても良さそうだけど
dp[ k ][ i ][ j ] := ( i -> j の総長 k のパスの本数 ) とすると制約見て行列積しかないねってなりそう.
O(N3 log K).

Submission #3948940 - Educational DP Contest

S

桁DP.
dp[ i ][ j ][ k ] := sum( 上から i 桁まで決めて数字の総和 mod D が j , k == 1 ならその桁まで K と等しい )
dp[ 0 ][ 0 ][ 1 ] = 1 から
dp[ i+1 ][ ( j + K[ i ] ) % D ][ 1 ] += dp[ i ][ j ][ 1 ]
for 0 <= d < K[ i ] : dp[ i+1 ][ ( j + d ) % D ][ 0 ] += dp[ i ][ j ][ 1 ]
for 0 <= d <= 9 : dp[ i+1 ][ ( j + d ) % D ][ 0 ] += dp[ i ][ j ][ 0 ]
と配っていく.
O( |K| D).

Submission #3949252 - Educational DP Contest

T

小さい順に挿入していくことを考えすぎてできなかった.

dp[ i ][ j ] := #( [0,i) の位置まで配って末尾より大きいものが j 個残っている状態 )
i + j <= N を満たす.
この時, 状態 ( i , j ) からの遷移を考える.
s[ i-1 ] = '<' の時,
j 個の置く数の候補があり dp[ i ][ j ] を dp[ i+1 ][ k ] ( 0 <= k < j ) に足し込めばいい.

'>' の時,
N-i-j 個の候補があり(末尾より小さい数), dp[ i ][ j ] を dp[ i+1 ][ k ] (j <= k < N-i )に足しこむ.

愚直 O(N3) 、 imos法を使うと O(N2) になる.

Submission #4385313 - Educational DP Contest

U

p[ s ] := ( 集合 s を全員同じグループにした時に得られる得点 ) を前計算し,
dp[ s ] = max( 集合 s を使った時の合計得点 )
漸化式は
dp[ s ] := max_{ t = subset( s ) } dp[ s \ t ] + p[ t ]

各 s に対して 2N 列挙して部分集合なら遷移みたいな実装をすると O(4N) になるが,
正しく部分集合を列挙すると s で立っているビット数を b として
sum_ { 0 <= b <= N } comb(N, b) 2b = 3N となる.
詳しくは こことか

Submission #3970446 - Educational DP Contest

V

いわゆる全方位木DPというやつ.
dp[ u ] := ( u以下の部分木で u を黒で塗る塗り方) として,
dfsで0を根として dpテーブルを埋める.
その後もう一回 dfsをしていく, この際呼び出し元 u から子 v を呼んだ際に
pval := ( 木全体からvを根とする部分木を除いた木で u を黒に塗る塗り方 ) を持っていく.
すると頂点 u に関する答えは PI( dp[ vの子 ] + 1 ) * ( pval + 1) になる (PIは積)
後は v から その子に pvalを持って伝播させていけばいい.
これは累積和の要領で [ 0,i ) の積, [ i, sz(vの子) ) の積を持っておけば,
i 番目の子に関して pval = PI _ [ 0, i ) * PI _ [i+1, sz) で計算できる.

木と計算量 後編 〜全方位木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

Submission #4387140 - Educational DP Contest

W

やっと解説ACした. 要復習.

区間の操作関連でDPするときに,区間が含まれたときではなくその終点で操作を行う,みたいなやつ.
この解説がわかりやすすぎて書くことない.

Submission #5033754 - Educational DP Contest

X

まず荷物の置き方について, 上から Xの荷物, (w_1,s_1) , (w_2,s_2) と置くことを考える.
この時満たすべき条件は
X <= s_1 and X + w_1 <= s_2
<=> X <= min(s_1 , s_2 - w_1 )
これを swapすると X <= min( s_2 , s_1 - w_2) .
これが上における荷物の上限ということになる.
w_1 を上に置きたい時 min( s_1 , s_2 - w_1 ) >= min( s_2 , s_1 - w_2) .. (1) であればいい.
(1) <=> s_1 >= min( s_2, s_1 - w_2 ) (2) かつ s_2 - w_1 >= min( s_2, s_1 - w_2) (3) となる.
(2) は s_1 >= s_1 - w_2 から必ず満たす.
(3)は s_2 - w_1 >= s_2 が成り立つことはないため s_2 - w_1 >= s_1 - w_2 と同値.
よって s_1 + w_1 <= s_2 + w_2 を得る. つまり { s_i + w_i } で並べていけばいい.

dp[ i ][ x ] := max( i 番目のブロックまでを考え,合計の重さ x の時の価値)
とすれば
dp[ i+1 ][ x ] = max( dp[ i ][ x ], ( x-w_i <= s_i ? dp[ i ][ x - w_i ] + v_i : -INF) )

重さは最悪ケースの max( w ) + max( s ) 程度を考えればOK.
( max( w ) の上に max( s ) が乗っている )

Submission #4386153 - Educational DP Contest

Y

数学でもそうだけど,こういうの大体余事象を数える.
この際 i 番目の点を初めて通ったという条件を入れると独立に数えられる.
{ (r_i, c_i) } に (H-1,W-1) を加えて pair の昇順sortし,
dp[ i ] := ( i 番目の点を初めて通るような ( r_i, c_i ) へのパスの数 ) とすれば,
dp[ i ] = f( r_i, c_i ) - sum _ { j, r_j <= r_i かつ c_j <= c_i } ( dp[ j ] * f(r_i - r_j, c_i - c_j ) )
ただし f( r , c) = {r+c} C {r} これ身に付けたい.

Submission #4384588 - Educational DP Contest

Z

dp[ i ] = min{0 <= j < i } (dp[ j ] + (h[ i ] - h[ j ])2 + C )
愚直O(N2)だがConvexHullTrickを使うとO(N)になる.
(右辺) = min{ 0 <= j < i }( -2 h[ j ] * h[ i ] + ( dp[ j ] + h[ j ]^2 ) )+ ( h[ i ]^2 + C )
で左の min の部分が求められればいいが, これは h[ i ] を x とみなして CHTを適用すれば求められる.
dp[ i ] を求めた後は 直線 -2 h[ i ] * x + ( dp[ i ] + h[ i ]^2 ) をCHTの直線群に追加する.
-2h[ i ] は単調増加するのでこれは可能である.

Submission #4707883 - Educational DP Contest

Codeforces ECR #57 F. Inversion Expectation

問題概要

一部が -1 である [1,N] のpermが与えられる.
各-1に等確率で残りの数が入る時,転倒数の期待値を求めよ.

解法

A = もともとある数, B = -1の場所に入る数 とする.
A-A, A-B, B-B の期待値を足せば良い.
A-A はBITを使って数え上げる.
B-B は b1, b2 in B が転倒している確率は 1/2なので,
これを全てのペアについて足し, |B| (|B|-1) /4.

以下でA-Bの期待値を考える.
x in B をどの-1に挿入する確率も 1/|B| なので,
xが片方になる転倒ペアを数え上げてこの確率をかける.

これは i in A に対して
left( i ) := ( i の左にある-1の数), rightも同様に定義すると,
sum{ y in A, y < x} left(y) + sum{ y in A, y < x } right(y) となる.
これは累積和で求められる.

コード

AGC 030 B - Tree Burning

解法

お絵描きしたのでメモ.

部分点は O(N2) の区間DP.

それ以上に早くやるにはどうするか.
遷移が O(1) なので状態を減らすしかない.
しかし,DPテーブルは疎でもなく,あまりまとめられそうにもない.
よってある状態(操作)を禁止して状態を減らすことを考える.

ここ とかがわかりやすい.

f:id:kurarrr:20190105233011j:plain

(直進) - (往復) - (直進) みたいな操作列が存在するならば,
最後の直進の終点が往復の終点になるように(直進) - (往復) の操作列に替えることができて,
これは元の移動距離よりも大きくなる.
よって (直進) - (往復) の操作列だけを考えてよく,状態が減らせた.

あとは累積和を使えばO(N)で解ける.

Hello 2019 D. Makoto and a Blackboard

問題概要

自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ.

  • 自然数に対してその約数を等確率で1つ選び,その約数で置き換える.

1 <= N <= 1015 , 1 <= K <= 104

解法

本番は愚直なDPを定数倍高速化しようとしたが無理だった.

これは約数を全列挙した後, dp[ i ][ j ] := ( i 回目の操作で j 番目の約数である確率,または期待値 ) とやるDP.
約数の数 S とすると, S 〜 213 〜 8 * 103 程度なので( 13番目の素数までの積〜 1015 より )
配るDPでやると複数区間に配ることになり,連続区間でなくimos法も使えないので O( S2 * K ) で間に合わない.

Hello 2019 Editorial - Codeforces にもあるように,各素因数が独立であることを使って計算しよう.

X,Y が独立の時, E[XY] = E[X]E[Y] より, 操作後の値 X= 2a 3b 5c ... とすれば
E[X] = E[ 2a 3b 5c .. ] = E[2a] E[3b] E[5c] .. となって各々DPで計算すれば良い.

a, b, c, .. = O( logN ) より, 全体での計算量は Q = |全体での素因数|と すると
愚直にやっても O( Q * log2 N * K ) となって
さっき見たように Q〜 13程度なので十分間に合う.
imos法も簡単に使えるので O(Q * logN * K) となる.
ちなみに元の計算量は S = O( logQ N) なので O( log2Q N * K ) である.(最初よりも緩い見積もり)
状態を複数の独立な状態に分割することによって計算量を落としていることがわかる.
期待値の問題でよく使えそうなので覚えておきたい.

メモ

本番では 最後ありえる状態に対してその確率をなんとかして数えたい
↓ 6 ~(2回の操作)~> 1 に対して
6->6->1, 6->3->1, 6->2->1, 6->1->1 を数える?と思っていたが,
各パスが遷移の確率が等しくないので困っていた.

素因数独立に見るのは少し考えたが回答までたどり着かなかった.
状態数が落ちるのが明確にイメージできてなかったせいだと思う.

ちなみに愚直DPを行列累乗で高速化すると O( S2 logK ) になるが間に合わないらしい.

コード