Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

AtCoder Regular Contest 159 D問題メモ

AtCoder Regular Contest 159

D - LIS 2

D - LIS 2

問題

(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によって求められる。

例で構築した 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,R109 のため、DP配列が 109 の長さになりえて、当然このままでは無理。

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

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

          旧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) = (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

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

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

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

Python3