@snuke_
ꑄ꒖ꐇꌅꏂ?

SRM 747 Div1 解法・感想

# Easy
if d < 2: d += 10
a = d/2
b = d-a
として、nの半分ずつくらいの1の位をaとbに割り振る感じで。
a,b=2,7 みたいなのを選んでもギリ大丈夫っぽくて、なかなか落ちにくそう。

# Med
maxをxと決め打つと、
dp[i][j][k] = i 山目までで j 個割り振って、min(ちょうど x の山の個数, 2) が k(x より大はダメ)
みたいなdpなんだけど遷移はコード見て。
誤差どれくらい気をつければいいのかわからない、誰か誤差講座を書いてくれ〜

# Hard
(x,y,z) = (l, n-r, s[l]+s[r]) だと思うと3次元 LIS (zだけ等号が許される)
(z,x)でソートして(x,y)を管理する二次元BIT。
BITに持たせる情報は、構造体作って+=をそれっぽくオーバーロードしとけばいい感じ。
maxクエリなのにBITでいいのかと思うかもしれないけど、削除クエリはない & 区間クエリの左端が常に0 なので大丈夫。


via Twishort Web App

Retweet Reply
Made by @trknov