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

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)

目次

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

A - Bitwise OR Game

問題文

制約

解法

B - Sum of Mod

問題文

制約

解法

C - Mod of XOR

問題文

制約

解法