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

AtCoder Regular Contest 208 (Div. 2)

前半は、ひたすら愚直実験→観察→構築という解法が有効な問題だったように思う。

A - Bitwise OR Game

• 石の山が $N$ 個あり、 $i$ 番目 $(1\le i\le N)$ の山には $A_i$ 個の石が積まれています。
• Alice と Bob がこれらの山を使って以下のようなゲームを行います。
  • Alice から始めて両者は交互に手番をプレイする。
  • 各手番では、プレイヤーは空でない山を一つ選び、その山から $1$ 個以上好きな個数の石を取り除く。ただし、石を取り除く前後で「全ての山の石の個数をビット単位 $\mathrm{OR}$ 演算することで得られる値」が変わるような行動を取ることはできない。

• 先に手番をプレイできなくなったプレイヤーの負けです。
• 両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。

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

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

すぐ実験はしたのだが、法則性を見いだすまでに時間がかかってしまった。
思いつく人はすぐ思いつきそうな解法だけに、もう少し速く解きたかったね。

実験すると、大半のケースで先手必勝となることが分かる。
後手必勝となるケースを観察すると、bitごとにそれが立っている $A_i$ の個数を数え、 全てのbitについて「$0$ または奇数」となっているケースで後手必勝となっているっぽい。

 A
 9   1 0 0 1
 1         1
 5     1 0 1
------------
個数 1 1 0 3  ← 全て0か奇数なので後手必勝

$2^d$ のbitが立っている $A_i$ の個数を $C_d$ とする。上例では $(C_0,C_1,C_2,C_3)=(3,0,1,1)$ となる。

$C_d=0$ のbitは0から変えられないことが決まっているので、除いて（隙間を詰めて）考える。
これにより「各 $d$ につき初期状態は $C_d \ge 1$ であり、これを $0$ にする操作は許されない」というルールにできる。

全ての $C_d$ が奇数の状態を「必敗状態」とする。

必敗状態から先手がどこかの山の石を減らしたとき、それによって変化した最も上位の桁を $d$ とする。
この時、選ばれた $A_i$ の $2^d$ のbitは必ず $1→0$ と変化し、$C_d$ は $1$ 減る。 （したがって、操作前の時点で $C_d \ge 3$ である。1個だとルール違反）。
$d$ より下の桁は「どこかの $C_k$ を $1→0$ にする」こと以外は好きなように $C_k$ の偶奇を操作できる。

後手は、操作後が再び必敗状態となるよう、全ての $C$ を奇数にして先手に渡し続けたい。

先手が選んだ $d$ と同じ箇所が立っている $A_i$ を選んで、変化する最大桁が $d$ となるように操作する。
これにより、$C_d$ は再び奇数となる。
$d$ より下の桁は先手と同様に好きに操作できる。
後手にとって変えなければならないbitは $C_k$ が偶数（2以上）の桁であり、減らしてもルールに違反しない。
よって、必ず必敗状態にして先手に返すことができる。

これを繰り返すと、いつかは $C=(1,1,1,...,1)$ となり操作できなくなり、先手が負ける。

初期状態が必敗状態で無い場合は、先手が初手で必敗状態を作って後手に渡すことができるので、先手必勝となる。

Python3

def solve(n, aaa):
    bit_counts = [0] * 32
    for a in aaa:
        i = 0
        while a:
            if a & 1:
                bit_counts[i] += 1
            a >>= 1
            i += 1

    if all(c % 2 == 1 or c == 0 for c in bit_counts):
        return 'Bob'
    else:
        return 'Alice'


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

B - Sum of Mod

• 正整数 $N,K$ が与えられます。
• 以下の条件を全て満たす長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ のうち、 $A_N$ の値が最小となるものを一つ求めてください。
  • $A$ は広義単調増加である。すなわち、 $1\le i\le N-1$ に対し $A_i \le A_{i+1}$ が成り立つ
  • $\displaystyle \sum_{i=1}^{N-1} (A_{i+1} \bmod A_i)=K$

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

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

$A$ を逆に構築し、最後に反転させることを考える。$A_1$ を最小化する。

$A_1$ を決めると、以降は「$A_{i}$ から、$A_{i+1} \gt (A_{i} - A_{i+1})$ となるように $A_{i+1}$ を残し、$A_{i} - A_{i+1}$ を取り出す」というように捉えることができる。この取り出した値が、$A_{i} \bmod A_{i+1}$ に相当する。

（※これは $A_{i}/A_{i+1}$ の商が全て $1$ であることを前提としているが、 商が2以上の場合、途中で $A_{i+1}$ 分の値が“消失”してしまうことに相当し、 初項を大きくしないといけなくなるので、最適にならない）

K=36

 i   1     2     3     4    5    6    7
 A  38 → 20 → 11 →  6 → 4 → 3 → 2      が引かれた数字の和が初項 A1 と一致
       ↘    ↘    ↘    ↘   ↘   ↘ ~    ~~
          18     9     5    2    1    1    ←取り出された数: この和をKとしたい
          ~~     ~     ~    ~    ~    ~ 

この時「$A$ の末項（上例では $A_7=2$）」と「$A_1$ から取り出された数」の総和が $A_1$ と一致する。

一旦、$N$ の制約は気にせず繰り返すと、どんな値からでも最終的に $A_i=2$ に行き着く。 $A_i=2$ からはもう正の値は取り出せない。 よって、$N$ が十分な長さを持っているとき、$A_1=K+2$ の解が存在する。

実際に $A_1=K+2$ から始めて $A_i=2$ になるまで構築してみて、長さが $N$ 以下ならこの方法で構築できる。
長さが余る場合は $2$ または $1$ を連続させればよい。

$N$ が短い場合、最速で $A_i$ を減らしていっても $A_i=2$ に到達する前に終わりが来てしまう。
うまく取り出す値を決めて $A_1=K+A_N$ とすることが可能な $A_N$ を探したい。

$A_N$ を決め、遡って $A_{N-1},A_{N-2},...$ の取り得る最大値を考える。
$A_{i-1}=2A_{i}-1$ としていくのが最適で、

A_N=4 の場合

A  ...  49 → 25 → 13 → 7 → 4
           ↘    ↘    ↘   ↘
   ...        24    12    6    3

この場合、取り出される値は $(A_N-1) \times (1+2+4+8+...) = (A_N-1)(2^{N-1}-1)$ となっている。

ちょうどの値で無くとも、初手で $A_1$ から取り出す値は $1～(A_N-1)2^{N-2}$ の範囲で好きに調整できる。

よって、$(A_N-1)(2^{N-1}-1) \ge K$ となる最小の $A_N$ を求め、逆順に $A_2$ までを構築し、 最後、取り出した値の和が $K$ に満たない分を $d$ として、$A_1=A_2+d$ とすればよい。

Python3

def solve(n, k):
    if n == 2:
        return [k + 1, 2 * k + 1]

    naive_ans = [k + 2]
    while naive_ans[-1] > 2:
        last = naive_ans[-1]
        naive_ans.append(last - (last - 1) // 2)
    if len(naive_ans) <= n:
        ans = [1] * (n - len(naive_ans))
        ans.extend(reversed(naive_ans))
        return ans

    total = (1 << (n - 1)) - 1
    x = (k - 1) // total + 1
    ans = [x + 1]
    tmp = 0
    for _ in range(n - 2):
        tmp += ans[-1] - 1
        ans.append(ans[-1] * 2 - 1)
    ans.append(ans[-1] + k - tmp)
    return ans


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

C - Mod of XOR

• $2^{30}$ 未満の正整数 $C,X$ が与えられます。
• 以下の条件を全て満たす正整数 $n$ が存在するか判定し、存在する場合は一つ求めてください。
  • $1\le n \lt 2^{60}$
  • $(n \oplus C) \bmod n=X$
• ただし、 $n \oplus C$ は $n$ と $C$ のビット単位 $\mathrm{XOR}$ を表します。

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

• $1\le T\le 2\times 10^5$
• $1\le C,X \lt 2^{30}$
• 入力される値は全て整数

とりあえず愚直解を書いてみて、観察する。

まず、簡単に答えが分かるケースが2つある。

• $C \oplus X \gt X$ の時、$n=C \oplus X$ が答えとなる。
  • $n \oplus C = X$ かつ $X \bmod n$ が $X$ のまま変化しないため
• $C=X$ の時、一例として $n=2^{30}$ が答えとなる。
  • $(n \oplus C) \bmod n=(n \oplus C) - n = C = X$ が成り立つ。
  • $C,X$ より大きく、$C$ とbitが被っていなければ何でもいい。

これ以外のケースでは、以下のように考えられる。

とりあえず、$n \ge 2^{30}$ の範囲で、$C,X$ より確実に大きいものに限定して考えてみる。
$(n \oplus C) \bmod n$ は $(n \oplus C)$ または $(n \oplus C) - n$ が成立するが、$(n \oplus C)$ は $X$ と等しくなり得ないため、$(n \oplus C)-n$ に限定する。

$(n \oplus C)-n=X$ より、$(n \oplus C) = X + n$ となればよい。

ここで、$(a \oplus b) = (a+b) - (a \& b)<<1$ と表せる。

よって、$C+n - (C \& n)<<1 = X+n$ より、$C-X=(C \& n)<<1$ となる必要がある。

つまり、以下が必要となる。

• $C \gt X$ かつ偶奇が一致
• $d=(C-X)>>1$ とすると、$d=(C \& n)$ より、$d$ のbitは全て $C$ で立っている

この条件を満たせば、$n = 2^{30} + d$ とすることで目標を達成できる。

条件を満たさない場合は不可能とすると通ったが、$n \lt 2^{30}$ の解が本当に無いのか？という証明はできてない。

Python3

def solve(c, x):
    bigbit = 1 << 30
    easy_n = c ^ x
    if easy_n > x:
        return easy_n
    if c == x:
        return bigbit

    if c % 2 != x % 2:
        return -1
    if c < x:
        return -1

    d = c - x
    d >>= 1
    if c & d != d:
        return -1
    ans = bigbit | d
    return ans

t = int(input())
for _ in range(t):
    c, x = map(int, input().split())
    ans = solve(c, x)
    print(ans)

D - Symmetric Matrix

• 各要素が $1$ 以上 $N$ 以下であるような長さ $N$ の整数列 $Y=(Y_1,Y_2,\ldots,Y_N)$ が与えられます。
• 以下の条件を全て満たす $N$ 行 $N$ 列の整数行列 $A=(A_{i,j})$ $(1\le i , j \le N)$ が存在するか判定し、存在する場合は一つ求めてください。
  • $1\le A_{i,j} \le N$ $(1\le i \le N, 1\le j\le N)$
  • $A_{i,j}=A_{j,i}$ $(1\le i\le N, 1\le j\le N)$
  • $A_{i,j_1}\neq A_{i,j_2}$ $(1\le i\le N, 1\le j_1 \lt j_2 \le N)$
  • $A_{i,Y_i}=1$ $(1\le i\le N)$

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

• $1\le T\le 5000$
• $1\le N \le 500$
• 全てのテストケースにおける $N^2$ の総和は $500^2$ 以下
• $1\le Y_i\le N$
• 入力される値は全て整数

右肩下がりの対角線に対して対称的なラテン方格のうち、“1”の位置のみ指定されているようなものを構築する問題。
以下、単に「対角線」と言ったときは右肩下がりのものを指すとする。

N=5
? ? ? 1 ?      3 2 4 1 5
? 1 ? ? ?      2 1 3 5 4
? ? ? ? 1  →  4 3 5 2 1
1 ? ? ? ?      1 5 2 4 3
? ? 1 ? ?      5 4 1 3 2

直接は難しいので、以下の手順を踏む。

• ①$1$ の位置は無視して、とりあえず「対角線に対し対称的」かつ「全ての行・列で1～N が1つずつ」という条件を満たす行列を構築する。
• ②条件を満たす状態を保ったまま、行や列を入れ替えて、$1$ の位置を合わせる。

①では、以下のような構築がひとまず可能である。これを仮に「ナナメ構築法」とでもしておく。

1 2 3 4 5
2 3 4 5 1    1つ上の行の並びを、1個左に回転させていく
3 4 5 1 2
4 5 1 2 3    i 行目 j 列目には (i+j)%N+1 を配置する、ともいえる。(0-indexed)
5 1 2 3 4

②では、条件を満たす行列から以下の操作をしても条件は満たされたままである。この操作を $swap(i,j)$ とする。

• ある $(i,j)$ に対し、$i$ 行目と $j$ 行目を入れ替え、$i$ 列目と $j$ 列目を入れ替える。

                        v v
3 2 4 1 5           3 2 1 4 5
2 1 3 5 4  i=3 j=4  2 1 5 3 4
4 3 5 2 1  ------>  1 5 4 2 3  <
1 5 2 4 3           4 3 2 5 1  <
5 4 1 3 2           5 4 3 1 2

①と②で方法が見つかって、これで解けた！……と思いきや、そう上手くはいかない。
②の swap では、必ずしも好きな位置に $1$ を持って来られるとは限らないのだ。
特に、「対角線上にある $1$」を「対角線以外の位置」に持ってくることはできない。逆もしかり。

愚直に再帰的探索で構築するコードを書くと、以下の性質がありそう、ということがわかる。

• $N$ 奇数の場合、対角線上にある $1$ の個数はちょうど $1$ 個でないと不可能
• $N$ 偶数の場合、対角線上にある $1$ の個数は偶数個でないと不可能

対角線上にない $1$ は、対称位置にある2個で1ペアとなるので、 「対角線上にある $1$ の個数」と $N$ の偶奇は一致する。

$N$ 偶数の場合はこれで説明できる。 奇数の場合も、$1～N$ 全てについてこれが成り立つので、各数字が奇数個ずつ対角線上に無いといけない →全ての数字が1個ずつある状態しかないことから示せる。

偶奇で分けて考える。

まず、基本的なとこを確認する。

• $Y_i$ に被りが無い
• $Y_i \neq i$ の場合、$Y_{Y_i}=i$ である。（対称性）
• $N$ が奇数の場合、$Y_i=i$ となる $i$ はちょうど $1$ つ

これらを満たす場合、構築可能である。

どんな構築方法を用いても、条件を満たす行列では、対角線上にある $1$ は1個となる。
たとえば前述のナナメ構築法では、唯一の対角線上の $1$ が左上 $(1,1)$ にあるものができあがる。

これを最初に swap 操作で目的の位置に持っていく。$swap(1, Y_i=i である唯一のi)$ すればよい。

その後、対角線外の $1$ を合わせる。
まだ $A_{i,Y_{i}}$ が $1$ でない $i$ に対し、その行の $1$ がある列を $j$ とし、$swap(i,j)$ していけばよい。

対角線外の操作では、ともに目標の位置に無かった $i$ 行目と $j$ 行目（$i$ 列目と $j$ 列目）が、同時に揃う。
逆に言うと、その行・列に他の $1$ はないので、既に揃った $1$ を崩す心配はない。

まず、「対角線が全て $1$ である行列」を構築する。
すると、対角線上の任意の $2 \times 2$ 行列は $\displaystyle \begin{pmatrix} 1 & a \\ a & 1 \end{pmatrix}$ という形になっているので、 ここだけ入れ替えても全体に影響しない。

1 2 3 4     [2 1]3 4
2 1 4 3  → [1 2]4 3
3 4 1 2      3 4 1 2
4 3 2 1      4 3 2 1

これによって、対角線上の $1$ と、対角線外の $1$ の個数を調整する。
その後は奇数と同様に、swap によって対角線上→対角線外の順に $1$ を合わせていけばよい。

問題は、「対角線が全て $1$ である行列」の構築の仕方である。
実験すれば簡単に法則性が見つかるかと思いきや、全然分からない。
（そもそもちょっと $N$ を大きくするとたくさん見つかってしまうので、どれが構成的に構築しやすいか見極められない）

諦めて（コンテスト終了後）Gemini に聞くと、ちゃんと正答を返してくれた。やりおる。

まず、「$2～N$ の値だけ」で、ナナメ構築法で $(N-1)\times (N-1)$ 行列を構築する。

2 3 4 5 6
3 4 5 6 2
4 5 6 2 3
5 6 2 3 4
6 2 3 4 5

その後、$N$ 行目・$N$ 列目を追加し、対角線を $1$ にしていく。
この時、既存の値は「一番右」と「一番下」に同時に押しやる。

[1]3 4 5 6[2]   1 3 4 5 6 2           1 3 4 5 6 2
 3 4 5 6 2      3[1]5 6 2[4]          3 1 5 6 2 4
 4 5 6 2 3   → 4 5 6 2 3   → ... → 4 5 1 2 3 6
 5 6 2 3 4      5 6 2 3 4             5 6 2 1 4 3
 6 2 3 4 5      6 2 3 4 5             6 2 3 4 1 5
[2]             2[4]                  2 4 6 3 5 1

こうすることで、対角線が全て $1$ の行列となる。

いや、まずは対角線上に $1$ を配置してから他の数字をどうしようか考えちゃうじゃん。最後に置き換えるとか発想出てこないよ。

Python3

def swap_rows(n, aaa, i, j):
    aaa[i], aaa[j] = aaa[j], aaa[i]


def swap_cols(n, aaa, i, j):
    for k in range(n):
        aaa[k][i], aaa[k][j] = aaa[k][j], aaa[k][i]


def swap(n, aaa, i, j):
    swap_rows(n, aaa, i, j)
    swap_cols(n, aaa, i, j)


def add1(n, aaa):
    for i in range(n):
        for j in range(n):
            aaa[i][j] += 1


def solve(n, yyy):
    if len(yyy) != len(set(yyy)):
        return None

    yyy = [y - 1 for y in yyy]
    diag = []
    for i in range(n):
        if yyy[i] == i:
            diag.append(i)
            continue
        if yyy[yyy[i]] != i:
            return None

    if n % 2 == 1:
        if len(diag) >= 2:
            return None
        assert len(diag) == 1
        di = diag[0]

        aaa = [list(range(i, n)) + list(range(0, i)) for i in range(n)]
        if di != 0:
            swap(n, aaa, 0, di)
        for i in range(n):
            if i == di:
                continue
            y = yyy[i]
            if aaa[i][y] == 0:
                continue
            s = aaa[i].index(0)
            swap(n, aaa, s, y)

        add1(n, aaa)
        return aaa

    # == N 偶数 ==
    diag_n = len(diag)
    if diag_n % 2 == 1:
        return None

    aaa = [[0] * n for _ in range(n)]
    for i in range(n - 1):
        for j in range(n - 1):
            x = (i + j + n - 2) % (n - 1) + 1
            if i == j:
                aaa[i][n - 1] = x
                aaa[n - 1][j] = x
            else:
                aaa[i][j] = x

    for i in range(diag_n, n, 2):
        aaa[i][i], aaa[i][i + 1] = aaa[i][i + 1], aaa[i][i]
        aaa[i + 1][i], aaa[i + 1][i + 1] = aaa[i + 1][i + 1], aaa[i + 1][i]

    diag_01 = [i for i in range(diag_n) if yyy[i] != i]
    diag_10 = [i for i in range(diag_n, n) if yyy[i] == i]
    assert len(diag_01) == len(diag_10)
    for i, j in zip(diag_01, diag_10):
        swap(n, aaa, i, j)

    for i in range(n):
        y = yyy[i]
        if aaa[i][y] == 0:
            continue
        s = aaa[i].index(0)
        swap(n, aaa, s, y)

    add1(n, aaa)
    return aaa


t = int(input())
for _ in range(t):
    n = int(input())
    yyy = list(map(int, input().split()))
    ans = solve(n, yyy)
    if ans is None:
        print('No')
    else:
        print('Yes')
        for row in ans:
            print(*row)