AtCoder Beginner Contest 262 F,G問題メモ

AtCoder Beginner Contest 262

学生大会の予選を兼ねていたからか、いつもより難しめに感じた。

F - Erase and Rotate

• 長さ $N$ の数列 $P=(P_1,...,P_N)$ が与えられる。これははじめ、$1～N$ の順列である
• $K$ 回以下、以下の操作を行える
• 操作: 以下の2つから好きな方を選ぶ
  • $P$ の任意の要素を削除
  • $P$ の末尾要素を先頭に移動
• 作ることが可能な辞書順最小の数列を求めよ
• $1 \le N \le 2 \times 10^5$
• $0 \le K \le N-1$

場合分け時の挙動の違いに気がついたり、indexを正しく管理したり、といった注意力と実装力が求められる。

まず、最終形の先頭要素を決めてしまいたい。
$K$ 回以下の操作で先頭に持ってこれるのは、以下の範囲にある数字である。

N=9 K=3

8 5 3 1 9 4 2 6 7
~~~~~~~     ~~~~~    先頭からK+1個 or 末尾からK個

①先頭から $K+1$ 個以内にあれば、先頭～直前までを全て削除することで先頭に持ってこれる。
②末尾から $K$ 個以内にあれば、直後～末尾を全て削除or回転させた上で、その数字を回転させれば先頭に持ってこれる。

②は自身も回転操作しなければいけないので $K$ 個だが、 ①は自身より前を削除してしまえばよいので $K+1$ 個目まで先頭になれる点に注意。

で、同じ数字は現れないので、辞書順最小を作るにはこの中の最小値を先頭として採用確定してしまってよい。

最適な先頭要素が決まったら、もう回転を行う必要は無い。
よって、後は削除だけで、どこまで最終形の2項目以降を辞書順で小さくできるか、という問題となる。

ここで、最小要素を先頭に持ってくるのに①を使ったか②を使ったかで、処理の一部が異なる。

     K=5    5 3 1 9 4 2 6 8 7 10 11
     ↓
残り K=3    1 9 4 2 6 8 7 10 11      確定したところの次以降、
            ^ ~~~~~~~                残K+1 個の中の最小値を次に採用
     ↓
残り K=1    1 2 6 8 7 10 11
              ^ ~~~
     ↓
残り K=1    1 2 6 8 7 10 11
                ^ ~~~
     ↓
残り K=0    1 2 6 7 10 11      K=0 になったら終了
                  ^

     K=7    5 3 9 7 6 1 8 2 4
     ↓                          とりあえず"1"以降は全て回転させたものとして扱う
残り K=3    1 8 2 4|5 3 9 7 6

この後、①と同様に2項目以降を確定させていくのだが、 回転によって前に持ってきたものを削除する場合は、 回転させる代わりに削除したと考えればよいので、残りKは減らさなくてよい。

最小値を取得すべき区間の右端は、「確定したところの次か、回転させた境界のうち、より右にある方から $K+1$ 個」ということになる。

残り K=3    1 8 2 4|5 3 9 7 6
            ^ ~~~~~~~~~~~~~
↓
残り K=3    1 2 4|5 3 9 7 6
              ^ ~~~~~~~~~
     ↓
残り K=2    1 2 3 9 7 6
                ^ ~~~~~
     ↓
残り K=0    1 2 3 6
                  ^

こちらの方は、$K=0$ になったら終了、とは限らない。
まだ回転させた要素が残っていた場合は、それをコスト0で削除できるからである。

「確定したところが回転させた境界を越えた上で、$K=0$ になった」ら終了だが、 正しい判定（またはそれが正しい証明）を考えるのが難しければ「最後まで確定したら」でもよい。

$N$ と $K$ の関係によっては①も②も使える場合があるが、そのときは両方試してみればよい。
まぁ、上手くやればこの2つはまとめることもできるか。

区間最小値の取得はセグメント木が使える。これを使うのが混乱しづらいと思う。
または、区間の左端・右端はともに常に進んでいくので、Dequeを使って尺取法のように最小値を管理する「スライド最小値」を少し応用したものを使えば、logが取れて若干高速になる。

• スライド最大（最小）値・ヒストグラム内最大長方形問題を俯瞰する - Qiita

残り $K$ が残ったまま右端まで確定してしまうことがある。
その場合、確定した要素は全て昇順に並んでいるはずである。
長さが短い方が辞書順は小さくなるので、確定した数列の末尾から残り $K$ だけ、消す必要がある。
（そのため、操作回数は必ず $K$ 回、フルで使われる）

残K = 2    1 2 3 6 7 9
↓
残K = 0    1 2 3 6

Python3

class SegmentTreeInjectable:
    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            tree[i >> 1] = func(tree[i], tree[i ^ 1])
            i >>= 1

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


def erase_head(n, k, ppp, loc, i):
    k -= i
    ans = [ppp[i]]

    INF = 1 << 60
    sgt = SegmentTreeInjectable.from_array(ppp, lambda: INF, min)

    i += 1
    while k > 0 and i < n:
        m = sgt.get_range(i, min(n, i + k + 1))
        j = loc[m]
        ans.append(ppp[j])
        k -= j - i
        i = j + 1

    ans.extend(ppp[i:])

    if k > 0:
        ans = ans[:-k]

    return ans


def rotate(n, k, ppp, loc, i):
    ppp = ppp[i:] + ppp[:i]
    t = n - i
    k -= n - i
    INF = 1 << 60
    sgt = SegmentTreeInjectable.from_array(ppp, lambda: INF, min)
    ans = [ppp[0]]
    i = 1

    while k >= 0 and i < n:
        m = sgt.get_range(i, min(n, max(i, t) + k + 1))
        j = (loc[m] + t) % n
        ans.append(ppp[j])
        k -= max(0, j - max(i, t))
        i = j + 1

    ans.extend(ppp[i:])

    if k > 0:
        ans = ans[:-k]

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))

if k == 0:
    print(*ppp)
    exit()

loc = [0] * (n + 1)
for i, p in enumerate(ppp):
    loc[p] = i

head = min(ppp[:k + 1])
tail = min(ppp[-k:])
ans1 = erase_head(n, k, ppp, loc, loc[head])
ans2 = rotate(n, k, ppp, loc, loc[tail])
ans = min(ans1, ans2)
print(*ans)

G - LIS with Stack

• 整数列 $A=(A_1,...,A_N)$ が与えられる
• ここから、1つのスタックを利用して、増加部分列を生成する
• 具体的な方法
  • 空の列 $X$ と、空のスタック $S$ を用意する
    • スタックは、後に入れた物から順に取り出せる
  • $i=1,2,...,N$ の順に、以下の一連の操作を行う
    • $A_i$ を $S$ に積むか、捨てるかを選ぶ
    • 「$S$ から要素を1つ取り出し、$X$ の末尾に移動させる」ことを好きなだけ繰り返す（0回でもよい）
• この方法で $X$ として得られる最長の増加部分列（広義単調増加）の長さを求めよ
• $1 \le N \le 50$
• $1 \le A_i \le 50$

解法が分かってみれば確かに自然に見えるけど、、、性質を理解するのはなかなか難しい。

いくつかの単純なケースを考えてみる。

元々の A が単調減少な場合、全てを S に積んでから X に移動させるとよい
A: [5 4 3 2 1]  S: []  X: []
  ↓
A: []  S: [5 4 3 2 1]  X: []
  ↓
A: []  S: []  X: [1 2 3 4 5]

スタックを介すると並び順は逆転するため、元々のAは単調減少な成分が多い方がよさそう

単調増加でも、1個ずつ確定させれば可能
A: [1 2 3 4]  S: []  X:[]
  ↓
A: [2 3 4]  S: [1]  X:[]
  ↓
A: [2 3 4]  S: []  X:[1]
  ↓
... 1個ずつ A→S→X への移動を繰り返す

ただ、$A$ で増加している2つを両方とも利用するなら、途中で $X$ に確定させることが必要なので、 これより後に小さい値が来ても採用できなくなる。

A: [2 3 1]  S: []  X:[]
  ↓                     2をA→S→Xに移し、3をA→Sに移動
A: [1]  S: [3]  X:[2]

この時、Aに残る1は、現時点で末尾が 2 である X に積むことはできないので、捨てるしかない

一気に積んでからちょっとずつ取り出すこともできる

A: [10 9 6 5 2 1 4 3 8 7]
  ↓                                   先頭6つをSに積む
A: [4 3 8 7]  S: [10 9 6 5 2 1]
  ↓                                   1,2をXに移す
A: [4 3 8 7]  S: [10 9 6 5]  X: [1 2]
  ↓                                   Aの2つをSに積む
A: [8 7]  S: [10 9 6 5 4 3]  X: [1 2]
  ↓                                   3～6をXに移す
A: [8 7]  S: [10 9]  X: [1 2 3 4 5 6]
  ↓                                   Aの2つをSに積む
A: []  S: [10 9 8 7]  X: [1 2 3 4 5 6]
  ↓                                   7～10をXに移す
A: []  S: []  X: [1 2 3 4 5 6 7 8 9 10]

制約が小さいこともあり、区間DPでできないか考える。

ある隣接区間 $[l,m)$ と $[m,r)$ からそれぞれ何らかの増加部分列が得られるとして、 それを区間 $[l,r)$ 全体を通して操作した際にも、個々から得られるものをつなげたものが実現できるか？

これを「結合可能」と呼ぶとする。
結合可能かどうかの要件として、少なくとも増加部分列として使われる値の範囲がかぶっていないことが必要となる。

よって、増加部分列として使う値の最小と最大を含めたDPを考える。
他にもいくつか遷移できる条件（後述）があって、結局、以下のようなDPを構築すればよい。

• $DP[l,r,k,a,b]$:
  • $A$ の $[l,r)$ の範囲だけで作れる最長増加部分列のうち、最小値が $a$ 以上、最大値が $b$ 以下のものの長さ
  • $k=0$ なら、その長さを達成するための要素は元の $A$ で全て単調減少であり、全てを $S$ に積んだままにできる
  • $k=1$ なら、その長さを達成するにはどこかで元の $A$ で増加している部分があり、途中で何らかを $X$ に確定させないと実現できない

初期化は、区間の長さが1（$l+1=r$）の箇所に対して、以下のように初期化できる。
1要素だけなら当然、長さ1の最長増加部分列を作れる。またそれは $S$ に積んだままにできるので、$k=0$ である。

• $DP[i,i+1,0,A_i以下, A_i以上]=1$（$i=1,2,...,N$）

いま、$DP[l,r]$ を求めたくて、それより短い区間のDPの値は全て求まっているとする。

各 $k,a,b$ に対して、左か右を1個削ったものと等しくなる。

• $DP[l,r,k,a,b] \xleftarrow{\max} \max(DP[l+1,r,k,a,b], DP[l,r-1,k,a,b])$

$[l,r)$ を2つに分割して、結合可能なら結合した値で更新する。

遷移元として、以下の3種類の変数がある。

• どこで分割するか $m$:
  • $l+1～r-2$ で全探索
• 分割した前半区間、後半区間それぞれの $k=0/1$
• 値の範囲（一方は $a$ 以上 $b$ 以下、もう一方は $b$ 以上 $c$ 以下）という $a,b,c$ の組
  • 全探索した上で、前半区間が大小どちらになるかで2通り

つまり、$l,r$ ごとに以下の計算が必要になる。$l,r$ の総当たりも含め、だいたい $O(N^6)$ かかることになる。

• ($m$ の取り得る値)×($a,b,c$ の組の個数)×(前後の区間の $k$ 4通り)×(値の範囲 どちらが大か 2通り)

定数倍が軽く、数十分の1の係数が付くため、$N=50$ でも間に合うことを期待して考察を続ける。

遷移としては、$m,a,b,c$ を決めた上で、遷移元の $k$ と値範囲の大小に対し8通りの組み合わせがあるため、それぞれの遷移先を考える。

• 前半区間も後半区間も $k=0$ であり、かつ値の範囲が 前半区間＞後半区間
  • 結合可能
  • $k=0$ （元の $A$ で単調減少であるという条件）を継続できる
  • $DP[l,r,0,a,c] \xleftarrow{\max} DP[l,m,0,b,c]+DP[m,r,0,a,b]$

• 前半区間が $k=1$ であり、値の範囲が 前半区間＞後半区間
  • 結合不可
  • 前半区間を処理中に $X$ に確定させなければならないため、それより後で、より小さい値を入れられない

• それ以外の5通り
  • 結合可能だが、過程で少なくとも1回は $X$ に書き出す必要がある
  • $DP[l,r,1,a,c] \xleftarrow{\max} \max(該当する DP[l,m,○,○,○] と DP[m,r,○,○,○] の結合結果)$

これを区間の短い方から埋めていくと、$DP[1,N+1,k,1,50]$ での $k=0/1$ の大きい方が答え。

DPで、$a,b$ を「最小値がちょうど $a$ で最大値がちょうど $b$」ではなく「$a$ 以上 $b$ 以下」としているのは、 値の範囲に関して $a,b,c$ を固定した遷移が必要なためである。

「以上、以下」で実装していれば、上記の通り $a \le b \le c$ なる3組の探索 $O(A_{max}^3)$ でよい。

一方、もし「ちょうど」だけをDPに記録していたなら、 「前半区間の最小・最大」「後半区間の最小・最大」を探索せねばならず4重ループとなり、$O(A_{max}^4)$ となって計算量が増えてしまう。

このDPを「以上、以下」で実装するうえで必要なのは、 初期値で $DP[i,i+1,0,A_i以下,A_i以上]$ のように、ジャスト $A_i$ の箇所以外も埋めておくことのみであり、 後は特に意識しなくても、定義通りの更新がされていく。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:]

    MAX_A = 50
    dp = np.zeros((n, n + 1, 2, MAX_A + 1, MAX_A + 1), np.int8)

    for i in range(n):
        a = aaa[i]
        dp[i, i + 1, 0, :a + 1, a:] = 1

    for w in range(2, n + 1):
        for l in range(n - w + 1):
            r = l + w

            for x in range(1, MAX_A + 1):
                for y in range(x, MAX_A + 1):
                    for flg in (0, 1):
                        dp[l, r, flg, x, y] = max(dp[l, r - 1, flg, x, y], dp[l + 1, r, flg, x, y])

            for m in range(l + 1, r):
                for x in range(1, MAX_A + 1):
                    for y in range(x, MAX_A + 1):
                        for z in range(y, MAX_A + 1):
                            l0xy = dp[l, m, 0, x, y]
                            l0yz = dp[l, m, 0, y, z]
                            r0xy = dp[m, r, 0, x, y]
                            r0yz = dp[m, r, 0, y, z]
                            l1xy = dp[l, m, 1, x, y]
                            l1yz = dp[l, m, 1, y, z]
                            r1xy = dp[m, r, 1, x, y]
                            r1yz = dp[m, r, 1, y, z]
                            dp[l, r, 0, x, z] = max(dp[l, r, 0, x, z], l0yz + r0xy)
                            dp[l, r, 1, x, z] = max(
                                dp[l, r, 1, x, z],
                                l0xy + r0yz,
                                l0xy + r1yz,
                                l0yz + r1xy,
                                l1xy + r0yz,
                                l1xy + r1yz,
                            )

            # print(l, r)
            # print(dp[l, r, 0])
            # print(dp[l, r, 1])

    ans = dp[0, n].max()
    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)