7K12 blog

猫でも分かるアルゴリズム解説

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)になる。

 

なお、この問題じつは遅延セグ木を使えば貼るだけで処理することも出来る

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