AtCoder Beginner Contest 360 F,G問題メモ

F - InterSections

問題文

$1$ から $N$ までの番号のついた $N$ 個の区間が与えられます。区間 $i$ は $[L_i,R_i]$ です。
区間 $[l_a,r_a]$ と区間 $[l_b,r_b]$ は $(l_a \lt l_b \lt r_a \lt r_b)$ または $(l_b \lt l_a \lt r_b \lt r_a)$ を満たすとき「交差する」といいます。
- つまり、長さが正の共通部分を持ちつつ、一方が一方を完全に含んでいるわけでは無い状態
$f(l,r)$ を $1 \leq i \leq N$ を満たし、区間 $[l,r]$ と区間 $i$ が交差する $i$ の個数と定義します。
$0 \leq l \lt r \leq 10^{9}$ を満たす整数の組 $(l,r)$ において、 $f(l,r)$ の最大値を達成する $(l,r)$ の組のうち $l$ が最小のものを答えてください。そのような組が複数存在する場合はさらにそのうちで $r$ が最小のものを答えてください。

制約

$ 1 \leq N \leq 10^{5}$
$ 0 \leq L_i \lt R_i \leq 10^{9}$ $(1 \leq i \leq N)$
入力は全て整数である

解法

こういう問題の時、$l,r$ の範囲制約（$0$ 以上 $10^9$ 以下）って、ある種お飾りというか、「自然にやれば勝手にこの範囲に収まりますよ。なんならこの範囲に収まるというヒントを与えていますよ」ということも多いように思うが、この問題の場合はわりとちゃんと“制約”であり、制約外で、問題の答えより $f(l,r)$ が大きくなる場合もあったりする。
仕様通りに「制約内での最大値を達成する $(l,r)$ の組」を求めなければならない。

それはともかく、解法の方針自体はそこまで難しくはない。

$l$ を固定して、$r$ についての問題を考えると、

                   l
区間1  |--------------| ********************
区間2      |----------------| **************
区間3        |---|                              *** の位置に r が来ると、
区間4                   |*************|         その区間と交差できることを意味する
区間5          |---|
区間6              |---------------|

$l$ が区間 $i$ の中にある場合は、$R_i+1$ 以降に $r$ が来ると交差する。
$l$ が区間 $i$ の左にある場合は、$L_i+1～R_i-1$ に $r$ が来ると交差する。
「中にある」「左にある」というのは、$l$ が $L_i,R_i$ と一致する場合は含まない（区間5,6の例）

よって、この ** を縦に合計して、一番 ** が多く重なっている箇所（のうち、最も左のもの）が、 $l$ を固定した場合の最適な $r$ となる。

$l$ を少し右に動かすと、

$l \lt L_i$ だったのが $l = L_i$ になった区間は、$L_i+1～R_i-1$ にあった *** が無くなる
$l = L_i$ だったのが $L_i \lt l \lt R_i$ になった区間は、$R_i+1$ 以降に *** が生じる
$l \lt R_i$ だったのが $l \ge R_i$ になった区間は、$R_i+1$ 以降にあった *** が無くなる

と、1つの区間に対し、$L_i,R_i$ と重なるタイミングで3回の更新が発生する。
逆に言うとそれ以外では変わらないので、$l$ を左から徐々に右に動かせば、全体で $O(N)$ 回の更新で済む。

区間加算・区間（最大値, 最大値が同じ場合は最小index）取得の遅延セグメント木で実装できる。

そのままでは座標の範囲が大きいが、「変化が生じる座標」「$l,r$ として最適になり得る座標」は $L_i,L_i+1,R_i,R_i+1$ のいずれかに限られる。これらのみ座標圧縮してセグメント木を構築すれば、サイズは $O(N)$ で済む。

で、範囲制約を考える。

実は、$l$ として最適になり得る座標には「$0$」も含まれる。
特に、交差できる区間が1つも無いとき、「$(0,1)$」が答えとなる。

また、$R_i+1=10^9+1$ なる区間が存在し、これが（範囲制約を考慮しない場合の）最適な $r$ になる場合がある。
これは答えの候補から除かないといけない。

これらのコーナーケースをちゃんと考慮すると、ACとなる。

Python3

import sys
from collections import defaultdict
from typing import TypeVar, Generic, Callable, List

T = TypeVar('T')
U = TypeVar('U')


class LazySegmentTreeInjectable(Generic[T, U]):
    def __init__(self,
                 n: int,
                 identity_data: Callable[[], T],
                 identity_lazy: Callable[[], U],
                 operation: Callable[[T, T], T],
                 mapping: Callable[[T, U], T],
                 composition: Callable[[U, U], U],
                 ):
        self.n = n
        self.depth = n.bit_length()
        self.offset = 1 << self.depth
        self.identity_data = identity_data
        self.identity_lazy = identity_lazy
        self.operation = operation
        self.mapping = mapping
        self.composition = composition
        self.data = [identity_data() for _ in range(self.offset << 1)]
        self.lazy = [identity_lazy() for _ in range(self.offset)]

    @classmethod
    def from_array(cls,
                   arr: List[T],
                   identity_data: Callable[[], T],
                   identity_lazy: Callable[[], U],
                   operation: Callable[[T, T], T],
                   mapping: Callable[[T, U], T],
                   composition: Callable[[U, U], U],
                   ):
        ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
        ins.data[ins.offset:ins.offset + ins.n] = arr
        for i in range(ins.offset - 1, 0, -1):
            ins.update(i)
        return ins

    def push(self, i: int) -> None:
        if i < self.offset:
            data = self.data
            lazy = self.lazy
            lz = lazy[i]

            lch = i << 1
            rch = lch + 1
            data[lch] = self.mapping(data[lch], lz)
            data[rch] = self.mapping(data[rch], lz)
            if lch < self.offset:
                lazy[lch] = self.composition(lazy[lch], lz)
                lazy[rch] = self.composition(lazy[rch], lz)
            lazy[i] = self.identity_lazy()

    def update(self, i: int) -> None:
        lch = i << 1
        rch = lch + 1
        self.data[i] = self.operation(self.data[lch], self.data[rch])

    def all_apply(self, i: int, d: U) -> None:
        self.data[i] = self.mapping(self.data[i], d)
        if i < self.offset:
            self.lazy[i] = self.composition(self.lazy[i], d)

    def propagate(self, l: int, r: int) -> None:
        for i in range(self.depth, 0, -1):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push((r - 1) >> i)

    def range_update(self, l: int, r: int, d: U) -> None:
        l += self.offset
        r += self.offset
        self.propagate(l, r)

        l2 = l
        r2 = r
        while l < r:
            if (l & 1) == 1:
                self.all_apply(l, d)
                l += 1
            if (r & 1) == 1:
                r -= 1
                self.all_apply(r, d)
            l >>= 1
            r >>= 1
        l = l2
        r = r2

        for i in range(1, self.depth + 1):
            if ((l >> i) << i) != l:
                self.update(l >> i)
            if ((r >> i) << i) != r:
                self.update((r - 1) >> i)

    def range_query(self, l: int, r: int) -> T:
        l += self.offset
        r += self.offset

        self.propagate(l, r)
        sml = self.identity_data()
        smr = self.identity_data()
        while l < r:
            if (l & 1) == 1:
                sml = self.operation(sml, self.data[l])
                l += 1
            if (r & 1) == 1:
                r -= 1
                smr = self.operation(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.operation(sml, smr)

    def point_set(self, p: int, d: T) -> None:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        self.data[p] = d
        for i in range(1, self.depth + 1):
            self.update(p >> i)

    def point_get(self, p: int) -> T:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        return self.data[p]

    def debug_print(self) -> None:
        i = 1
        while i <= self.offset:
            print(*((cnt, xxx[idx] if idx < m else idx) for cnt, idx in self.data[i:i * 2]))
            i <<= 1
        i = 1
        while i <= self.offset:
            print(self.lazy[i:i * 2])
            i <<= 1


INF = 1 << 60
identity_data = lambda: (0, INF)
identity_lazy = int


def operation(a: T, b: T) -> T:
    if a[0] >= b[0]:
        return a
    return b


def mapping(a: T, b: U) -> T:
    return (a[0] + b, a[1])


def composition(a: U, b: U) -> U:
    return a + b


input = sys.stdin.buffer.readline
n = int(input())
sections = []
xxx = {0}
for _ in range(n):
    l, r = map(int, input().split())
    sections.append((l, r))
    xxx.add(l)
    xxx.add(l + 1)
    xxx.add(r)
    xxx.add(r + 1)
xxx = sorted(xxx)
rev = {x: i for i, x in enumerate(xxx)}
m = len(xxx)

init = [(0, i) for i in range(m)]
lst = LazySegmentTreeInjectable.from_array(init, identity_data, identity_lazy, operation, mapping, composition)

sections_l = defaultdict(list)
sections_r = defaultdict(int)
for l, r in sections:
    i = rev[l]
    j = rev[r]
    sections_l[i].append(j)
    sections_r[j] += 1
    lst.range_update(i + 1, j, 1)

ans_count = 0
ans_l = 0
ans_r = 1
for l in range(m):
    if l in sections_l:
        for r in sections_l[l]:
            lst.range_update(l + 1, r, -1)
    if l in sections_r:
        lst.range_update(l + 1, lst.offset, -sections_r[l])

    cnt, r = lst.data[1]
    # print(f'{l=} {cnt=} {r=}')
    if ans_count < cnt and 0 <= xxx[l] < xxx[r] <= 1_000_000_000:
        ans_count = cnt
        ans_l = xxx[l]
        ans_r = xxx[r]

    if l in sections_l:
        for r in sections_l[l]:
            lst.range_update(r + 1, lst.offset, 1)

    # print(f'{l=} {ans_count=} {ans_l=} {ans_r=}')

cnt, r = lst.data[1]
assert cnt == 0 and r == 0

print(ans_l, ans_r)

G - Suitable Edit for LIS

問題文

長さ $N$ の整数列 $A$ が与えられます。高橋くんは、 $1$ 回だけ次の操作をします。
- $1$ 以上 $N$ 以下の整数 $x$ と、任意の整数 $y$ を選ぶ。$A_x$ を $y$ に置き換える。
操作をした後の $A$ の最長増加部分列の長さとしてあり得る最大の値を求めてください。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$

解法

1箇所を変えるだけでは、LISは高々1増えるか、増えないかとなる。
素朴なLISを求めた上で、「1増やせますか」を判定する問題と考えてよい。

好きな箇所を好きな値にできるので、だいたいは1増やせる。

具体的には、LISに “空間的かつ数値的な隙間” がある場合に可能となる。

LISに採用される添字列を $I=(i_1,...,i_k)$ として、以下をともに満たすような $j$ が存在する
- $1 \le j \le k-1$
- $i_{j+1} - i_{j} \gt 1$ … LISとして採用される位置の間に他の要素がある（空間的な隙間がある）
- $A_{i_{j+1}} - A_{i_{j}} \gt 1$ … 数値が2以上離れている（数値的な隙間がある）

添字列 $I$ は、$A$ によっては複数考えられるものの、そのうち1つでも上記を満たすものがあれば1増やせる。
全ての $I$ が上記を満たさないと、不可能ということになる。

ただし、便宜的に $A_0=-\infty,A_{N+1}=\infty$ とし、これらはLISに必ず含まれるとする。（最終的な答えからはもちろん除く）

【空間的かつ数値的な隙間の例】（ _ はLISに不採用の値であることを示す）

-∞  1  3  _  _  4  _  _  5  8  9  _  _  11  ∞
   ~~ ~~  ~~~~~~   ~~~~~~  ~~ ~~  ~~~~~~   ~~
   ① ①    ②       ②    ① ①    ③     ①

①は、LISとして採用される箇所が隣接していて、空間的な隙間がない例。
②は、値が隣接していて、数値的な隙間がない例となる。
③は、空間的かつ数値的な隙間がある。このいずれかを例えば 10 にすると、LISを1増やせる。

LISを求めるDPの過程で、「このような隙間のあるLISが1つでもあるか？」を判定したい。
LISを求めるアルゴリズムには、二分探索するものもあるが、今回はセグメント木で求めるものをベースとする。

yukicoder No.992 最長増加部分列の数え上げ #競技プログラミング - Qiita

LIS長のみを求めるシンプルなDPでは、以下のDPをセグメント木に載せ、 $A_i$ の小さい順に（同じならindexが大きい順に）埋めていく。

$DP_{仮}[i]=A_i$ を末尾とするような増加部分列の中で、最長のものの長さ

i     1  2  3  4  5   ...  i-2  i-1  i
A    11  5  2  7 12         11   5  10   ※Ai <= Aj となる j については、未処理なのでDP[j]=0
DP    0  1  1  2  0          0   3
     |-----------------------------|     ←この区間のDPの最大値+1が、DP[i]

今回求めたいものは、以下のように拡張する。

$DP[i]=A_i$ を末尾とするような増加部分列の中で（(a)最長のものの長さ, (b)条件達成済フラグ, (c)最長の時の最小末尾要素）

i       1  2  3  4  5   ...  i-2  i-1  i
A      11  5  2  7 12         11   5  10
DP(a)   0  1  1  2  0          0   3
      |-------------------------|         ←この区間のDP(a)の最大値と、
      |-----------------------------|     ←この区間のDP(a)の最大値が同じなら、空間的な隙間がある
      
2回のクエリで、空間的な隙間の有無を確認できる。
空間的な隙間があるとき、短い方のクエリの (c)+1 < Ai なら数値的な隙間もあると判定できる。

セグメント木では、(a)が長いもの > (b)がTrueのもの > (c)が小さいものの優先順位でマージしていく。

これで最後までDPした後、全体に対するクエリ結果の(b)がTrueなら1増やせる。

Python3

from atcoder.segtree import SegTree


def merge(a, b):
    if a[0] > b[0]:
        return a
    elif a[0] < b[0]:
        return b
    elif a[1] > b[1]:
        return b
    return a


n = int(input())
aaa = list(map(int, input().split()))
INF = 1 << 60
sgt = SegTree(merge, (0, INF), n + 1)
sgt.set(0, (0, -1))

order = [(a, -i) for i, a in enumerate(aaa, start=1)]
order.sort()
for a, i in order:
    i = -i
    l1, k1 = sgt.prod(0, i - 1)
    l2, k2 = sgt.prod(0, i)
    if l1 < l2:
        if k2 == -9:
            sgt.set(i, (l2 + 1, -9))
        else:
            sgt.set(i, (l2 + 1, a))
    else:
        if k2 == -9 or k1 + 1 < a:
            sgt.set(i, (l1 + 1, -9))
        else:
            sgt.set(i, (l1 + 1, a))

l1, k1 = sgt.prod(0, n)
l2, k2 = sgt.prod(0, n + 1)
if l1 < l2:
    if k2 == -9:
        ans = l2 + 1
    else:
        ans = l2
else:
    ans = l1 + 1
print(ans)

目次

AtCoder Beginner Contest 360 F,G問題メモ

F - InterSections

問題文

制約

解法

G - Suitable Edit for LIS

問題文

制約

解法