問題

正整数 $X$ と列 $L \in \lbrack 1, X \rbrack^N$ が与えられる。 $f : N \to \mathbb{N}$ であって $\forall i \lt N.~ f(i) + L_i \le X$ および $\forall x \lt X.~ \exists i \lt N.~ f(i) \le x \lt f(i) + L_i$ を満たすものの数を数えよ。

考察

  • とりあえず補集合か？
  • ある位置 $x \lt X$ が使われないようなものをすべて数えて包除原理したい
    • 使われない座標の集合が区間にならないのでだめ
  • 座標を左から埋めていきたい
    • となると使ったシートの集合を管理しないとだめで $O(2^N)$ が乗っちゃう
  • $N \le 100$ はけっこう小さいし $X \le 500$ はかなり小さい
  • とりあえずシートを長さ順でソートしましょう
    • シートの長さを降順で使っていけば、次のうちのどれかなのでうれしい
      • 新しい区間を形成する
      • すでにある区間のひとつにまったく包含される
      • すでにある区間のひとつの右側を伸ばす
      • すでにある区間のひとつの左側を伸ばす
      • すでにある区間ふたつの間を埋めてひとつにする
    • つまり、次が発生しない
      • すでにある区間のひとつの右側と左側の両方を伸ばす
  • 次のすべてを状態とする DP ができる
    • すでに覆われている区間の長さの合計
    • まだ覆われていない区間の長さの列 (両端を除いて順序は無視する)
  • 計算量が分割数 $p(400) \approx 6.3 \times 10^{18}$ は厳しい
  • 無理でしょ

ここで解説をちら見

  • すでにある区間どうしの間隔は無視してよい。繋げるときに始めて固定すればよい。それはそう
  • 互いに共通部分を持たない閉区間の列についての次のような DP ができる
    • 次のすべてを状態とする
      • すでに覆われている区間の長さの合計
      • すでに覆われている区間の個数
    • 次を遷移とする
      • 新しい区間を作る (列のどこかに挿入する)
      • ひとつの区間を伸ばす ($0$ 以上 $L_i$ 以下)
      • ふたつの隣接する区間を繋ぐ (ここで始めて隣接する区間の間の距離が確定する)
    • ただし最後に区間の間の距離の可能性の分だけ乗じるやつをする

解法

愚直 DP を考えると、すでに使われている座標の区間の集合 (例 $A = \left\lbrace \lbrack 0, 3 \rbrack, \lbrack 4, 5 \rbrack, \lbrack 7, 9 \rbrack \right\rbrace$) を状態とするものになる。 区間同士の間隔は区間の併合が発生する時や DP が終わった後に考慮することにすると、長さの列 (例: $A’ = ( #a \mid a \in A _ {\text{as list}} ) = (3, 1, 2)$) だけ管理すれば十分になる。 シートを長さの降順にソートし大きい方から使っていくとすることで $3$ 個以上の区間がまとめられたりすることがなくなり、区間の個数と長さの和 (例: $A’’ = (#A’, \sum _ {a \in A’} a) = (3, 6)$) だけ覚えておけばよくなる。 これで荒い見積りで $O(N^2X^2)$ に落ち、間に合う。

メモ

  • 要点は次
    • 使った区間同士の距離の決定を遅延する
    • 区間を長さの降順で使っていく。これにより新しく使う区間がすでにある区間を包含する場合が排除され、左を伸ばす / 右を伸ばす / 隣接する区間をつなぐ、の $3$ 通りだけ考えればよくなる

リンク