AtCoder Regular Contest 159 D問題メモ

AtCoder Regular Contest 159

D - LIS 2

• 数列 $X$ を、$N$ 個の $(L,R)$ の組によって、以下の方法で構築する
  • はじめ、$X$ は空
  • $i=1,2,...,N$ の順に、$X$ の末尾に $L_i,L_i+1,...,R_i$ をこの順で追加する
• 構築完了した $X$ のLIS（狭義最長増加部分列）を求めよ
• $1 \le N \le 2 \times 10^5$
• $1 \le L_i \le R_i \le 10^9$

(L, R) = (3,5), (7,8), (12,13), (4,10), (2,7)
↓
X = 3 4 5 7 8 12 13 4 5 6 7 8 9 10 2 3 4 5 6 7

(3 4 5 6 7 8 9 10) の、長さ8のLISが取れ、これが最長

LISをそのまま求める方法から情報を圧縮することを考える。（遅延評価セグ木でも解けるらしい）

一般的なLISは次のDPによって求められる。

• $DP[i][j]=X_1～X_i$ で作れる長さ $j$ のLISで、末尾要素になり得る最小値
  • ただし、$i$ の次元は、1つ前の状態があれば求められるため、実装上は省略

例で構築した $X$ をもとにこれをおこなっていくと、

          DP
初期状態  [0]

(3, 5)    [0 3 4 5]
             ~~~~~
(7, 8)    [0 3 4 5 7 8]
                   ~~~
(12,13)   [0 3 4 5 7 8 12 13]
                       ~~~~~
(4, 10)   [0 3 4 5 6 7  8  9 10]
               ~~~~~~~~~~~~~~~~
(2, 7)    [0 2 3 4 5 6  7  9 10]
             ~~~~~~~~~~~~

となる。性質上、1ずつ増加する部分が非常に多い。
実際は制約が $L,R \le 10^9$ のため、DP配列が $10^9$ の長さになりえて、当然このままでは無理。

そこで、1ずつ増加する部分は省略し、それが途切れる右端部分 $r$ と、その位置 $i$ を保持することを考える。
このような $r$ は、たかだか $N$ 個に収まる。

実装上は、$r$ は順番を保ったまま追加・削除ができる平衡二分探索木やSortedSetのようなデータ構造で管理し、 $r→i$ は辞書で関連付けることにする。

          旧DP                      DP  r:i
初期状態  [0]                      {0:0}  

(3, 5)    [0 3 4 5]                {0:0  5:3}
             ~~~~~
(7, 8)    [0 3 4 5 7 8]            {0:0  5:3  8:5}
                   ~~~
(12,13)   [0 3 4 5 7 8 12 13]      {0:0  5:3  8:5  13:7}
                       ~~~~~
(4, 10)   [0 3 4 5 6 7  8  9 10]   {0:0  10:8}
               ~~~~~~~~~~~~~~~~
(2, 7)    [0 2 3 4 5 6  7  9 10]   {0:0  7:6  10:8}
             ~~~~~~~~~~~~

説明上、DPの1つの $\{r:i\}$ を「$r$ の区間」と呼ぶことにする。
たとえば上例の最下段のDPで、「7の区間」は $\{7:6\}$ 、旧DPで $(2,3,4,5,6,7)$ の部分に相当する。

重要な事実として、$(L,R)$ で更新されるたびに、旧DP上にはどこかしらで $L,L+1,...,R$ の並びができる。

元来のLISのDPの更新方法「DP配列上で、自身未満で一番大きい要素の次に、自身を上書きまたは追加する」という更新方法からしても分かるとおり、 更新後のDP配列には必ず、直近に更新した値が存在する。
（元から同じ数字が存在していて、実質的には更新されていない、ということもあり得るが、存在はする）

$(L,R)$ をまとめて更新する際でもそれが連鎖的に起きるため（$L+1$ を更新するときには必ず $L$ が存在し、かつそれが $L+1$ 未満で一番大きい要素）、$L,L+1,...,R$ の並びは必ず作られる。

よって、$(L,R)$ をまとめて更新する際には、「どの位置から $L$ がスタートするか？」が分かればよい。
ただその際、上書きされて不要になる区間があったりするので、更新パターンを考える。

具体的には以下の手順で更新できる。更新作業を行う関数を $f(L,R)$ とする。

まず、追加しようとしている並びの左端 $L$ の位置を知るため、DPから以下の値を得る。

• $L$ 未満で直近の $r_1$、対応する $i_1$
• $L$ 以上で直近の $r_2$、対応する $i_2$、$r_2$ の区間の左端 $l_2 = r_2-(i_2-i_1)+1$

追加しようとしている(L,R) = (5, 8)

旧DP                     DP
[0 2 3 4 5 6  7  9 10]   {0:0  7:6  10:8}

→  r1 = 0   i1 = 0
    r2 = 7   i2 = 6   l2 = 2

• $r_2$ が存在しない場合
  • $r_1$ の末尾からLISを伸ばせる
    • →DPに $r=R,i=i_1+R-L+1$ を追加して終了

• $L \lt l_2$ のとき
  • 旧DP配列の $(l_2,l_2+1,...)$ の部分を、より小さい $(L,L+1,...)$ で上書きできる
  • 上書きが終わる（$R$ に対応することになる $i$）のは、$i_R=i_1+R-L+1$
  • $i_2 \gt i_R$ のとき
    • $r_2$ の区間の末尾は上書きされずに残るので、追加だけを行う
      • →DPに $r=R,i=i_R$ を追加して終了
  • $i_2 = i_R$ のとき
    • ちょうど $r_2$ の区間で更新が終わる
      • →DPから $r_2$ を削除、$r=R,i=i_R$ を追加して終了
  • $i_2 \lt i_R$ のとき
    • $r_2$ の区間を越えて更新が続く
      • →DPから $r_2$ を削除し、再び $f(L,R)$ を行う

• $L = l_2$ のとき
  • 旧DP配列のうち、$(l_2,l_2+1,...)$ の部分を $(L,L+1,...)$ で上書きするが、結局同じ値のため、実際には変化しない
  • $r_2 \lt R$ なら、それ以降も更新が続く
    • →DPから $r_2$ を削除し、再び $f(L,R)$ を行う

• $L \gt l_2$ のとき
  • 旧DP配列の $(l_2,l_2+1,...,r_2)$ の途中に $L$ が存在する（$r_2$ は $L$ 以上なので、必ず存在する）
    • 今回の更新による $L,L+1,...,R$ の並びは、その $L$ から始まる
  • $r_2 \ge R$ のとき、$L,L+1,...,R$ の並びは既存の状態に完全に重なるため、更新は発生しない
  • $r_2 \lt R$ のとき、$r_2$ の区間が終わった箇所から更新できる
    • →DPから $r_2$ を削除し、$f(l_2,R)$ をおこなう

最終的なDPのうち、最大の $r$ に対応する $i$ が答えとなる。

$r$ の追加・削除はそれぞれたかだか $N$ 回までしか行われず、探索も追加・削除毎に最大2回、計 $4N$ 回までなので、 これらの操作1回を $O(\log{N})$ や $O(\sqrt{N})$ で行えれば、全体で $O(N\log{N})$ や $O(N\sqrt{N})$ となり実行制限時間に間に合う。

本問題は、ナイーブなLISのDPから情報を圧縮したが、 「実際に更新によってどのようになるか」は いきなり圧縮後の状態だけで考えてもイメージしにくく、 圧縮前の方が理解しやすかった。
問題にもよるが、着実に考察を進めるには2つを並べて行き来することが肝要だね。

Python3