絶対冷えたと思ったけど
result:ooooo---
rate:1926->1933
■A - Rotate
(s[0] + s[1] + s[2])*111
■B - Climbing Takahashi
貪欲に前から
■C - The Kth Time Query
map< pair<要素、同じ要素の何番目か , idx>>
■D - Multiply and Rotate
考える必要のある要素は同じ桁数までなのでBFSでやる
■E - MST + 1
クエリを先読みしてクラシカル法
■F - Variety of Digits
典型桁dpだが何故かバグる。
leading-zeroがバグってるようだが結局わからないので書き直してAC
pair<合計, 要素数> dp[i][j][k][l]:=i番目まで見た、reading0かどうか(j)、未満かどうか(k)、ここまで使った集合がl
としたらACしたが1859msなので
dp[i][j]:=未満なのが確定、ここまで使った集合がj
とすると高速
桁dpは未満の方だけ配列でもって、一致中の場合は直値を持ったままにしたほうが早い。
遷移が単純に半分になるので。
■G - Gardens
こっちを解くべき。
というかFもGも通せるべき。
最低でもFで詰まった時点でGを考えるべき
どう見てもド典型包除原理。
サンプル3を考えると
+Biom(2,2)*(Biom(2,0))*(Biom(2,0)+Biom(2,1)+Biom(2,2))*(Biom(2,0)+Biom(2,1)+Biom(2,2))
-Biom(2,1)*(Biom(1,0))*(Biom(1,0)+Biom(1,1))*(Biom(1,0)+Biom(1,1))
+Biom(2,0)*(Biom(0,0))*(Biom(0,0))*(Biom(0,0))
ちょっと見やすくすると
+Biom(2,2)*(Biom(2,0))*(Biom(2,0)+Biom(2,1)+Biom(2,2))*(Biom(2,0)+Biom(2,1)+Biom(2,2))
-Biom(2,1)*(Biom(1,0))*(Biom(1,0)+Biom(1,1)+Biom(1,2))*(Biom(1,0)+Biom(1,1)+Biom(1,2))
+Biom(2,0)*(Biom(0,0))*(Biom(0,0)+Biom(0,1)+Biom(0,2))*(Biom(0,0)+Biom(0,1)+Biom(0,2))
となるので括弧ないのcの連続和を考えればよい。
これはパスカルの三角形上で考えると下から上にみるとして
倍して余計なものを省くともとまる。
■Ex - Painting Weighted Graph
O(NK)の木dp。
2乗の木dpじゃないところが難しくないですか？
解説動画参照。
