AtCoder Beginner Contest 371 F,G問題メモ

AtCoder Beginner Contest 371

F - Takahashi in Narrow Road

問題文

東西に無限に続く道があり、道の上には $N$ 人の人がいます。
$i$ 番目 $(1\leq i\leq N)$ の人は、はじめ原点から東に $X_i$ メートル進んだところにいます。
人は道の上を東西に動くことができます。
具体的には、次の移動を好きなだけ行うことができます。
- 人を一人選ぶ。移動する先に他の人がいない場合、選んだ人を $1$ メートル東に、もしくは西に移動させる。
合計 $Q$ 個の用事があり、 $i$ 個目 $(1\leq i\leq Q)$ の用事は次の形式で表されます。
- $T _ i$ 番目の人が座標 $G _ i$ に到着する。
$Q$ 個の用事を先頭から順にすべて完了するために必要な移動回数の最小値を求めてください。

制約

$1\leq N\leq2\times10 ^ 5$
$0\leq X _ 1\lt X _ 2\lt\dotsb\lt X _ N\leq10 ^ 8$
$1\leq Q\leq2\times10 ^ 5$
$1\leq T _ i\leq N\ (1\leq i\leq Q)$
$0\leq G _ i\leq10 ^ 8\ (1\leq i\leq Q)$
入力はすべて整数

解法

人 $T_i$ が目標地点 $G_i$ に行くまでに他の人がいたら、ズリズリと押していく感じになる。
その押した分の人の移動コストも計上される。

たとえば用事 $i$ によって人 $T_i$ が $G_i$ に行くのに右（東）に移動するとして、ひとまず以下の解法が考えられる。

$k$ 人分右の人 $T_{i+k-1}$ まで影響する（移動が必要になる）とする
$T_i～T_{i+k-1}$ の現在の座標の合計値 $s$ を得る
各人の移動先の座標は公差1の等差数列なので、和 $t$ は $\frac{k(G_i+G_i+k-1)}{2}$ で求められる
$t-s$ がその用事のコストの和

なので、「各用事によってどの人まで影響するか」「その間の人の現在の座標の合計値」がわかればよい。

影響する人は必ず連続した区間になるので、座標をセグメント木などで管理すれば合計値はわかりそうだが、そのままだとどの人まで影響するのかわかりづらい。また、移動後の座標も等差数列で更新する必要があり、できなくはなかったはずだが、ややこしい。

典型の一種で、1ずつのズレを最初から織り込めば実装が楽になる。

$Y_i = X_i-i$ として定義する
用事を、 $Y_{T_i}$ を $H_i = G_i - T_i$ にするものと捉える

こうすると、影響する全ての人の目標地点が $H_i$ となる。

どこまで影響するかも、「 $T_i$ より右で、現在の $Y_j$ が $H_i$ より小さい人まで」（右に移動する場合）、「 $T_i$ より左で、現在の $Y_j$ が $H_i$ より大きい人まで」（左に移動する場合）となり、二分探索が使える。

また、移動後の更新も、区間を同じ値で更新すれば良いので、等差数列よりは実装しやすい。

ただ、区間更新・区間和取得が必要になるので遅延セグメント木を使うのだが、その木の上で二分探索を行う必要がある。
AtCoderLibraryの遅延セグメント木にはその機能がある（max_right, min_left）が、自作ではそこまで実装してない人もいそう（というか自分がしてなかった）。
いい機会なので、AtCoderLibraryの実装を参考に機能追加しておいた。

ノードに (区間長, 区間内の $Y_i$ の最小値, 最大値, 合計値) を持たせれば、左右いずれにもの影響範囲の二分探索、および区間合計値の取得がおこなえる。

Python3

        
          
          
              
              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 max_right(self, l: int, ev: Callable[[T], bool]) -> int:
        """
        [l, r) の集約値を x とした時 ev(x) = True となる最も右のindex r を得る
        ただし二分探索可能である前提とする。
        （rがある特定の値より小さければ全てTrue, 大きければ全てFalseとなるような性質を持っている）
        """
        op = self.operation
        data = self.data
        push = self.push
 
        l += self.offset
        for i in range(self.depth, 0, -1):
            push(l >> i)
        sm = self.identity_data()
        while True:
            while l & 1 == 0:
                l >>= 1
            sm_tmp = op(sm, data[l])
            if not ev(sm_tmp):
                while l < self.offset:
                    push(l)
                    l <<= 1
                    sm_tmp = op(sm, data[l])
                    if ev(sm_tmp):
                        sm = sm_tmp
                        l += 1
                return l - self.offset
            sm = sm_tmp
            l += 1
            if (l & -l) == l:
                break
        return self.n
 
    def min_left(self, r: int, ev: Callable[[T], bool]) -> int:
        """
        [l, r) の集約値を x とした時 ev(x) = True となる最も左のindex l を得る。
        ただし二分探索可能である前提とする。
        （lがある特定の値より小さければ全てFalse, 大きければ全てTrueとなるような性質を持っている）
        """
        op = self.operation
        data = self.data
        push = self.push
 
        r += self.offset
        for i in range(self.depth, 0, -1):
            push((r - 1) >> i)
 
        sm = self.identity_data()
        while True:
            r -= 1
            while 1 < r and (r & 1) == 0:
                r >>= 1
            sm_tmp = op(data[r], sm)
            if not ev(sm_tmp):
                while r < self.offset:
                    push(r)
                    r = (r << 1) + 1
                    sm_tmp = op(data[r], sm)
                    if ev(sm_tmp):
                        sm = sm_tmp
                        r -= 1
                return r + 1 - self.offset
            sm = sm_tmp
            if (r & -r) == r:
                break
        return 0
 
    def debug_print(self) -> None:
        i = 1
        while i <= self.offset:
            print(*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, -INF, 0)
identity_lazy = lambda: INF
 
 
def operation(a, b):
    return (a[0] + b[0], min(a[1], b[1]), max(a[2], b[2]), a[3] + b[3])
 
 
def mapping(a, b):
    if b == INF:
        return a
    return (a[0], b, b, a[0] * b)
 
 
def composition(a, b):
    if b == INF:
        return a
    return b
 
 
n = int(input())
xxx = list(map(int, input().split()))
init = [(1, x - i, x - i, x - i) for i, x in enumerate(xxx)]
lst = LazySegmentTreeInjectable.from_array(init, identity_data, identity_lazy, operation, mapping, composition)
 
ans = 0
q = int(input())
for _ in range(q):
    t, g = map(int, input().split())
    t -= 1
    g -= t
    s = lst.point_get(t)
    if s[3] == g:
        continue
    if s[3] < g:
        j = lst.max_right(t, lambda a: a[2] < g)
        res = lst.range_query(t, j)
        ans += (j - t) * g - res[3]
        lst.range_update(t, j, g)
    else:
        t += 1
        j = lst.min_left(t, lambda a: a[1] > g)
        res = lst.range_query(j, t)
        ans += res[3] - (t - j) * g
        lst.range_update(j, t, g)
 
print(ans)

            

        
      

G - Lexicographically Smallest Permutation

問題文

$(1,2,\ldots,N)$ の並べ替え $P=(P _ 1,P _ 2,\ldots,P _ N),A=(A _ 1,A _ 2,\ldots,A _ N)$ が与えられます。
あなたは、次の操作を $0$ 回以上好きな回数行うことができます。
- $i=1,2,\ldots,N$ に対して一斉に $A _ i$ を $A _ {P _ i}$ で置き換える。
得られる $A$ としてありえるもののうち、辞書順で最小のものを出力してください。

制約

$1\leq N\leq2\times10 ^ 5$
$1\leq P _ i\leq N\ (1\leq i\leq N)$
$P _ i\neq P _ j\ (1\leq i\lt j\leq N)$
$1\leq A _ i\leq N\ (1\leq i\leq N)$
$A _ i\neq A _ j\ (1\leq i\lt j\leq N)$
入力はすべて整数

解法

indexに混乱しやすいので、落ち着いて問題を把握する。

初期状態と途中状態が分かりづらいので、 $A_i$ と言ったときには初期状態の $A$ を指すことにする。

置換グラフは、いくつかのサイクルに分解できる。

$i→P_i$ を辿っていって、たとえば $1→3→7→10→1→...$ のサイクルが繰り返されるとしたら、 $i=1$ の位置に来る値は $A_1→A_3→A_7→A_{10}→A_1→...$ と変わっていくことになり、それ以外の値には変化しない。

辞書順最小なので、 $i=1$ には、持ってこられる中で一番小さい値を持ってきたい。
幸い、 $A$ に同じ値は無いので、持ってくる $A_i$ は一意に決まる。
上例では、 $(A_1,A_3,A_7,A_{10})$ の中から選べばよい。

この時、答えを作るための最適な操作回数を $X$ として、 $X \equiv r \mod{m}$ の $r,m$ が決まったことになる。
上例で $A_7$ が最小だったとして、2回、6回、10回、、、の操作を行ったときに $i=1$ の位置に $A_7$ が来るので、 $m$ はサイクル長の $4$ 、 $r$ はその中の最適な操作回数 $2$ として $X \equiv 2 \mod{4}$ ということが決まる。

これで、1を含むサイクル（ $i=1,3,7,10$ ）の値が決定する。

次、最終的に $i=2$ に来る値を考える。

2を含むサイクルが、 $2→8→5→6→4→9→2→...$ の長さ $l=6$ だったとする。
先ほどの制約から、今回は全ての値を取れるわけではない。 $X \equiv r \mod{m}$ に矛盾しないようにする必要がある。

2つのサイクル長のGCDが1なら、何回も周期を繰り返せば全ての値を回れるが、そうで無い場合、例えば今回は $\mathrm{gcd}(m,l)=2$ なので、 $r \mod{\mathrm{gcd}(m,l)}$ 、つまり $2 \mod{2}$ と等しい操作回数しか選べない。

よって、候補は偶数回操作された $(A_2,A_5,A_4)$ の中から選ぶことになる。
この中の最小値を $i=2$ に持ってくればよい。

$A_4$ が最小だったとして、これは今のサイクルで4回操作された値なので、 $X \equiv 4 \mod{6}$ という制約が加わる。

これを先ほどの制約とマージする。
中国剰余定理を使うと、「 $m_1$ で割って $r_1$ 余り、 $m_2$ で割って $r_2$ 余る数 $X$ は、 $\mathrm{lcm}(m_1,m_2)$ で割って○○余る」の○○を求められる。
今回の場合、 $X \equiv 10 \mod{12}$ となる。

このようにして、前から「今の制約内で選択できる $A_i$ の最小値」を求め、「その $A_i$ を希望の位置に持ってくる操作回数の制約を、今の制約とマージする」を繰り返せばよい。

問題となるのが、LCMを繰り返すと、例えばサイクル長が全て異なる素数だった場合に $m$ がどんどん巨大になる。
実際に「総和が $N \le 2 \times 10^5$ を超えない範囲での、素数のLCM=総積」を求めると、700桁くらいの数になる。

確かに大きいが、まぁ、多倍長整数を扱える言語なら致命的な水準ではなく、そのまま扱って問題ない。
おこなう演算にもよるが、桁数が万まで来ると数秒では無茶かなというイメージ。

Python3