result:oooooo---(37分+1WA)
perf:2087
rateing:1907->1926
■A - Weird Function
関数を関数化する
■B - Longest Segment
全部試す
■C - Happy New Year!
2を1に置き換えるとただの２進数
■D - Prefix K-th Max
priority_queueにk個入れておく
癖で２本持ったが、一本で良い
■E - Arithmetic Number
最上位と交差を全探索、桁上りするパターンに注意
■F - Reordering
挿入dp
a~eまで使って長さxの文字列を作る通り数をdp[5][x];
これにfをy文字突っ込むという遷移は
dp[6][x + y] += dp[5][x] * biom(x + y,y);
制約が緩いのでfpsなどをする必要はない。
■G - Divide a Sequence
これは解けないと駄目。
dp[i]:=i文字までで答えとすると
dp[i+1] = Σdp[j]*(max(aj+1~ai)-min(aj+1~ai))
となりこれはO(n^2)に見えるが
stackで上手に管理するといい
サンプル２
a/dp/maxstack/minstack
_/1/_/_
1/0/(1,1)/(1,1)
10/9/(10,1)/(1,1)
1/9/(10,1),(1,9)/(1,10)
10/90/(10,19)/(1,10),(10,9)
という感じ
これの差分管理を行えばいい。
■Ex - Enumerate Pairs
領域をk*kの大きさのブロックに分割すると
そのブロックの周辺9マス(自分を含む)にない限り距離がk以下にはならない。
なのでそのケースのみ考えればいい
で計算量はという話を考える
あるk*kの正方形の中にn個数の点が存在する
k/2の*k/2の領域に分割するとどれかのなかにn/4この点が存在するため
k*kの中には少なくとも(n/4)*(n/4-1)/2個数の距離k以下のペアが存在する
そのためn*(n-1)/2で同じことをやっても定数倍は問題がない。
領域をs0,s1,,,,,snとしその中の点の個数をd0,d1,,,,,,dnとすると
Σdi^2=O(m + n) mは答えの個数
となり
また、違うブロック通しをすべて調べるケースにおいても
Σdi*(di0+di1+......di8)になるが(di0,,,di8は周辺のもの)
di* dij <=(di^2+dij^2)/2になるため
Σdi*(di0+di1+......di8)<=O(Σ9di^2+di0^2+di1^2.....di8^2)となるため
同じ物はすべての式をあわせても定数回しか足されないため
O(n+m)で収まる
