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の実装あたり引いたっぽい