result:oooooo--
rateing:1867->1863
■A - Four Points
xorをすれば早い
■B - Get Closer
やるだけ
■C - Coupon
無駄なくクーポンを使うのを優先する
オーバーフローで１ペナ
■D - 2-variable Function
O(1)算数とおもいきや
aを全探索してbを二分探索なり尺取法で求める。
■E - Bishop 2
01BFS
■F - typewriter
解説となんかやり方違うね。
n種類の文字すべてを使って、長さlの文字列を作れる通り数は簡単なdpで求められる。
2^26通りある文字の選び方に対してそれらが作れるかどうかは
入力の文字列をbitにしたもののどれかと包含関係があるかどうか
でもこれだとO(n(26+n+2^26))なので少し遅い。
■G - Game on Tree 3
解を二分探索するということはわかる。
ある頂点から初めたときのスコアを
この地点からスタートしたときに青木くんが勝つために、
ゲーム開始前から書き換えておかないと行けない場所の数とする。
すると
dp[v]=max(0,Σdp[c]-1)+vがansかどうか
とすればよく
dp[0] = 0なら青木の勝ち。
■Ex - 01? Queries
割とシンプルなdp
クエリによるアップデートを無視してた答えをまず考えてみる
00110として
0:0
00:00
001:01,001,1
0011:011,0011,11
00110:000,010,0010,10,0110,00110,110
ぼんやり眺めていみると遷移がわかって
dp[n][0],dp[n][1]をそれぞれ、n番目の文字まで見て作れる末尾が0と1の文字列の個数とすると
s[n+1] = 0としたときに
dp[n+1][1] = dp[n][1]
dp[n+1][0] = dp[n][0]+dp[n][1]+1
となる?や1も同様に遷移させる。
これは3*3の行列に乗るのでクエリを無視したときの答えは求まる
クリエによる更新は上記の行列をセグ木に乗せれば良い。
