AtCoder Regular Contest 225 A,B,C,D問題メモ

AtCoder Regular Contest 225

ひらめけば実装は簡単、という問題が多かった印象。

Writer のブログ
- 【コンテスト開催記】AtCoder Regular Contest 225 - milkcoffeeのブログ

A - Four Coloring

問題文

$N \times N$ のグリッド $X$ があります。マス $(i,j)$ には整数 $X_{i,j}$ が書かれています。
- 整数は $1,2,3,4$ のいずれかであり、4方向に隣接するマスは異なる整数が書かれています。
あなたは $N \times N$ のグリッド $Y$ を用意し、各マスに整数を書き込みます。$(i,j)$ に書き込む整数を $Y_{i,j}$ と表します。
以下の条件を満たすような書き込み方を $1$ つ求めてください。
- 書き込む整数は $1,2,3,4$ のいずれかである。隣接するマスの値は同じでも良い。
- 隣接する任意の $2$ マス $(i_1,j_1), (i_2,j_2)$ について、以下が成り立つ。
  - $X$ で2マスの差が $1$ なら、$Y$ で同じ箇所の差は $2$ 以上
    - $|X_{i_1,j_1} - X_{i_2,j_2}|=1$ ならば $|Y_{i_1,j_1} - Y_{i_2,j_2}|\ge 2$
  - $X$ で2マスの差が $2$ 以上なら、$Y$ で同じ箇所の差は $1$ 以下
    - $|X_{i_1,j_1} - X_{i_2,j_2}|\ge2$ ならば $|Y_{i_1,j_1} - Y_{i_2,j_2}|\le 1$
なお、条件を満たすような色の塗り方は必ず存在することが証明できます。

制約

$2 \le N \le 500$
$1 \le X_{i,j} \le 4$
$X$ の隣接するマスは異なる色で塗られている。
入力される値は全て整数

解法

「$X$ で1の箇所は $Y$ では○にする、のような1対1対応の置換がある」という可能性を考えてみる。

すると、$[1,2,3,4]→[3,1,4,2]$ という置換が条件を満たすことが分かる。

Python3

def solve(n, grid):
    mapping = [0, 3, 1, 4, 2]
    for i in range(n):
        for j in range(n):
            grid[i][j] = mapping[grid[i][j]]
    return grid


n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, grid)
for row in grid:
    print(*row)

発展

色の種類数 $K=5$ の時

構築が可能である。
グリッドを二部グラフに分け、それぞれで別々の置換を用いると達成できる。

■□■□    ■: (1,2,3,4,5) → (2,1,3,5,4)
□■□■    □: (1,2,3,4,5) → (4,5,3,1,2)
■□■□
□■□■

「$X$ では同じ値が隣接しないが、$Y$ ではしてもいい」という制約が有効に働く。

$K \ge 6$ の時

$K \ge 6$ の時は反例が存在する。
といっても、$N$ が小さいうちは結構成り立ってしまうので、見つけづらい。

一例として、以下のような構造がグリッドに含まれていると不可能である。

X                    Y
1 . 3 . 1 . 3 . 1    a - b - c - d - e
.   .   .   |   .    |   |   |   .   |
3 . 5 - 4 . 2 . 4    f - g . h - i - j
.   |   |   .   .    |   .   .   |   |
1 . 6 . 3 . 5 - 6    k - l - m - n . o
.   .   .   |   .    |   |   |   .   |
4 . 2 - 1 . 4 . 1    p - q . r - s - t

不可能の証明には、差分制約系（牛ゲー）への帰着が役立つ。

牛ゲー - yaketake08's 実装メモ

グリッドをグラフと捉える。
マス（頂点）$u$ に書き込む値を $Y_u$ と表す。
$Y$ における差が1以下の辺 $(u,v)$ は、$Y_u-Y_v \le 1$ かつ $Y_v - Y_u \le 1$ という制約になる。
$Y$ における差が2以上の辺 $(u,v)$ は、その方向を決め打ってやれば、$Y_u-Y_v \le -2$（または $u,v$ 逆）という制約になる。

全ての制約が $Y_v - Y_u \le w_k$ で与えられたときに、そのような割り当てが可能かは、$u→v$ に重み $w_k$ の辺を持つグラフに負閉路が存在しないことと一致する。

上記の $Y$ において、“-” は双方向の重さ $1$ の辺、“.” は方向を決めれば一方通行の $-2$ の辺となる。
“.” は7個あるが、この方向の決め方 $2^7$ 通り全てで、どこかで負閉路が発生してしまうことが全探索により分かる。

B - Independent Nim

問題文

長さ $N$ の整数列 $A$ があります。$A$ の各要素は $0$ または $1$ です。
Alice と Bob がゲームをします。Alice から始めて以下の操作を交互に行います。
- $A$ の要素から $1$ であるものを $1$ つ以上選び、それらを $0$ にする。ただし、隣接する要素を同時に選ぶことはできない。
先に操作を行えなくなったプレイヤーの負けです。
両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 10^5$
$1 \le N \le 2\times 10^5$
$A_i = 0$ または $A_i = 1$
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
入力される値は全て整数

解法

$0$ を挟んだ2つの $1$ の連続区間は互いに干渉せず、それぞれを最適に処理できる。

1 1 1 0 1 1 1 1
~~~~~   ~~~~~~~  ←それぞれを最適なように処理できる

なので、まず初期状態が $1$ のみの場合を考えてみる。

1     → 先手必勝
11    → 先手は 10 や 01 にせざるを得ず、後手必勝
111   → 先手は 110 などにすると先手必勝
1111  → 先手は 0110 などにすると先手必勝
11111 → ?

5つ目からちょっと迷うが、“11” の形を相手に渡すのが強そうと考察を進めていくと、「“11” のみからなる形」が必敗形（相手から渡されると必ず負ける形）であることが分かる。

0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
    v   v             v        先手（渡された側）はどこを0にしても
0 1 0 0 0 1 0 1 1 0 1 0 0 1 1
  v       v         v          後手はそれと対になる1を0にすると必敗形を保てる
0 0 0 0 0 0 0 1 1 0 0 0 0 1 1

で、5つ以上の“1”の連続は、必ず1手で必敗形にできるので、

最初から必敗形の場合のみ後手必勝（初期状態が全て “0” の場合を含む）
それ以外は先手必勝

Python3

from itertools import groupby


def solve(n, aaa):
    all2 = True
    for a, itr in groupby(aaa):
        if a == 0:
            continue
        l = len(list(itr))
        if l != 2:
            all2 = False
            break
    ans = not all2
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    if ans:
        print('Alice')
    else:
        print('Bob')

C - K Spanning Tree

問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフ $G$ が与えられます。
辺 $i$ は頂点 $a_i$ と頂点 $b_i$ を結ぶ重み $c_i$ の辺です。ここで、各辺の重みは $0$ または $1$ です。
非負整数 $K$ が与えられます。
$G$ の全域木であって、その全域木を構成する辺の重みの和がちょうど $K$ であるものが存在するかを判定し、存在するなら一つ求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 10^5$
$2 \le N \le 2\times 10^5$
$N-1 \le M \le \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)$
$0 \le K \le N-1$
$1 \le a_i,b_i \le N$
$c_i=0$ または $c_i=1$
グラフ $G$ は単純連結である。
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
全てのテストケースにおける $M$ の総和は $2\times 10^5$ 以下
入力される値は全て整数

解法

最小全域木のコスト $x$ と最大全域木のコスト $y$ をまず求め、$x \le K \le y$ でなければ無理。以下、満たすとする。

適当に繋いでいくと、「もう $1$ の辺を $K$ 本使ったが、まだ連結成分が複数残っていて、それを繋ぐにはさらに $1$ の辺を使わないといけない」みたいなことが発生しうる。

なので、まず「絶対必要な $1$」を洗い出し、そこは優先的に採用するように $K$ 本を選ぶとよい。

$0$ の辺→$1$ の辺の順に採用して全域木を作る。
- この時使用した $1$ の辺を「絶対必要な $1$ の辺」とする。$x \le K$ より、この辺の数は、$K$ より小さい。
リセットして、以下の順に全域木を作る。
- 絶対必要な $1$ の辺
- 他の $1$ の辺。合計 $K$ まで採用したら止める。$K \le y$ より、必ず $K$ 本は採用できる。
- $0$ の辺

絶対必要な $1$ の辺さえ繋いでおけば、後は全体が連結になることが保証される。

Python3

from atcoder.dsu import DSU


def solve(n, m, k, edges):
    edges = [(a - 1, b - 1, c) for a, b, c in edges]
    edge0s = []
    edge1s = []
    for i in range(m):
        a, b, c = edges[i]
        if c == 0:
            edge0s.append((a, b, i))
        else:
            edge1s.append((a, b, i))

    uft = DSU(n)
    use1 = set()
    for a, b, ei in edge0s:
        uft.merge(a, b)
    for a, b, ei in edge1s:
        if uft.same(a, b):
            continue
        use1.add(ei)
        uft.merge(a, b)

    if len(use1) > k:
        return [-1]

    uft = DSU(n)
    use0 = set()
    for a, b, ei in edge1s:
        uft.merge(a, b)
    for a, b, ei in edge0s:
        if uft.same(a, b):
            continue
        use0.add(ei)
        uft.merge(a, b)

    if len(use0) > n - 1 - k:
        return [-1]

    uft = DSU(n)
    score = 0
    for ei in use0:
        a, b, c = edges[ei]
        uft.merge(a, b)
    for ei in use1:
        a, b, c = edges[ei]
        uft.merge(a, b)
        score += 1

    ans = list(use0) + list(use1)

    for a, b, ei in edge1s:
        if score == k:
            break
        if not uft.same(a, b):
            uft.merge(a, b)
            score += 1
            ans.append(ei)
    assert score == k

    for a, b, ei in edge0s:
        if not uft.same(a, b):
            uft.merge(a, b)
            ans.append(ei)

    ans = [a + 1 for a in ans]
    ans.sort()
    return ans


t = int(input())
for _ in range(t):
    n, m, k = list(map(int, input().split()))
    edges = [list(map(int, input().split())) for _ in range(m)]
    ans = solve(n, m, k, edges)
    print(*ans)

D - Gap Swap (easy)

問題文

$(1,2,\ldots,N)$ の順列 $P$ があります。$P$ に対して以下の操作を行えます。
- 以下の条件を全て満たす整数 $i,j$ を選ぶ。
  - $1 \le i \lt j \le N$
  - $i \lt k \lt j$ を満たす全ての整数 $k$ について $P_k=k$ である
- その後、$P_i,P_j$ を入れ替える。この操作にはコストが $\boldsymbol{j-i}$ かかる。
なお、$i+1=j$ の場合、$i\lt k\lt j$ を満たす整数 $k$ は存在しないため、操作は常に行えます。したがって、$P$ を昇順にするような操作手順は必ず存在します。
$P$ を昇順にするために必要なコストの和の最小値を求めてください。

制約

$2 \le N \le 5\times 10^5$
$1 \le P_i \le N$
$P$ は $(1,2,\ldots,N)$ の順列
入力される値は全て整数

解法

各要素について、絶対このコストはかかるという下限を考え、それが達成可能であることを示す。

$i$ を $P_i$ に持って行くには、絶対 $|i-P_i|$ かかる。それを持っていく方向とともに記録してみる。

i   1   2   3   4   5   6   7
P   3   1   4   7   5   2   6
   →2 ←1 →1 →3  0  ←4 ←1

この時、→の総和と←の総和は等しくなる。

また、（0は無視して）→と←が隣り合うところが必ず存在する。
（∵左端は必ず→で、右端は必ず←となるので）

そのような箇所は必ず操作可能で、コスト $c=j-i$ として、操作後の値はそれぞれ $c$ だけ減少する。

これを繰り返せば、→の総和（＝←の総和）の下限コストが達成できる。

Python3

def solve(n, ppp):
    ans = 0
    for i in range(n):
        p = ppp[i] - 1
        if p > i:
            ans += p - i
    return ans


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

E - Gap Swap (hard)

問題文

$(1,2,\ldots,N)$ の順列 $P$ があります。$P$ に対して以下の操作を行えます。
- 以下の条件を全て満たす整数 $i,j$ を選ぶ。
  - $1 \le i \lt j \le N$
  - $i \lt k \lt j$ を満たす全ての整数 $k$ について $P_k=k$ である
- その後、$P_i,P_j$ を入れ替える。この操作にはコストが $\boldsymbol{1}$ かかる。
なお、$i+1=j$ の場合、$i\lt k\lt j$ を満たす整数 $k$ は存在しないため、操作は常に行えます。したがって、$P$ を昇順にするような操作手順は必ず存在します。
$P$ を昇順にするために必要なコストの和の最小値を求めてください。

制約

$2 \le N \le 5\times 10^5$
$1 \le P_i \le N$
$P$ は $(1,2,\ldots,N)$ の順列
入力される値は全て整数

解法

WA考察

全くの方針違いなので価値はないが、一応、本番中に考えたことをメモ。

WA考察

「$i～j$ の間が全て $P_k=k$」という制約が無ければ、順列をswapによってソートする典型問題となり、手数は（$N-$ サイクルの個数）である。

制約があると、互いに互いをロックし合って、一旦マージしないことには操作できないサイクルの組が発生する。

,---,    サイクルは2つだが、ロックし合う関係にあるので、
3 4 1 2  4と1などに操作し、一回、マージする必要がある。
  `---'  マージ1回 + サイクルが1個なので(4-1) = 4 回の操作が必要
  ,-,
4 3 2 1  ロックしあわないので、先に2と3に操作して揃えれば、4と1は操作可能
`-----'  → 4-2 = 2 を達成可能

包含的な関係にあるサイクルはマージしなくて良い。マージの必要回数 +（N-マージ後のサイクル数）が答え？

…と思ったが、実際は1つのサイクル内でもロックし合う場合がある。
制約がない場合の「$N-$サイクル数」は、「1回操作すれば必ず1要素は正しい位置に収まる」ことが前提であったが、それが成り立たないので、必要な操作はもっと増える。

P  4 5 1 2 3    どの1手でも、要素を正しい位置に収めることはできない。
                サイクル理論だと 5-1=4 だが、実際は6手必要。

正解方針

D問題の考察をもう少し進める。移動させなければならない方向と距離を再掲する。

i   1   2   3   4   5   6   7
P   3   1   4   7   5   2   6
   →2 ←1 →1 →3  0  ←4 ←1

もし、正しい操作手順において「いちど $i=P_i$ となった要素に対しては操作しない」という性質があれば、操作は「$i=P_i$ となった要素に対するコスト0の削除操作」と「コスト1の隣接swap操作」の2つで表せる。ひとまず、その性質を正しいとして考察を進める。

上例では、初期状態では $i=5$ が削除できる。

$i=5$ を削除し、後続の要素は位置と値を詰める。つまり「$5$ より右の要素は位置を詰め」「$5$ より大きな要素は値を1ずつ減らす」。その上で改めて移動距離を求めると、「目標位置に行くためには $i=5$ を跨ぐ」ような要素の「→○」「←○」の値が $1$ 減っていることがわかる。

i   1   2   3   4   5   6   7
P   3   1   4   7   5   2   6
   →2 ←1 →1 →3  0  ←4 ←1
               ~~~     ~~~
                  ↓
i   1   2   3   4   5   6
P   3   1   4   6   2   5
   →2 ←1 →1 →2 ←3 ←1
               ~~~ ~~~

残った中で「→←」の順に隣接した要素に対しては隣接swapを行える。コストが1かかり、互いに「→○」「←○」の値が $1$ 減る。

i   1   2   3   4   5   6
P   3   1   4   2   6   5
   →2 ←1 →1 ←2 →1 ←1
               ~~~ ~~~

（削除操作を可能な限り行った後）隣接していない要素間に操作するのは問題制約上認められない。
また、→←でない隣接は、操作はできるが目標の並びに近づかない。

$i=P_i$ になり次第「削除操作」を優先的に行った上で、「→←の隣接swap操作」を繰り返せば、効率的にソートできそうである。

この時、ある要素の操作回数は「初期状態の→○の値 $|i-P_i|$」から、「途中で他の要素の削除操作により節約できた分」を引いたものとなる。この「削除によって節約できるコスト」を考えればよい。（操作順により変わりうる場合はその最大化）

$\mathrm{sum}(P)=\displaystyle \sum_{i=1}^{|P|}|i-P_i|$ とする。

どうも「転倒数」が関わってきていそうなので、削除操作と隣接swap操作の転倒数および $\mathrm{sum}(P)$ の変化を見てみる。

削除操作:
- 削除対象を $i$ とする。$i$ と転倒の関係にあった要素分だけ転倒数も $\mathrm{sum}(P)$ も減る
  - $i$ より左にあって $i$ より小さい値: 変化せず
  - $i$ より左にあって $i$ より大きい値: 転倒数が1つにつき1減る。その要素の→○の値が1減る
  - $i$ より右にあって $i$ より小さい値: 転倒数が1つにつき1減る。その要素の←○の値が1減る
  - $i$ より右にあって $i$ より大きい値: 変化せず
隣接swap操作:
- 転倒数は1減る。
- $\mathrm{sum}(P)$ は操作した互いの→○、←○の値が1ずつ減ることで、$2$ 減る

削除操作では転倒数と $\mathrm{sum}(P)$ の変化が等しく、隣接swap操作では $1$ だけ転倒数の減少が遅い。

このズレがちょうど「操作のコスト」に対応し、 $\mathrm{sum}(P) - \mathrm{inv}(P)$ が上手くコストを表現している。

目標のソートされた状態になった瞬間、$\mathrm{sum}(P), \mathrm{inv}(P)$ は同時に $0$ になる。（それまでは $0$ にはならない）。
操作によって両者を減らしていったとき、「隣接swap操作」の回数はちょうど $\mathrm{sum}(P) - \mathrm{inv}(P)$ になっていないといけない、ということがわかる。

「削除操作」「→←の隣接swap操作」のいずれかは常に行えるので、途中で両者を増やす、または inv のみ減らす、という操作をすることはいたずらに操作回数を増やすだけであり、意味が無い。最初に仮定した「$i=P_i$ となった要素には操作をしない」についても、操作してもいたずらに $\mathrm{sum}(P)$ を増やすことにしかならないことから、しなくてよいことがわかる。

たとえば、ある2要素 $P_i=8$ と $P_j=4$ が転倒の関係にあった場合、初期位置や操作順によって $4$ の方に削除操作を行う場合もあれば、$8$ の方に削除操作を行う場合もあれば、$8,4$ が近づいていってswap操作で直接、転倒を解消する場合もある。しかし、そのいずれを取っても全体としての $\mathrm{sum}(P) - \mathrm{inv}(P)$ は一定である、という点が直感的に見えづらく、難しい点である。

Python3

from atcoder.fenwicktree import FenwickTree


def inversion_number(aaa):
    """ 転倒数
    制約: 各 i につき、0 <= aaa[i] <= メモリに乗る程度の値
    """
    assert len(aaa) > 0
    fwt = FenwickTree(max(aaa) + 1)
    inv = 0
    for i, a in enumerate(aaa):
        inv += i - fwt.sum(0, a + 1)
        fwt.add(a, 1)
    return inv


def solve(n, ppp):
    diff = sum(abs(i - p) for i, p in enumerate(ppp, start=1))
    inv = inversion_number(ppp)
    ans = diff - inv
    return ans


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

目次

AtCoder Regular Contest 225 A,B,C,D問題メモ

A - Four Coloring

問題文

制約

解法

発展

色の種類数 $K=5$ の時

$K \ge 6$ の時

B - Independent Nim

問題文

制約

解法

C - K Spanning Tree

問題文

制約

解法

D - Gap Swap (easy)

問題文

制約

解法

E - Gap Swap (hard)

問題文

制約

解法

WA考察

正解方針