主食は米

主に競プロ備忘録

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 / DP まとめコンテスト

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 / DP まとめコンテスト

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 / DP まとめコンテスト

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 / DP まとめコンテスト

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 / DP まとめコンテスト

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 / DP まとめコンテスト

G

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

Submission #3941322 - Educational DP Contest / DP まとめコンテスト

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 / DP まとめコンテスト

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 / DP まとめコンテスト

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 )
次に別の状態に移るのは s 以外の時で, それまでに 平均(期待値)で 1/s 回 0 枚の皿を選ぶので
i, j, k の降順に dp[ i-1 ][ j ][ k ] += p * (dp[ i ][ j ][ k ] + 1/s )
dp[ i+1 ][ j-1 ][ k ] += q * (dp[ i ][ j ][ k ] + 1/s )
dp[ i ][ j+1 ][ k-1 ] += r * (dp[ i ][ j ][ k ] + 1/s )
と配っていく.
O(N3).
頭バグって飛ばした.(未AC)

追記. 違いましたごめんね(未だわからず)

K

苦手. 飛ばした

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 / DP まとめコンテスト

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 / DP まとめコンテスト

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 / DP まとめコンテスト

アルゴリズムイントロダクションに乗ってる連鎖行列積とほとんど一緒だなあと思った.
このスライドの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 / DP まとめコンテスト

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 / DP まとめコンテスト

和と積がこっちゃになる人は和集合(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 / DP まとめコンテスト

R

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

Submission #3948940 - Educational DP Contest / DP まとめコンテスト

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 / DP まとめコンテスト

T

寝ます

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 / DP まとめコンテスト

追記

WIP

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 ) になるが間に合わないらしい.

コード

CODE THANKS FESTIVAL 2018 H - Median Game (500)

解法

スコアは中央値なので,そのままやるとこれまで書いた和を全て持っておく必要がある(どれも中央値になり得る)
=> これは当然全探索に近いので不可能
=> 中央値は2ぶたんがやりやすい(X以上がY個の条件が判定しやすい) という典型もあり,判定関数を作って2ぶたんをしようという気持ちになる

すると判定をO(N2)ぐらいのDPでやろうというのが自然な流れになる.
注意としては,ゲームでDPをやるときは後ろから(そうしないと最終的にmax/minに持っていけない)
x以上のスコアを取れるか?という判定をすることを考える.
dp[ i ][ j ] := ( i ターン経過, a[j,N) でゲームをした時の x 以上の個数 ) とやると, O(N3) かかってしまう.
かといって遷移で x 以上でなるべく遠くをとったほうがいい みたいなのは成り立たない.(間違った)
ここで削れる要素は i ターンで, 先手/後手を持てば良さそうだが, x 以上が半分以上か?というのが判定できなくて困る.
こういうときは 値として #(x 以上) - #(x 未満) を持てば良い (半分以上か?を判定する典型)
( #(x以上)/ターン数 を最大化するようにこの2つの数を持ってもいいのか.. ? )

後は公式解説と同じ.
コードでは
dp1[ i ] := (先手番で,#(x以上) - #(x未満) の max )
dp2[ i ] := (後手番で #(x以上) - #(x未満) の min )
としている.

メモ

500ではない

コード

CADDi 2018 D - Harlequin (500)

解法

公式動画&解説で基本的にわかるので個人的な備忘録にとどめておく.

ゲームの問題の基本的な戦略として,手で書いて実験をする.
N個の数のケースで実験すると1回の遷移が O(2N) になるので, N=2で実験する.
公式解説のようなグラフを書いて実験をすると良い.
これは結構定番で ARC 072 D - Alice&Brown - 主食は米 とかもこれを使って解ける.

2個で大体のパターンがわかると一般化できそうだという気がしてくる.
この際に用いるのが相手がどのような手をとっても同じ状態に戻せるということで,
この問題であれば 全て偶数/それ以外 の状態に全ての状態をまとめることができ,
全て偶数という状態が最終的に相手の負けになるので,解説の答えが出る.

メモ

N=2 の状態で実験をしてグラフを書くのはマストな気がする.
最初からNが大きい状態で考えてしまって解けなかった.

コード