ABC263 (LINE Verda) 参加記

参加記書くのちょっとさぼってたので復帰

58:32 6完 182位 G解きたかった

A Full House

Aとしては大変かも、出てきた数をカウントして2,3になるところがあるか調べました

(AC 2:57)

 

B Ancestor

こういうのもうちょっと難易度高いところで無限回やった

Nから移動を繰り返して1にたどりつけばよいので、whileでループします

(AC 5:03)

 

C Monotonically Increasing

これも何回か見たことあるような

vectorをqueueに入れて、長さがNになったら答えにカウントするようにします

やってることはBFSですね

順列全列挙してもなんとか間に合いそう?

(AC 9:43)

 

D Left Right Operation

Dにしてはむずかしく感じました

これみたいに「両端から何かする」タイプの問題は、左からの計算・右からの計算をあらかじめしておいて、それをくっつけるとうまくいくことがあります

 

今回は

left[i][j] = 左からi番目までみて、まだLを使っている(j=1)/いない(j=0)時の最小値

right[i][j] = 右からi番目までみて、まだRを使っている(j=1)/いない(j=0)時の最小値

とDPを定義して計算しておくと、

答えは left[i][?] + right[i+1][?] (?=0 or 1)の最小値になります

ただし、全部L、Rで埋めるときが実装によっては漏れるので注意しましょう

(AC 20:13)

 

E Sugoroku 3

ド典型なんですが、知らないと自力で思いつくのは難しそうです

まず、こういう期待値DPの典型として「ゴールから考える」というものがあります

今回もNから決めていくとよいです

また、今回のようにループしているときの期待値って結構困ると思うんですが、

E[X] = aE[X] + bの式を、

E[X](1-a) = b

E[X] = b / (1-a)

と整理してあげると、右辺のE[X]が消えてループに対してうまく処理できます

これも非常に典型的な処理なので、知らなかった人は覚えておいた方がいいと思います

 

逆にこれを知っていれば、segment treeなどで累積和をとってあげれば簡単に計算できます

教育的!!初見で死ぬのは仕方ないタイプという印象

(AC 33:13)

 

F Tournament

これは普通に考察しました

まず貪欲にできないか考えるんですが、各区間で1勝が何人、2勝が何人...という条件を考慮しないといけないのでかなり厳しそうです

 

いろいろ考えると

dp[i][j] = 人iがj勝するときの最大値

みたいなdpが思い浮かんできます

 

これをマージすることを考えると、トーナメントは木の形になっているので、木DPができないかな?と思います

dp[i][j] = iを根とする部分木に含まれる人が最大j勝するときの最大値

と定義すると、このマージがきれいにできて

iの子がL,Rだとすると、今の高さをhとして

dp[i][j] = max ( dp[L][h-1] + dp[R][j], dp[L][j] + dp[R][h-1] )

として計算できます

h-1の部分は「高さhで負ける = h-1勝しかできない」という意味になります

ちょっと正当性を示すことはできなかったんですが、かなり正しそうなので実装すると通ります

(AC 58:32)

 

G Erasing Prime Pairs

1+1 = 2を素数にするのやめませんか...解けず...

 

総括

Fの実装あたり引いたっぽい