区間に対する判定問題、最適化が必要となるのが精選100問48問目「ダルマ落とし」（ICPC2016国内予選Dとして出題）です。
区間DPがテーマですが、ここではメモ化再帰を使った理解しやすい解法を紹介したいと思います。
問題概要
長さ[math]N[/math]の数列[math]w_1,\dots,w_N[/math]が与えられる。差が1以下の隣接する2要素を削除していく時、削除できる要素数の最大値を求めよ。
制限
- [math]1 \leq N \leq 300[/math]
- [math]1 \leq w_i \leq 1000[/math]
- 実行時間制限は8秒
考察
具体例での考察
貪欲に削除していくのはうまくいきません。例えばサンプルの2つ目の「1 2 3 1」は左から「1 2」を消すとこれ以上消せませんが、先に「2 3」を消して残った「1 1」を消すと4つすべてを消すことができます。
こういった最適化問題を解く一つの典型アプローチは「より小さな部分問題に分解できないか？」と考えることです。まず、[math]N=9[/math]の例で考えてみましょう。
一番左の要素8に注目すると
「使わない（削除せず残す）」か「他の要素とペアにして削除」の2通りあります。
まず「使わない」場合は簡単で
サイズが1つ小さい[math]N=8[/math]の問題に帰着できます。
「他の要素とペアにして削除」する場合は
ペアになり得る要素（この例だと右隣りの7とその2つ隣の9）が複数ありえますが、いずれの場合も削除した要素から右側の数列についての問題に帰着できます。
これを繰り返すことで自明な大きさ（[math]N \leq 2[/math]）まで問題を分割していき、その結果を集めることで全体の答えを求めることができそうです。
考察の一般化
ある要素[math]l[/math]と要素[math]r[/math]をペアにして削除するための条件を考えると
2要素の間である「区間[math][l+1, r)[/math]の要素すべてが削除できること」になります。
では、「ある区間[math][l, r)[/math]の要素がすべて削除できる」ための条件を考えると
ある[math]l < r_1 < r[/math]が存在して
- 区間[math][l+1, r_1)[/math]はすべて削除可能
- 要素[math]l, r_1[/math]の差が1以下で削除可能
- 区間[math][r_1+1, r)[/math]はすべて削除可能
であることが分かります。これでより小さな判定問題に分割することができたので再帰的に任意の区間[math][l, r)[/math]について削除可能かを判定可能です。
区間[math][l, r)[/math]の要素がすべて削除可能を判定する疑似コードを書くと以下になります。
bool all_out(int l, int r){
要素数r-lが0ならばtrueを返す
要素数r-lが奇数ならばfalseを返す
要素数r-lが2ならば要素の差が1以下ならばtrue, そうでなければfalse
要素r_1をl+1からr-1まで動かし、
区間[l+1, r_1), 要素lとr_1, 区間[r_1+1, r)がすべて削除可能ならtrue
以上の処理が途中で終わらなければfalse
}
区間[math][l, r)[/math]の要素がすべて削除可能を判定できるようになれば、削除する個数の最大化についても解くことができます。
具体的には区間[math][l, N)[/math]で削除できる個数の最大値を[math]f(l)[/math]と置くと
- [math]f(l+1)[/math](要素[math]l[/math]を使わないことに対応)
- 要素[math]l, r(l < r < N)[/math]をペアにして削除: 区間[math][l+1, r)[/math]がすべて削除可能な場合に[math]r-l + f(r+1)[/math]
の最大値が[math]f(l)[/math]になることが分かります。こちらも再帰的に求めることができて[math]f(0)[/math]が求める答えになります。
最後に計算量を評価すると区間[math][l, r)[/math]の要素がすべて削除可能かを判定する部分が重くメモ化を行って
- 状態数: [math]O(N^2)[/math]
- 1つの状態を求めるための計算量: [math]O(N)[/math]
の[math]O(N^3)[/math]になります。[math]N \leq 300[/math]なので実行時間制限時間内に求めることができます。
最後にAOJで提出したコードはこちらになります。
