AtCoder Regular Contest 160
メモ
1 ~ 2*10^5 の整数がN個ある時に
xという整数を二つ消して、x+1を一つ作れる
この時集合としてあり得るものの数え上げをしろという問題
dp[a][x] := aより前までについての繰り上がり処理を終えた際に、aに対する繰り上がりがxであるような状態の場合の数
として遷移することが思いつくが、dpの状態数のオーダーが分からなかった
よく考えると、この状態数は
aiをaの個数として
操作中になり得る、最大のaiをSaiとしたときに
sigma(Sai)になる
ここでai(個数)が全体に寄与する量を考えると
ai, ai/2, ai/4, ....と右に行くにつれて半分になっていき
1+1/2+1/4+.... == 2であることから
aiが全体に寄与する量は O(ai)である
よって全体の合計もO(sigma(ai)) = O(N)
aiが寄与する量は
