競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 132C

ARC132C

まず,愚直なDPを考えると,
\(dp_{i,s} := \) \([0,i)\) まで,使った数のset \(s \in 2^{N}\).
これは TLE, MLE.

 

改良を考える. \(i \in N\) は減らすのが難しいので, \(s \in 2^{N}\) を減らすことを考える. 与えられた条件から,任意の \(i \in N\) に対して, \(- d \leq p_{i} - i \leq d\). よって, \(p_{i}\) の候補は \(2d+1\) 通りに絞れる. したがって,状態が \(O(2^{2d+1})\). 遷移は \(O(N)\).

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"