AtCoder Regular Contest 214 A～E問題メモ

AtCoder Regular Contest 214

A - Same Sum Grid Path

• $N \times N$ のマス目があります。各マス目には数字（0～9）または ? が書かれています。
• ? をそれぞれ 0～9 のいずれかの数字に置き換えることで以下の条件を満たせるか判定し、可能ならばそのような置き換え方を $1$ つ出力して下さい。
  • 右または下に隣接するマスへの移動のみを繰り返してマス $(1,1)$ からマス $(N,N)$ まで到達する経路について、経路上に含まれるマス（始点・終点を含む）に書かれた整数の総和を経路のスコアとする。
  • このとき、$\binom{2N-2}{N-1}$ 通りある経路について、スコアは全て等しい。

• $2 \le N \le 100$
• $S_{i,j}$ は数字（0～9）または ?

ある2×2のマスについて、

...┼─┼─┼...
   │①→②│
...┼↓┼↓┼...
   │③→④│
...┼─┼─┼...

「…→①→②→④→…」という経路と「…→①→③→④→…」という経路のスコアが等しくなければならない。
よって、②と③に書き込む数字は同じでなければならない。

これが全ての2×2マスについて成り立つので、結局、「／」方向に並ぶ数字は全て同じでなければならない。

逆に、「／」方向に並ぶ数字が全て同じであれば、 $i$ ステップ目（$i=0,1,...,2N-2$）に踏むマスに書いてある数字が全て同じなので、スコアが等しいことが保証される。

Python3

def solve(n, field):
    appeared = {}
    for i in range(n):
        for j in range(n):
            if field[i][j] == '?':
                continue
            a = int(field[i][j])
            if i + j in appeared and appeared[i + j] != a:
                return [[-1]]
            appeared[i + j] = a
    ans = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i + j in appeared:
                ans[i][j] = appeared[i + j]
    return ans


n = int(input())
field = [input() for _ in range(n)]
ans = solve(n, field)
for row in ans:
    print(''.join(map(str, row)))

B - Missing Number in Graph

• $N$ 頂点の $M$ 辺の連結な単純無向グラフがあります。
• また、$0$ から $N$ までの整数が書かれたカードがそれぞれ $1$ 枚ずつ、合計 $N+1$ 枚あります。
• すぬけ君は以下の操作を順番に行いました。
  • 各頂点に $1$ 枚ずつカードを置き、残った $1$ 枚のカードを食べる。
  • 各 $i\ (1 \le i \le M)$ について、頂点 $A_i,B_i$ に置かれた $2$ 枚のカードに書かれた整数のビット単位 $\mathrm{XOR}$ を辺 $i$ に書く。この整数を $X_i$ とする。
  • 頂点に置かれたカードを全て捨てる。

• グラフの情報（$N,M,A_1,\dots ,A_M,B_1,\dots ,B_M,X_1,\dots ,X_M$）が与えられるので、すぬけ君が食べたカードに書かれた整数を特定して下さい。ただし、一意に定まらない場合は -1 を出力して下さい。
• なお、与えられる $X$ が上記の操作で得られるものであることは保証されます。

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

• $1 \le T \le 10^4$
• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i,B_i \le N$
• 与えられるグラフは連結な単純無向グラフである
• $X_1,\dots ,X_M$ は問題文中の操作で得られるものである
• 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• 全てのテストケースにおける $M$ の総和は $2 \times 10^5$ 以下
• 入力される値は全て整数

とりあえず、どれか1つの頂点に置いたカードの数字を仮定すると、全ての頂点が連鎖的に決まる。

○----4---○--7--○
 `-1-○-5-'        ↖たとえばここを"0"に仮定すると
  ↓
③----4---⑦--7--⓪  他も全て決まる。
 `-1-②-5-'

問題の制約からXORについて矛盾は発生しないが、最大値が $N$ を超えてしまう可能性がある。 （上例では $N=4$ なのに⑦があるので、正しい値ではない）

ここで求まった仮値を $s=(s_1,s_2,...,s_N)$ とする。 $s$ は、真の答え $t=(t_1,t_2,...,t_N)$ から全ての頂点に何らかの固定値 $k$ をXORしたものである。

• $s_i \oplus k = t_i$

$N$ が偶数なら、「$s$ の要素の総XOR」をとれば $k$ の影響は相殺され、 「$t$ の要素の総XOR」、つまり「$0～N$ から食べたカードを除いたものの総XOR」と等しくなる。

よって、具体的に $k$ を特定しなくても（$0～N$ の総XOR）$\oplus$（$s$ の総XOR）が答えとなる。

$N$ が奇数の場合、$s$ の総XORに $k$ の影響が残ってしまうので困るが、、、

よく考えると、$t$ の全ての要素に $1$ をXORしたものも、最大値 $N$ を超えずに必ず条件を満たす。
よってこの場合は一意に定まらないので、-1 を出力すればよい。

Python3

def solve(n, m, edges):
    if n % 2 == 1:
        return -1

    links = [[] for _ in range(n)]
    for a, b, x in edges:
        a -= 1
        b -= 1
        links[a].append((b, x))
        links[b].append((a, x))
    tmp = [-1] * n
    tmp[0] = 0
    q = [0]
    while q:
        u = q.pop()
        for v, x in links[u]:
            if tmp[v] == -1:
                tmp[v] = tmp[u] ^ x
                q.append(v)
    # print(f'{tmp=}')
    index_xor = n
    tmp_xor = 0
    for i in range(n):
        index_xor ^= i
        tmp_xor ^= tmp[i]
    ans = index_xor ^ tmp_xor
    return ans


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

C - Divide into 4 Teams

• $1, \dots ,N$ の番号がついた $N$ 人の人がいます。人 $i$ の強さは $P_i$ です。
• 各人を $A,B,C,D$ のいずれかのチームに割り当てることで、$4$ つのチームにチーム分けをします。
• チーム分けの方法は $4^N$ 通りありますが、このうち以下の条件を全て満たすチーム分けの個数を $998244353$ で割った余りを求めて下さい。
  • $A,B,C,D$ のどのチームにも $1$ 人以上所属する。
  • チーム $A$ に所属する人の強さの和とチーム $B$ に所属する人の強さの和が等しい。
  • チーム $C$ に所属する人の強さの和とチーム $D$ に所属する人の強さの和が等しい。

• $4 \le N \le 500$
• $1 \le P_i$
• $\sum_{1 \le i \le N} P_i \le 10^5$
• 入力される値は全て整数

問題は、次のように言い換えられる。

• 2次元座標 $(0,0)$ にいる。
• これから $N$ 回移動する。$i$ 回目は、移動前の座標を $(x,y)$ として以下のいずれかに移動する。
  • $(x-P_i,y)$
  • $(x+P_i,y)$
  • $(x,y-P_i)$
  • $(x,y+P_i)$
• 上下左右、いずれの方向にも1回以上移動しつつ、最終的に $(0,0)$ に戻っているような経路は何通り？

左右移動が $A-B$、上下移動が $C-D$ に対応する。これがいずれも $0$ になればよい。

もし4グループでなく2グループなら、1次元のみの問題となり以下のDPで $O(N \sum P_i)$ で解けるのだが、

• $\mathrm{DP}[i,x]:=i$ 回目の移動後に座標 $x$ にいるパターン数

4グループあると $x,y$ をそれぞれキーに持っていたら $O(N(\sum P_i)^2)$ かかるので困る。

これ、知らないとなかなか発想しづらいが過去に類題が出題されていて、45度回転すると見通しが良くなる。 つまり、移動を以下のようにしても答えは変わらない。

• $(x-P_i,y-P_i)$
• $(x-P_i,y+P_i)$
• $(x+P_i,y-P_i)$
• $(x+P_i,y+P_i)$

これの何が嬉しいかというと、$x$ と $y$ を独立に考えられるようになる。

よって、1次元でDPした結果を $X=\mathrm{DP}[N,0]$ として、$X^2$ が答えとなる、、、

が、この中には「上下、または左右に1回も移動しないパターン」も含まれている。
これは、$2X$ だけ含まれているので、答えから除けばよい。

Python3

def solve(n, ppp):
    MOD = 998244353
    s = sum(ppp)
    limit = s // 2 + 1
    m = limit * 2 + 1
    dp = [0] * m
    dp[0] = 1
    for p in ppp:
        ndp = [0] * m
        for i in range(-limit, limit + 1):
            if dp[i] == 0:
                continue
            ndp[i - p] += dp[i]
            ndp[i - p] %= MOD
            ndp[i + p] += dp[i]
            ndp[i + p] %= MOD
        dp = ndp
    ans = dp[0] * dp[0] - dp[0] * 2
    ans %= MOD
    return ans


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

D - Distinct Sum Grid Path

• $N \times N$ のマス目があります。
• 以下の条件を満たすように各マスに非負整数を $1$ つずつ書き込む方法を $1$ つ出力して下さい。
  • 右または下に隣接するマスへの移動のみを繰り返してマス $(1,1)$ からマス $(N,N)$ まで到達する経路について、経路上に含まれるマス（始点・終点を含む）に書かれた整数の総和を経路のスコアとする。
  • このとき、$\binom{2N-2}{N-1}$ 通りある経路について、スコアは互いに異なり、全て $6 \times 10^6$ 以下である。

• $2 \le N \le 13$

やってみたらできた、感が強い。

とりあえず、スコア $0$ の経路を右上に作る。
[A] のマスを通る経路に着目する。ここを通るルートは最も小さいスコアでも $0$ であってはならない。

N=5
0  0  0  0  0
?  ?  ? [A] 0
?  ?  ?  ?  0
?  ?  ?  ?  0
?  ?  ?  ?  0

ここを $1$ にするとスコア $1$ の経路となる。 その下のマスも同様に $1$ を設定すれば、 現時点で数字が決まっているマスのみを通る経路のスコアは全て異なり、$0～4$ の値を取る。

0  0  0  0  0   →→→→↓↓↓↓: 0
?  ?  ?  1  0   →→→↓→↓↓↓: 1
?  ?  ?  1  0   →→→↓↓→↓↓: 2
?  ?  ?  1  0   →→→↓↓↓→↓: 3
?  ?  ?  1  0   →→→↓↓↓↓→: 4

次、[ ] の位置に着目する。 ここを通るルートで最も小さいスコアを $5$ 以上にしたい。 $4$ を設定すれば最小が $5$ となる。また、現時点で数字が決まっているマスのみを通る経路の中での最大が $8$ となる。

0  0  0  0  0   →→↓→→↓↓↓: 5
?  ? [4] 1  0   →→↓→↓→↓↓: 6
?  ?  ?  1  0   →→↓→↓↓→↓: 7
?  ?  ?  1  0   →→↓→↓↓↓→: 8
?  ?  ?  1  0

さらに次、[ ] の位置を通る最も小さいスコアを $9$ 以上にしたい。 ここも $4$ を設定すれば条件を満たし、最大が $11$ となる。

0  0  0  0  0   →→↓↓→→↓↓:  9
?  ?  4  1  0   →→↓↓→↓→↓: 10
?  ? [4] 1  0   →→↓↓→↓↓→: 11
?  ?  ?  1  0
?  ?  ?  1  0

このようにして、右上から順に「そのルートを通る最も小さいスコア」が「現在決まっているマスのみを通る最も高いスコア $+1$」となるように設定していけば、各ルートのスコアを隙間無く埋めていける。

 0  0  0  0  0   →→↓↓↓→→↓: 12
 ?  ?  4  1  0   →→↓↓↓→↓→: 13
 ?  ?  4  1  0   →→↓↓↓↓→→: 14
 ?  ? [3] 1  0
 ?  ? [2] 1  0

 0  0  0  0  0   →↓→→→↓↓↓: 15
 ?[10] 4  1  0   →↓→→↓→↓↓: 16
 ?  ?  4  1  0     ：
 ?  ?  3  1  0   →↓→↓↓↓→→: 24
 ?  ?  2  1  0

 0  0  0  0  0   →↓↓→→→↓↓: 25
 ? 10  4  1  0   →↓↓→→↓→↓: 26
 ?[10] 4  1  0     ：
 ?  ?  3  1  0   →↓↓→↓↓→→: 30
 ?  ?  2  1  0

 0  0  0  0  0
20 10  4  1  0
20 10  4  1  0
14  7  3  1  0
 8  4  2  1  0

このアルゴリズムをプログラムに落とし込む必要がある。 以下の [?] の位置の値を決めるとき、

 0  0  0  0  0    (A) [?]を通る最も小さいスコア
 ? 10  4  1  0    →↓↓→→→↓↓
 ? [?] 4  1  0
 ?  ?  3  1  0    (B) 現在決まっているマスのみを通る最も高いスコア
 ?  ?  2  1  0    →↓→↓↓↓→→

いずれも [?] の1つ上の $10$ のマスまでは同じ経路を辿る。差分さえ分かればよいので、

• (A) [?] のすぐ右から、最右列まで右に進み、その後、下降する経路上の数字の合計
• (B) [?] の右上のマス（上側の $4$）から、最下段まで下降し、その後、右に進む経路上の数字の合計

として、$(B)-(A)+1$ とすると、[?] に置くべき値が求まる。

Python3

def solve(n):
    def get_min(si, sj):
        tmp = 0
        for j in range(sj, n):
            tmp += ans[si][j]
        return tmp

    def get_max(si, sj):
        tmp = 0
        for i in range(si, n):
            tmp += ans[i][sj]
        for j in range(sj + 1, n):
            tmp += ans[-1][j]
        return tmp

    ans = [[0] * n for _ in range(n)]
    for i in range(1, n):
        ans[i][n - 2] = 1
    for j in range(n - 3, -1, -1):
        for i in range(1, n):
            ans[i][j] = get_max(i - 1, j + 1) - get_min(i, j + 1) + 1

    return ans


n = int(input())
ans = solve(n)
for row in ans:
    print(*row)

E - Swap K times

• 長さ $N$ の整数列 $A = (A_1, \dots ,A_N), B = (B_1, \dots ,B_N)$ と正整数 $K$ が与えられます。
• コストを $1$ 払うたびに、隣接 swap をちょうど $K$ 回行うことが出来ます。隣接 swap とは、以下の操作を指します。
  • $1$ 以上 $N-1$ 以下の整数 $i$ を $1$ つ選び、$A_i$ と $A_{i+1}$ を入れ替える。
• $A$ を $B$ に一致させられるかを判定して下さい。可能な場合は、一致させるために必要なコストの最小値を求めて下さい。

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

• $1 \le T \le 10^5$
• $2 \le N \le 3 \times 10^5$
• $1 \le K \le 10^9$
• $1 \le A_i,B_i \le N$
• $\{A_1,\dots ,A_N\}$ と $\{B_1,\dots ,B_N\}$ は多重集合として一致する
• 全てのテストケースにおける $N$ の総和は $3 \times 10^5$ 以下
• 入力される値は全て整数

隣接swapによって一致させるための最小回数 $M$ は、以下で求められる。

• $A$ の要素→index への変換マップを作る。
  • $A=(2,3,1)$ の場合、$\{2→0,3→1,1→2\}$
• $B$ をそれに従って変換し、$C$ とする。
  • $B=(1,2,3)$ の場合、$C=(2,0,1)$
• $C$ の転倒数を求める。

よって、$t = \lceil \frac{M}{K} \rceil$ 回あれば足りる。。。 のだが、「ちょうど」$K$ 回操作しなければならないので、偶奇が重要になる。
余った分は2回ずつ、同じ位置にswapを繰り返せばよいが、順列に影響を与えずに1回だけ操作する方法はない。

• $tK$ と $M$ の偶奇が一致していればOK。$t$ が答えとなる。

そうでない場合、

• $K$ が奇数の場合、もう1回追加すれば偶奇が揃うので、$t+1$ が答え。
• $K$ が偶数の場合、一致させることは不可能となる。

こっちが本質。

まず最小の隣接swap回数は、先ほどの $C$ を作るところにおいて、以下のようにすると求められる。

• 同じ要素毎に、$A$ で $i$ 番目に出てくる値と、$B$ で $i$ 番目に出てくる値を対応させる

i  0 1 2 3 4
A  3 1 4 1 5    Aで1番目に出てくる1は、
     `-, `-,    Bで1番目に出てくる1の位置に対応させる。
B  5 4 1 3 1
C  4 2 1 0 3

これで $C$ の転倒数が最小となり、$\lceil \frac{M}{K} \rceil K$ と $M$ の偶奇が一致すればいいのだが、そうで無い場合、今回は次善の策がある。

i  0 1 2 3 4
A  3 1 4 1 5    同じ要素のどこか1箇所の対応を入れ替える
     `--/--,
B  5 4 1 3 1
C  4 2 3 0 1

こうすると、必ず転倒数の偶奇が変化する。
「最小転倒数 $M$ と偶奇が異なる中で、最小の転倒数」を見つければよい。

それを考える上で、以下の疑問が浮かぶが、

• 対応の入れ替えは1箇所だけでいいの？ 複数箇所を同時に入れ替えた方が最適になることはない？
• 1箇所入れ替えればいいとして、どれを入れ替えるのがいいの？

結論として、入れ替えは1箇所だけでよく、以下の値が最小となるペアを見つければよい。

• 入れ替える同じ値のペアが、$B$ に出現する位置をそれぞれ $i,j$ とする。
  • 上例では、$B$ で2つの $1$ が出現する位置は $i=2,j=4$
• $C$ において「$i～j$ の間にある、$C_i$ より大きく $C_j$ 未満の値の個数」を $y$ とする。
• $y$ が最小となるペアが最適であり、転倒数は $2y+1$ 増加する。

i  0 1 2 3 4
C  4 2 1 0 3      Cにおいてi=2～4の間に出現する
        ~~~     ←1より大きく3未満の値の個数（この例では y=0）。

略証

... 3 x x x 7 ...
    ↓
... 7 x x x 3 ...

3と7をswap → 転倒数に影響があるのは、ペア自身とそれに挟まれた項のみ

・3と7自体      : 1増える                         → ＋1
・    x < 3 の項: 3に対して減り、7に対して増える  → ±0
・3 < x < 7 の項: 3に対しても7に対しても増える    → ＋2
・7 < x     の項: 3に対して増え、7に対して減る    → ±0

... 3 x x x 7 x x x 10 ...  swapした時の y
    * ----- *               ①区間内にある 3<x<7 の個数
            * ------ *      ②区間内にある 7<x<10 の個数
    * -------------- *      ③区間内にある 3<x<10 の個数

$y$ は、$B,C$ の情報があれば「矩形の中の点の個数」の問題に落とし込める。平面走査っぽく以下のように見つけられる。

$C$ を $i=0,1,2,...$ の順に調べながら、FenwickTree などで、出現済みの値 $C_i$ に $1$ を立てていく。

ある $i$ に対し、

• $B$ において、$i$ 以降に $B_i$ と同じ値が出現するなら、
  • その位置を $j$ とする。
  • 現時点で $C$ に出現している、$C_i$ より大きく $C_j$ 未満の値の個数を取得する。
  • その値を $B_i$ に紐付けてメモっておく。
• $B$ において、$i$ 以前に $B_i$ と同じ値が出現していたなら、
  • その位置を $j$ とする。
  • 現時点で $C$ に出現している、$C_j$ より大きく $C_i$ 未満の値の個数を取得し、$s$ とする。
  • $s-$（$B_i$ に紐付けてメモっておいた値）が、転倒数の増分のファクター $y$ である。
  • （※説明のため順番が前後したが、処理としてはこちらを先に行い、その後、$i$ 以降にも $B_i$ と同じ値が出現するなら、メモを更新する）
• $C_i$ に $1$ を立てる。

これで最小の $y$ を見つけられる。

偶奇の異なる転倒数最小値 $M$ と $M+2y+1$ のそれぞれで最小コストを求め、小さい方が答えとなる。

Python3

from collections import defaultdict

from atcoder.fenwicktree import FenwickTree


def solve(n, k, aaa, bbb):
    pos = defaultdict(list)
    for i in range(n):
        a = aaa[i]
        pos[a].append(i)

    fwt = FenwickTree(n + 1)
    progress = defaultdict(int)
    memo = {}
    INF = 1 << 60
    best_same_swap = INF
    inversion = 0
    dbg_ccc = []
    for bi in range(n):
        b = bbb[bi]
        pb = progress[b]
        i = pos[b][pb]
        dbg_ccc.append(i)
        progress[b] += 1

        inversion += fwt.sum(i + 1, n)

        if pb >= 1:
            prev = pos[b][pb - 1]
            between_prev_curr = fwt.sum(prev + 1, i)
            same_swap = between_prev_curr - memo[b]
            best_same_swap = min(best_same_swap, same_swap)
        if pb < len(pos[b]) - 1:
            nxt = pos[b][pb + 1]
            between_curr_next = fwt.sum(i + 1, nxt)
            memo[b] = between_curr_next

        fwt.add(i, 1)

    def odd_inv_odd_k(inv, k):
        if inv <= k:
            return 1
        return even_inv_odd_k(inv - k, k) + 1

    def even_inv_odd_k(inv, k):
        return ((inv - 1) // (k * 2) + 1) * 2

    if k % 2 == 0:
        if inversion % 2 == 0:
            ans = (inversion - 1) // k + 1
            return ans
        if best_same_swap == INF:
            return -1
        inversion += 2 * best_same_swap + 1
        ans = (inversion - 1) // k + 1
    else:
        if inversion % 2 == 0:
            ans = even_inv_odd_k(inversion, k)
            if best_same_swap < INF:
                inv2 = inversion + 2 * best_same_swap + 1
                ans = min(ans, odd_inv_odd_k(inv2, k))
        else:
            ans = odd_inv_odd_k(inversion, k)
            if best_same_swap < INF:
                inv2 = inversion + 2 * best_same_swap + 1
                ans = min(ans, even_inv_odd_k(inv2, k))
    return ans


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    ans = solve(n, k, aaa, bbb)
    print(ans)