ARC043 B - 難易度

f:id:tkr987:20210320155915p:plain

f:id:tkr987:20210320155956p:plain

https://atcoder.jp/contests/arc043/submissions/20924727

初期値は dp[0][0] = ... = dp[0][N-3] = 1
繰り返しは each(i, e, D) rep(j, 1, 4)
漸化式は dp[j].Add(i, dp[j - 1].Sum(0, distance(D.begin(), upper_bound(all(D), e / 2))))
最終目標は Sum(all(dp[3]))

f:id:tkr987:20210320160943p:plain

問題がN個あり、その中から4問選択する組み合わせの数なので

dp[i][j] := i番目の難易度をj問目の出題として選択する組み合わせ数　とする

しかし、難易度をソートして文章通りに実装すると遷移先が最大N個あるので合計 $O(N^2)$ になりTLEしてしまう。ここで、配るDPでなく貰うDPで考える。難易度Xに遷移するのは難易度1から難易度X/2の範囲である。したがって、点加算と区間合計を高速に処理できるデータ構造でDPすればよく、DPの型をBITにしてX/2の位置をupper_boundで検索しながら処理することで $O(N \log N)$ になる。