AtCoder Regular Contest 189 (Div. 2) B,C,D,E問題メモ

AtCoder Regular Contest 189 (Div. 2)

今回のARCから、簡単めのDiv.2と、難しめのDiv.1にわかれることになったらしい。
Div.2は、ABCのE～Gくらいがいっぱいある印象。

今まで以上にそれぞれのレート帯に適したコンテストに参加できるようになってうれしいね。

B - Minimize Sum

問題文

数直線上に $N$ 個のコマが置かれており、最初、すべてのコマは相異なる座標に置かれています。
- 最初にコマが置かれている座標は $X_1,X_2,\ldots, X_N$ です。
高橋君は、次の操作を繰り返し ($0$ 回でも良い) 行う事ができます。
- $1\leq i\leq N-3$ をみたす整数 $i$ を $1$ つ選ぶ。
- 座標が小さい方から $i$ 番目のコマのある位置と $i+3$ 番目のコマのある位置の中点を $M$ とする。
- 座標が小さい方から $i+1$ 番目のコマと $i+2$ 番目のコマを、それぞれ $M$ と対称な位置に動かす。
なお、本問題の制約下において、どのように操作を繰り返し行ってもすべてのコマが相異なる座標に置かれていることが証明できる。

高橋君の目標は $N$ 個のコマが置かれている座標の総和を最小にする事です。
操作を繰り返した後の座標の総和としてあり得る最小の値を求めてください。

制約

$4 \leq N \leq 2\times 10^5$
$0 \leq X_1 \lt X_2 \lt \cdots \lt X_N \leq 10^{12}$
入力はすべて整数

解法

変な操作は差分に着目してみる。定石の1つなのに思いつけなかったね。

             M
 |<---a--->|<-b->|<--c-->|
x0        x1    x2      x3
            ↓
 |<--c-->|<-b->|<---a--->|
x0      x1    x2        x3

差分に着目して操作を観察すると、3つ並んだ差分のうち、1番目と3番目をスワップすることに相当する。
つまり操作を繰り返すことで、偶奇別に、差分を好きな順に並び替えられる。

座標の総和を最小にするためには、なるべく左に小さい差分を持ってくるのがよい。
差分を偶数番目と奇数番目に分けてそれぞれでソートし、復元した結果が答えとなる。

Python3

def solve(n, xxx):
    even_space = []
    odd_space = []
    for i in range(n - 1):
        if i % 2 == 0:
            even_space.append(xxx[i + 1] - xxx[i])
        else:
            odd_space.append(xxx[i + 1] - xxx[i])
    even_space.sort()
    odd_space.sort()
    yyy = [xxx[0]]
    for i in range(n - 1):
        if i % 2 == 0:
            yyy.append(yyy[-1] + even_space[i // 2])
        else:
            yyy.append(yyy[-1] + odd_space[i // 2])
    return sum(yyy)


n = int(input())
xxx = list(map(int, input().split()))
ans = solve(n, xxx)
print(ans)

C - Balls and Boxes

問題文

$N$ 個の箱があります。
- $i = 1, 2, \ldots, N$ について、$i$ 番目の箱には $A_i$ 個の赤いボールと $B_i$ 個の青いボールが入っています。
また、数列 $(1, 2, \ldots, N)$ を並べ替えた $2$ つの順列 $P = (P_1, P_2, \ldots, P_N)$ と $Q = (Q_1, Q_2, \ldots, Q_N)$ が与えられます。
高橋君は、下記の操作を好きな回数（ $0$ 回でも良い）だけ繰り返すことができます。
- $1 \leq i \leq N $を満たす整数 $i$ を選び、$i$ 番目の箱に入っているすべてのボールを箱から取り出して手に持つ。
- 手に持っているすべての赤いボールを $P_i$ 番目の箱に入れる。
- 手に持っているすべての青いボールを $Q_i$ 番目の箱に入れる。

高橋君の目標は、上記の操作の繰り返しによって、$X$ 番目の箱以外にボールが入っていない状態にすることです。
この目標を達成することが可能かどうかを判定し、可能な場合はそのために行う操作回数の最小値を出力してください。

制約

$2 \leq N \leq 2 \times 10^5$
$0 \leq A_i, B_i \leq 1$
$1 \leq P_i, Q_i \leq N$
$P,Q$ はそれぞれ $(1, 2, \ldots, N)$ の順列
$1 \leq X \leq N$
入力はすべて整数

解法

赤・青のボールを移し替える箱を示すそれぞれのグラフ（$i→P_i, i→Q_i$ に辺を張ったグラフ）は置換グラフなので、いくつかのサイクルに分けられる。

i  1  2  3  4  5  6  7  8  9 10
P  1  4  9  5  8  2  3  6 10  7
Q  7  4  9 10  6  3  1  2  8  5
                                     ☆
P  ①┐  ②→④→⑤→⑧→⑥  ③→❾→⑩→❼    ●: ボールが入った箱
   ＾┘  ＾--------------┘  ＾----------┘    ☆: ボールを集める箱（X）
                   ☆
Q  ①→⑦  ②→④→⑩→❺→❻→③→❾→⑧
   ＾--┘  ＾--------------------------┘

どちらか一方のグラフでも、☆を含むサイクル以外にボールが入った箱があったらアウト。

それ以外の場合、ボールが入っている箱のうち、☆まで一番遠い頂点から、順番に操作していくしかない。

P'  ❼→③→❾→☆
Q'  ❺→❻→③→❾→⑧→②→④→☆

基本的には2つの操作回数の和が答えとなるのだが、このうち、最長共通部分列の長さだけ操作を一度に行って節約できる。

    ⑦          __________
      ↘      ／          ↘      最長共通部分列は ③,⑨,☆
        ③→⑨              ☆    ③と⑨に対する操作を、一度に行える
      ↗      ↘          ↗
⑤→⑥          ⑧→②→④

通常の最長共通部分列は、2つの列の長さを $n,m$ として $O(nm)$ かかるが、「いずれかに同じ要素が出てこない」場合は、$O(n \log{m})$ などでおこなえる。

LISに言い換えられる。$Q'$ を、$P'$ での登場順に $1,2,...$ と振り直す（出てこない値はINF）と、最長増加部分列がそのまま最長共通部分列となる。

P': 7,3,9,☆  →  1,2,3,4
Q':           →  INF,INF,2,3,INF,INF,INF,4

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 debug_print(self) -> None:
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.data[i:i * 2]))
            i <<= 1
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.lazy[i:i * 2]))
            i <<= 1


def to_loop(x, aaa, ppp):
    n = len(ppp)
    rev = [0] * n
    for i, p in enumerate(ppp):
        p -= 1
        rev[p] = i
    loop = [x]
    y = rev[x]
    while y != x:
        loop.append(y)
        y = rev[y]
    while loop and aaa[loop[-1]] == 0:
        loop.pop()

    s = set(loop)
    for i in range(n):
        if i not in s and aaa[i] == 1:
            raise Exception

    return loop


def solve(n, x, aaa, bbb, ppp, qqq):
    x -= 1
    try:
        p_loop = to_loop(x, aaa, ppp)
        q_loop = to_loop(x, bbb, qqq)
    except:
        return -1

    if len(p_loop) <= 1:
        ans = max(0, len(q_loop) - 1)
        return ans
    elif len(q_loop) <= 1:
        ans = max(0, len(p_loop) - 1)
        return ans

    p_loop.reverse()
    q_loop.reverse()
    if len(p_loop) > len(q_loop):
        p_loop, q_loop = q_loop, p_loop
    appear = {}
    for i, q in enumerate(q_loop):
        appear[q] = i

    m = len(q_loop)
    sgt = LazySegmentTreeInjectable(m, int, int, max, max, max)
    for p in p_loop:
        if p not in appear:
            continue
        i = appear[p]
        k = sgt.point_get(i)
        sgt.range_update(i, m, k + 1)

    c = sgt.point_get(m - 1)
    ans = len(p_loop) + len(q_loop) - 2 - (c - 1)
    return ans


n, x = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
ans = solve(n, x, aaa, bbb, ppp, qqq)
print(ans)

D - Takahashi is Slime

問題文

$N$ 体のスライムが左右一列に並んでいます。
- $i = 1, 2, \ldots, N$ について、左から $i$ 番目のスライムの大きさは $A_i$ です。
$K = 1, 2, \ldots, N$ のそれぞれの場合について、下記の問題を解いてください。
- 初期状態で左から $K$ 番目にいるスライムが高橋君です。
- 高橋君が下記の行動を好きな回数（ $0$ 回でも良い）だけ行ったあとの、高橋君の大きさとしてあり得る最大値を求めてください。
  - 高橋君に隣接するスライムのうち、高橋君より大きさが真に小さいものを選んで吸収する。
  - その結果、吸収されたスライムは消滅し、高橋君の大きさは吸収したスライムの大きさだけ増加する。

制約

$2 \leq N \leq 5 \times 10^5$
$1 \leq A_i \leq 10^9$
入力はすべて整数

解法

少しのメモ化の工夫をすれば、愚直に近いことをやっても意外と計算量が増えない。

$K$ が小さい方から答えを求めていく。$K=i$ の時の答えを求めるとする。

$i$ から、1回毎に以下の法則に則って吸収する。

左を吸収可能ならする。無理なら右を吸収可能ならする。それも無理なら終わり。

左のスライム $j$ を吸収した場合、$j$ を始点とした結果を再利用できないか確認する。
$j$（$j \lt i$）から始めた場合の以下が記録してあるものとする。

答え $B_j$
吸収した最も左のスライム $L_j$
吸収した最も右のスライム $R_j$

$i \le R_j$ の場合、$B_i=B_j$ である。
「$j$ から始めて $i$ を吸収可能」「$i$ から始めて $j$ を吸収可能」がともに成り立つ場合、両者から左右に吸収できる範囲は変わらない。

.....  j  ...  i  .....    jがi、または iがj を吸収した時点で、
      [---------]          ←①両者が確実に吸収している範囲
[---]                      ←②jだけが吸収しているかもしれない範囲
                  [---]    ←③iだけが吸収しているかもしれない範囲

$j$ が $i$ 吸収前に②の範囲を吸収可能な場合、$i$ も $j$ 吸収後に②を吸収可能である（$i$ 吸収前の $j$ より $j$ 吸収後の $i$ の方が必ず大きいので）。 ③の範囲にも同じ事が言えるので、結局、相手が自身吸収前に吸収可能な範囲は、自身も相手吸収後に吸収できる。
同じ途中状況に持っていくことができるため、答えも同じになる。

$i \gt R_j$ の場合、少なくとも $L_j$ まで、吸収するスライムの範囲を一気に左に伸ばせる。

これも、上記と似た考え方で「$\mathrm{Sum}(A[j:R_j])$（あるいはそれ以下の範囲の合計）をもって $j-1,j-2,...,L_j$ を吸収していけたのなら、それより大きい $\mathrm{Sum}(A[j:i])$ をもってすれば必ず同じ範囲を吸収できる」といえる。

この2つの再利用により、全位置から探索を開始しても間に合うようになる。

計算量の見積もりは、少しあやふやだが、

左側への探索は、$N$ 個の始点を通して $O(N)$ 回。
あるスライムが、自身の右にあるスライムのうち何個から“左側への探索”の過程で吸収されるかを考えると、最初に1回吸収されたら以降はスキップされるので、$O(1)$ 個となる。
あとは、「吸収を試みるが失敗」というのが、右側への探索で吸収が発生する分だけ追加で発生する。

右側への探索は、、、どう考えればいいだろうね。

「あるスライム $j$ が、自身の左にある何個のスライムから、重ねて探索対象とされうるか」を考える。
$i_1 \lt i_2 \lt ... \lt i_k \lt j$ なる $i=(i_1,...,i_k)$ から探索されるとして、

$i_2$ は $i_1$ に吸収されているので、左への探索で $i_1$ を吸収可能になったら、答えを再利用して終了する。
$i_3$ は $i_2$ に吸収されているので、左への探索で $i_2$ を吸収可能になったら、答えを再利用して終了する。
…

でも、そうならずにいずれの $i$ も $j$ まで探索が続いているということは、

$A_{i_{k-1}} \ge \mathrm{sum}(A[i_{k}:j])$
$A_{i_{k-2}} \ge \mathrm{sum}(A[i_{k-1}:j])$
$A_{i_{k-3}} \ge \mathrm{sum}(A[i_{k-2}:j])$
:
$A_{i_1} \ge \mathrm{sum}(A[i_{2}:j])$

が成り立つので、少なくとも $i$ を遡るたびに2倍ずつになっていかないといけない。
よって、$k \le \log{A_{\max}}$ で抑えられることが分かる。

1つのスライム当たり、右への探索対象となる回数は最大 $\log{A_{\max}}$ より、全体でも $O(N \log{A_{\max}})$ となる（と思う）。

Python3

import random
from itertools import accumulate


def solve(n, aaa):
    INF = 1 << 60
    acc = [0] + list(accumulate(aaa))
    aaa = [INF] + aaa + [INF]
    lll = [-1] * (n + 2)
    rrr = [-1] * (n + 2)
    ans = [0] * (n + 2)

    for i in range(1, n + 1):
        l = i
        r = i
        w = aaa[i]
        while True:
            if aaa[l - 1] < w:
                l -= 1
                if rrr[l] >= i:
                    w = ans[l]
                    l, r = lll[l], rrr[l]
                    break
                elif lll[l] < l:
                    w += acc[l] - acc[lll[l] - 1]
                    l = lll[l]
                else:
                    w += aaa[l]
            elif aaa[r + 1] < w:
                r += 1
                w += aaa[r]
            else:
                break
        ans[i] = w
        lll[i] = l
        rrr[i] = r

    return ans[1:n + 1]


n = int(input())
aaa = list(map(int, input().split()))

# n = 500000
# aaa = [random.randint(1, 100000) for _ in range(n)]

ans = solve(n, aaa)
print(*ans)

E - Straight Path

問題文

$N$ 頂点の完全グラフ $G$ の辺に正整数の番号を付ける方法のうち、以下の条件を満たすものを「良い完全グラフ」と言うことにします。
- $N$ 個の頂点を全てちょうど $1$ 回ずつ通るパスのうち、通った辺の番号を通った順に並べた数列が広義単調増加になるものが存在しない。

「良い完全グラフ」が存在するか判定し、存在する場合は「辺に付ける正整数の番号の最大値」が最小になるものを $1$ 個構築してください。

制約

$2 \le N \le 20$

解法

実験すると見えてくる。見えたら割と単純で、複雑な実装は要らない。

愚直は計算量がすごいことになるのが目に見えていて（実際、$N=7$ あたりで既に純粋な全探索は厳しいものがある）、なかなかこの問題を本番中に実験しようとする勇気は出ないなあ。

小さい $N$ の結果を観察して、ある程度「こうするのが良さそう」と法則を見いだして決め打ちしつつ、少しずつ大きい $N$ を試していく、ということを繰り返すと、$N=4$ および $N \ge 6$ では以下の構築が可能であるとわかる。

頂点を半分に分け、同じグループ同士では“1”の辺を張る
異なるグループ間には、後述の法則に従って“2”または“3”の辺を張る

最大値を3とした良い完全グラフが得られる。

最大値2が不可能という証明は、帰納法で示せる。
頂点数 $n-1$ のグラフに、ある値の割り振り方をした時、単調増加になるパスがあったとすると、頂点 $n$ を追加して既存の頂点との間の辺の値をどのようにしても、必ず $n$ を含んだ単調増加パスに拡張できる。 $N=3$ などで、最大値2ではどのような値の割り振り方にも単調増加パスが存在することが全探索で示されるので、それ以上の頂点数のどのような値の割り振り方にも必ず含まれる。

解説 - AtCoder Regular Contest 189 (Div. 2)

$N$ 偶数の時

GrpA  GrpB
  ○--○
GA  ×  GB      ※1,2,3の辺の内、2の辺のみ描画
  ○--○
 
Ga○--○Gb

2つの同数のグループ（GrpA,GrpB、上図では縦に並んだ3つずつが同一グループ）に分け、両グループから適当に1点ずつ選ぶ。（$a,b$）
頂点集合を、以下のように命名する。

GrpA の $a$ 1頂点からなる集合: $G_{a}$
GrpA の $a$ 以外からなる集合: $G_{A}$
GrpB の $b$ 1頂点からなる集合: $G_{b}$
GrpB の $b$ 以外からなる集合: $G_{B}$

GrpA内、GrpB内の頂点同士は“1”の辺を張る。
異なるGrp間は、「$G_a$ と $G_b$」「$G_A$ と $G_B$」には“2”の辺を張る（上図で明示された辺）。
「$G_a$ と $G_B$」「$G_A$ と $G_b$」には“3”の辺を張る。

「GrpA,GrpBの2つに分け、グループ内に“1”、グループ間に“2”以上の辺を張る」ということをした時点で、「GrpAをいくつか巡る→GrpBに移る→GrpBをいくつか巡る」というパスが一切禁じられる。
よって、「GrpA→GrpB→GrpA→…」のように、グループ間を交互に渡り歩くパスしかなくなる。
（最初にGrpA内をいくつか巡ることもできない。交互に渡り歩くための個数が足りなくなるので）

たとえば $G_A$ から開始した場合、どこかで $G_a$ または $G_b$ に移らなければならないが、一度移ると、もう $G_A-G_B$ 間、$G_a-G_b$ 間は移動できなくなる。
たとえば $G_A→G_b$ に移った場合、以降は $G_A$ と $G_b$ を交互に移動するしかなくなり、$G_a$ に移動できなくなる。
他の移動方法でも、3つめの頂点集合に移動した時点で、4つめには移動できなくなる。

このため、単調増加パスは不可能であることがわかる。

$N$ 奇数の時

GrpA  GrpB
  ○--○
GA  ×  GB
  ○--○
  
  ○--○Gb
Ga  ／
  ○

サイズが1だけ異なるように2つに分ける。
サイズが大きい方（GrpA）から2点、小さい方（GrpB）から1点選び、あとは偶数の時と同じように辺を張る。

偶数の時と違うのは、「最初に1回だけ、GrpA内の2点間を移動してから、GrpA-GrpB間の交互移動を開始することもできる」という点である。

そのため、$G_a$ が1点しかない場合、最初にその1点から開始することで「$G_a-(1)→G_A-(2)→G_B-(2)→...-(2)→G_A-(3)→G_b$」のような単調増加パスが作れてしまう。
$G_a$ を2点とすることで、これを防げる。

その他は偶数の時と同じ。

$N=5$ の時は、GrpAが3点しかなく、$G_A,G_a$ をいずれも2点以上にすることができないため、コーナーケースとなる。
この場合は最大値が4まで必要であり、サンプルに答えがある（また、全探索しても十分高速である）。
まさか $N=5$ で最大値が最大になるとは思わなんだ。

構築はこのように単純なので、$N=3000$ くらいでも出力はできるのだが、制約が $N=20$ と控えめなのは何でだろう。ジャッジが難しいからかな。（実際、どうやってるんだろ）

Python3


def solve(n):
    if n <= 3:
        return None
    if n == 5:
        return [[0, 1, 1, 3, 3], [1, 0, 3, 2, 4], [1, 3, 0, 4, 2], [3, 2, 4, 0, 1], [3, 4, 2, 1, 0]]

    edges = [[0] * n for _ in range(n)]
    for i in range(n // 2):
        for j in range(i + 1, n // 2):
            edges[i][j] = edges[j][i] = 1
    for i in range(n // 2, n):
        for j in range(i + 1, n):
            edges[i][j] = edges[j][i] = 1

    a_thr = n // 2 - 1
    b_thr = n - 1 if n % 2 == 0 else n - 2
    for i in range(n // 2):
        for j in range(n // 2, n):
            if (i < a_thr) ^ (j < b_thr) == 0:
                edges[i][j] = edges[j][i] = 2
            else:
                edges[i][j] = edges[j][i] = 3

    return edges

n = int(input())
ans = solve(n)
for i in range(n - 1):
    print(*ans[i][i + 1:])

目次

AtCoder Regular Contest 189 (Div. 2) B,C,D,E問題メモ

B - Minimize Sum

問題文

制約

解法

C - Balls and Boxes

問題文

制約

解法

D - Takahashi is Slime

問題文

制約

解法

E - Straight Path

問題文

制約

解法

$N$ 偶数の時

$N$ 奇数の時