AtCoder Beginner Contest 262 F問題メモ

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)

目次

AtCoder Beginner Contest 262 F問題メモ

F - Erase and Rotate

問題

解法

①の場合

②の場合

補足事項など