AtCoder Regular Contest 231 A～F問題メモ

AtCoder Regular Contest 231

A - Two Dimensional Invader

問題文

あなたは $2$ 次元平面上に存在する魔法戦士であり，最初は点 $(0, 0)$ に位置します．
これから $N$ 回のイベントが起こります．
- $i$ 回目 ($1 \leq i \leq N$) のイベントでは点 $(X_i, Y_i)$ にモンスターが $1$ 体現れます。
- あなたはこのモンスターを剣で倒すか魔法で倒すかを選択します．
  - モンスターを剣で倒すことを選択した場合，あなたは点 $(X_i, Y_i)$ に移動します．この際，あなたが移動する前に位置していた点と点 $(X_i, Y_i)$ のユークリッド距離の $2$ 乗のコストがかかります．
  - モンスターを魔法で倒すことを選択した場合，$Z_i$ のコストがかかります．この際，移動は行いません．
最終的に必要なコストの総和の最小値を求めて下さい．

$1$ つの入力ファイルにつき，$T$ 個のテストケースを解いてください．

制約

$1 \leq T \leq 10$
$1 \leq N \leq 250\,000$
$0 \leq X_i \lt 500$ ($1 \leq i \leq N$)
$0 \leq Y_i \lt 500$ ($1 \leq i \leq N$)
$1 \leq Z_i \leq 10^9$ ($1 \leq i \leq N$)
$T$ 個のテストケースにおける $N$ の総和は $250\,000$ 以下
入力される値はすべて整数である

解法

「ユークリッド距離」は $x$ 軸と $y$ 軸の足し算に分割することができないけど、「ユークリッド距離の2乗」ならできる、という点に何故か気付かなかった。言われてみれば、なんだよな。

剣なら移動が生じて、魔法なら生じない、という点が厄介。
剣のコスト計算には現在位置の情報が必要だが、 $i$ 回目のイベントの直前で存在する位置の候補は、$(0,0)$ に加え $j \lt i$ を満たす全ての $(X_j,Y_j)$ となる。（$j$ を剣で倒し、それ以降全て魔法で倒していたら、どこであろうと存在する位置としてあり得る）

ここから

$\mathrm{DP_{TLE}}[i][j]:=i$ 番目のイベントまで考慮し、最後に剣で倒したのが $j$ である場合の最小コスト

のようなDPは考えられるが、これだと $O(N^2)$ かかってしまう。

以下の2点の工夫を施す。

まず、剣のコストを「移動コスト $-Z_i$」、魔法のコストを $0$ とする。
これで求めた最終的なコストに $\sum_iZ_i$ を足すと、元の問題と同じ答えとなる。
これで、魔法を完全に無視できるようになる。

また、軸を分解する。
移動コストは出発点の座標を $(x,y)$ として $(X_i-x)^2+(Y_i-y)^2$ だが、これを「$(Y_i-y)^2$ のコストで $(x,Y_i)$ まで移動してから、 $(X_i-x)^2$ のコストで $(X_i,Y_i)$ まで移動する」と考える。まるでマンハッタン距離のようになる。

すると、$X,Y$ の取り得る座標が $\lt 500$ と小さいことから、「$y$ 軸だけ先に移動した状態」をDPとして持っておける。

$\mathrm{DP}[y][x]:=(x,*)$ を剣で倒した後、次のイベント発生前に先んじて $(x,y)$ まで移動した場合の最小コスト

「次に剣で倒すモンスターの出現位置は現時点では知らないが、とりあえず $y$ まで移動しておいた」場合のコストを求めておくということになる。

初期値は、$y=0,1,...,499$ に対し $\mathrm{DP}[y][0]=y^2$、他は $\infty$ とする。

クエリ $(X_i,Y_i)$ に対して、

剣の場合の最良コストを求める:
- $\min_{x}\mathrm{DP}[Y_i][x]+(X_i-x)^2$ を見つければよい。
- このminを $M$ とする。
更新する:
- $y=0,1,...$ について、$\mathrm{DP}[y][X_i] ← M-Z_i+(Y_i-y)^2$ とする。ただし $←$ はchminとする。

座標の範囲を $C=500$ として、1イベントに付き $O(C)$ の参照・更新2回、計 $O(NC)$ で求められる。

魔法コストを $0$ にする前だと、そのコストとして全体に $Z_i$ を加算しなければならない（$O(C^2)$ の処理）が、 $0$ にしたことでそれをサボれて、「剣を使った時に更新される箇所」のみの更新（$O(C)$ の処理）で済むようになる。

Python3

def solve(n, points):
    INF = 1 << 60
    dp = [[INF] * 500 for _ in range(500)]
    for y in range(500):
        dp[y][0] = y ** 2
    magic_sum = 0
    for x, y, z in points:
        magic_sum += z
        best = INF
        for x2 in range(500):
            if dp[y][x2] == INF:
                continue
            best = min(best, dp[y][x2] + (x - x2) ** 2)
        for y2 in range(500):
            dp[y2][x] = min(dp[y2][x], best + (y - y2) ** 2 - z)
    ans = min(min(row) for row in dp) + magic_sum
    return ans


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

B - Three Mex

問題文

非負整数 $A, B, C$ が与えられます．
以下の $3$ つの条件を満たす非負整数集合 $X, Y$ が存在するか判定し，存在する場合はその一例を示してください．
- $X, Y$ の各要素は $2026$ 以下の非負整数である．
- $\mathrm{mex}(X)=A, \mathrm{mex}(Y)=B$ である．
- 非負整数集合 $Z$ を $Z=\{x\oplus y\mid x\in X, y \in Y\}$ で定める．このとき，$\mathrm{mex}(Z)=C$ である．ただしここで，$\oplus$ はビット単位 $\mathrm{XOR}$ 演算を表します．

$1$ つの入力ファイルにつき，$T$ 個のテストケースを解いてください．

制約

$1 \leq T \leq 10$
$0 \leq A \leq 1000$
$0 \leq B \leq 1000$
$0 \leq C \leq 1000$
入力される値はすべて整数である

解法

気付けば一発の問題。

$A,B,C \le 1000$ なのに、$X,Y$ に入れられる要素は $2026$ 以下とされ、若干の余裕がある。
しかし、$1000 \lt 2^{10}=1024$ に対し、その2倍 $2^{11}=2048$ までは行かない。

このあたりの奇妙さが気づきのヒントになり得たかもしれない。

とりあえず、$X$ には $(0,1,...,A-1)$、$Y$ には $(0,1,...,B-1)$ を入れざるを得ないので、これだけの要素から $Z'$ を構成してみて、既に $C$ が含まれていたら不可能。

含まれない場合、以下のように構成可能となる。

$X$ には $1024$ を追加
$Y$ には $1024,1025,...,1024+C-1$ を追加

以下よりそれが確認できる。
$X$ に対し $(0,1,...,A-1)$ を「元からある要素」、$1024$ を「追加した要素」とする。$Y$ に対しても同様。

追加した要素によって $mex(X)=A,mex(Y)=B$ が崩れることはない。
追加した要素同士のXORで $(0,1,...,C-1)$ が $Z$ に追加される。
元からある要素と追加した要素間のXORは必ず $1024$ 以上となり、$C$ が追加されることはない。
追加した要素は最大でも $1024+C-1 \le 2026$

Python3

def solve(a, b, c):
    base = 1 << 10
    X = list(range(a))
    Y = list(range(b))
    if any(x ^ y == c for x in X for y in Y):
        return None
    X.append(base)
    Y.extend(base ^ i for i in range(c))
    return X, Y

t = int(input())
for _ in range(t):
    a, b, c = list(map(int, input().split()))
    ans = solve(a, b, c)
    if ans is None:
        print('No')
    else:
        print('Yes')
        X, Y = ans
        print(len(X), *X)
        print(len(Y), *Y)

発展

値の上限を「$X, Y$ の各要素は $1023$ 以下の非負整数である」としても解ける。
（※元の問題では可能なケースでも不可能となることはあるが、制約内で不可能であると判定はできる）

省略

最低限必要な要素だけで破綻する（$C \in [0,A) \oplus [0,B)$）場合はやっぱり不可。以下、そうでないとする。

ある $k$ に対し、$M=2^k, H=M/2, U=[0,M)$ とする。
その上で、$0 \le A,B,C \le M$ に対し「$X,Y \subseteq U$、$mex(X)=A$、$mex(Y)=B$、$mex(Z)=C$ となる $X,Y$」を解く問題を $f(A,B,C,k)$ とする。

一般性を失わず、$A \ge B$ とする。

$C=M$

$X=U\backslash \{A\},Y=U\backslash \{B\}$ とすれば、$Z=U$ となるので可。

$C \lt M, B=0$

$C=0$
- $Y=\phi$ とすれば $Z=\phi$ となり、$mex(Z)=0$ が満たされる。
$C \gt 0, A=M$
- 不可。$X=U$ となるので、$Z$ も $\phi$ でなければ $U$ しか取れない。
$C \gt 0, A \lt M, C \neq A$
- $y=A \oplus C$ とし、$Y=\{y\}$、$X=[0,A)\cup (y \oplus [0,C))$
$C \gt 0, C=A=M-1$
- 不可。$X=[0,M-1)$ に対し、$Z=[0,M-1)$ にするためには、$Y$ に $0$ を入れるしかない
$C \gt 0, C=A \le M-2$
- $y=A \oplus (A+1)$ とし、$Y=\{y\}$、$X=[0,A)\cup (y \oplus [0,C))$

$C \lt M, B \le 1, A \ge H$

$0 \in Y$ なので、$X$ の要素はそのまま $Z$ にも入る。よって $C \le A$。（そうでないケースは前提で弾かれてるはず）

$X$ は $[0,H)$ の全てを持つので、$Y$ に $H$ 以上の要素があったら必ず $Z$ には $[H,M)$ の範囲が含まれてしまう、つまり $C$ も含まれてしまう。
よって $B \le H$。（そうでないケースは前提で弾かれてるはず）

この時、$X=[0,H) \cup (H+X')$ となるように $X'$ を定義すると、 $Z=[0,H) \cup (H+(X' \oplus Y))$ なので、$f(A-H,B,C-H,k-1)$ から $X',Y$ が求められる。

$C \lt M, B \le 1, A \lt H$

$C \lt H$ の時、$A,B,C$ の全てが最上位bitを使わないので、元の問題の解法をそのまま使える。

$C \ge H$ の時、とりあえず $X'=[0,H) \backslash \{A\}$、$Y'=[0,H) \backslash \{B\}$ として、$Z'=[0,H)$ は埋まる。 $X=X'$、$Y=Y' \cup \{H+(A \oplus (C-H))\}$ とすると、$Z=U \backslash \{C\}$ が達成できる。

C - One Sky, Many Stars

問題文

長さが $N$ の非負整数列 $x = (x_1, x_2, \cdots, x_N), d = (d_1, d_2, \cdots, d_N)$ に対して，以下の問題 Stargazing を考えます．ここで，$x_1 \lt x_2 \lt \cdots \lt x_N$ とします．
Stargazing
- $1$ から $N$ までの番号が付けられた $N$ 人の人が数直線上にいます．人 $i$ ($1 \leq i \leq N$) は座標 $x_i$ にいます．
- また，数直線上には点とみなすことができる星が $1$ つ以上存在します．
- 星の配置について，人 $i$ は「自分に一番近い星までの距離は $d_i$ である」と証言しています．なお，自分との距離が最短となる星が複数存在しても構いません．
- $N$ 人の証言に矛盾しないような星の配置が存在するか判定し，存在する場合は Yes を，そうでない場合は No を出力してください．

長さが $N$ の非負整数列 $A = (A_1, A_2, \cdots, A_N), B = (B_1, B_2, \cdots, B_N)$ が与えられます．
$Q$ 個のクエリを処理してください．$j$ 番目 ($1 \leq j \leq Q$) のクエリは以下のように表されます．
- $1$ 以上 $N$ 以下の整数 $P_j$ と非負整数 $S_j$ が与えられます．
- 人 $P_j$ の証言 $B_{P_j}$ を、$S_j$ に変更してください．
- その後，$x, d$ をそれぞれ $A, B$ とした場合の Stargazing を解いてください．
- なお，$B_{P_j}$ の変更は以降のクエリにも引き継がれます．

$1$ つの入力ファイルにつき，$T$ 個のテストケースを解いてください．

制約

$1 \leq T \leq 10$
$1 \leq N \leq 150\,000$
$0 \leq A_1 \lt A_2 \lt \cdots \lt A_N \leq 10^9$
$0 \leq B_i \leq 10^9$ ($1 \leq i \leq N$)
$1 \leq Q \leq 150\,000$
$1 \leq P_j \leq N$ ($1 \leq j \leq Q$)
$0 \leq S_j \leq 10^9$ ($1 \leq j \leq Q$)
$T$ 個のテストケースにおける $N$ の総和は $200\,000$ 以下
$T$ 個のテストケースにおける $Q$ の総和は $200\,000$ 以下
入力される値はすべて整数である

解法

Yesとなる条件は以下をともに満たすことである。

各人が証言する最寄りの星より、近い位置に星があってはいけない
各人が証言する位置（$x_i-d_i$ または $x_i+d_i$）のいずれかに星が必要

つまり、$L_i=x_i-d_i,R_i=x_i+d_i$ と変換した時、Stargazing は、以下のように言い換えられる。

$N$ 個の開区間 $(L_i,R_i)$ がある。
全ての $i$ について以下の条件が成り立つならYes、1つでも成り立たないならNoを出力せよ
- $L_i,R_i$ の少なくともいずれかは、他の開区間に内包されていない。

ただし、中心の座標 $\frac{L_i+R_i}{2}$ は $i$ に対して狭義単調増加である。

ある $i$ が「$L_i,R_i$ の両方とも他の開区間に内包される」ことを「破綻する」と呼ぶことにする。

実際に具体的なケースで考えてみると、破綻する人は、“隣り合う人”の開区間に含まれる、というケースが多い。少し考えると、以下が成り立つことが分かる。

（★）No である場合、少なくとも1つは、$L_i,R_i$ がともに $i-1$ または $i+1$ の開区間に含まれる $i$ が存在する。

i-1  (-v-----)                (----------v--v-)
 i     x---------x       or              x--x     のような i が必ず存在する
i+1            (-^----)

もちろん、破綻する $i$ の中には、「両端が、$i-1$ や $i+1$ の区間には含まれないのに、$i-2$ 以前や $i+2$ 以降の区間に含まれることで破綻する」というケースも存在はする。しかしその場合、必ず他に条件を満たす $i$ が存在する。「中心座標が狭義単調増加」であることが、有効に働く。

i の左端が i-1 には内包されないが i-2 以前に内包される、という例は以下の3通り。

i-2 (-----)             i-1 が i に内包される場合
i-1        (--)         言うまでも無く、i-1 が★の条件を満たすことになる。
 i      (----------)

i-3 (-------)           i と i-1(, i-2, ...) で左端が一致する場合
i-2       (---)         iの左端は i-1 には内包されないが、i-2以前に内包される可能性がある。
i-1       (-----)       ここで、「区間は中心が狭義単調増加」より、i-1 の右端は必ず i に内包される。
 i        (-------)     よって i の左端が i-2 以前のいずれかに内包されるなら i-1 も必ず破綻する。
                        左では、同じことが i-1とi-2 の関係にも言え、i-2 が★を満たすことになる。

i-3 ----------------)      i-1 とは重なりを持たないが、i-2以前から伸びてきた区間に内包される場合
i-2   (---)                この場合、i-1 もその伸びてきた区間に完全に内包されている。
i-1         (---)          i が破綻するなら i-1 も破綻する。
 i                (----)   左では、同じことが i-1とi-2 の関係にも言え、i-2 が★を満たすことになる。

複合することもあり得るが、いずれにせよ「$i$ が破綻するなら $i-1$ も必ず破綻し、遡っていくといつかは、$j-1$ に内包される $j$ に（存在すれば）行き着く」ことになる。

$T_i:=$ $i$ が「$L_i,R_i$ がともに $i-1$ または $i+1$ の開区間に含まれる」なら $1$、そうでないなら $0$

として、$\sum T_i \gt 0$ なら No と判定できることになる。

クエリによる更新時は、高々 $T_{i-1},T_i,T_{i+1}$ の3箇所について更新すれば十分であり、$O(N+Q)$ で解ける。

Python3

def solve(n, aaa, bbb, q, queries):
    def check_included(i):
        l = aaa[i] - bbb[i]
        r = aaa[i] + bbb[i]
        ll = aaa[i - 1] - bbb[i - 1]
        lr = aaa[i - 1] + bbb[i - 1]
        rl = aaa[i + 1] - bbb[i + 1]
        rr = aaa[i + 1] + bbb[i + 1]
        if (ll < l < lr or rl < l < rr) and (ll < r < lr or rl < r < rr):
            return 1
        return 0

    aaa = [-1 << 60] + aaa + [1 << 60]
    bbb = [0] + bbb + [0]
    ngs = []
    for i in range(1, n + 1):
        ngs.append(check_included(i))
    
    ng_count = sum(ngs)
    buf = []
    for p, s in queries:
        p -= 1
        bbb[p + 1] = s
        for i in range(p - 1, p + 2):
            if i < 0 or n - 1 < i:
                continue
            ng_count -= ngs[i]
            ngs[i] = check_included(i + 1)
            ng_count += ngs[i]
        if ng_count == 0:
            buf.append('Yes')
        else:
            buf.append('No')
    return buf


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    q = int(input())
    queries = [list(map(int, input().split())) for _ in range(q)]
    ans = solve(n, aaa, bbb, q, queries)
    print('\n'.join(ans))

D - Choose Your Role

問題文

この問題はインタラクティブな問題です．
$1$ から $N$ までの番号が付けられた $N$ 個の山があります．それぞれの山には石が $N - 1$ 個ずつあります．
これらを用いて先手と後手でゲームを行うことを考えます．ゲームでは先手から交互に手番を行います．
- 先手は石が $1$ つ以上存在する山を $1$ 個選ぶ．そこから $1$ 個以上 $K$ 個以下の石を取り除く．
- 後手は石が $1$ つ以上存在する山を $1$ 個以上 $K$ 個以下選ぶ．それらから石を $1$ 個ずつ取り除く．
先に操作ができなくなった方の負けです．
あなたはこのゲームをジャッジと対戦します．まず，ジャッジにあなたが先手となるか後手となるかを宣言し，その後ゲームを行って勝ってください．

制約

$2 \leq N \leq 200$
$1 \leq K \leq N$
入力される値はすべて整数である

解法

未証明。

$K=1$ の時は石を1個ずつ取っていくだけであり、総数が偶数なのでどうやっても後手が勝つ。$K \ge 2$ を考える。

実験すると、小さい範囲では全て後手勝ちとなる。途中の状態（$(2,3,3,4)$ など山の石の数が必ずしも同じでない状態）も、圧倒的に後手勝ち状態が多い。
（※状態は、0以外の各山の石の数を昇順に並べることで表現している）

後手必勝と仮定して考える。

操作は、$(N-1) \times N$ の長方形を、先手は縦に、後手は横に削っていくようなイメージであり、最後に（サイズ2以上で）縦に1列残ったら先手が、横に1列残ったら後手が、勝ちと決まる。初期状態がわずかに横に長い分だけ、後手が有利そうなのは頷けるが、、、

なるべく早く「横に1列」の状態にしたいので、「★:石が $2$ 個以上で多く残る山から優先的に $K$ 個取る」という戦略が思いつく。

これは実験するとそれなりに勝て、負けるケースも存在するが非常に限られている。
例えば $N=8,K=3$ では後手番で $(4,4,4,5,5)$ → $(3,4,4,4,4)$ とするのが唯一の失着手で後手必勝状態から先手必勝状態に移行するが、それ以外には★の戦略の失着は存在しない。

どうも、$(K+1,...,K+1,K+2,...,K+2)$（長さ $K+2$）という状態で回ってきたときに、 $(K,K+1,...,K+1)$ としてしまうのが失着となりそうなので、それを避けるようにすれば勝てる。

まとめると、石が $1$ 個以上残っている山における石の最小数を $m$、最大数を $M$ として、

$M=1$ の場合
- 石が $1$ 個残る山が $K+1$ 個の場合、$K-1$ 個取って2個残す。
- それ以外の場合、$\min(K,山の数)$ 取る。
$m=K+1,M=K+2$ の場合
- $\min(K,M個残る山の数)$ 取る。
それ以外
- $2$ 個以上残る山の、多く残る方から $\min(K,山の数)$ 個

とすると通る。

Python3

from collections import defaultdict


def solve(n, k):

    def restore_index(piles, aaa):
        indices = []
        for i, p in enumerate(piles, start=1):
            if p in aaa:
                indices.append(i)
                aaa[p] -= 1
                if aaa[p] == 0:
                    del aaa[p]
        indices.sort()
        return indices

    def strategy(piles):
        # aaa = [(i, a) for i, a in enumerate(piles, start=1) if a > 0]
        aaa = sorted((a for a in piles if a > 0), reverse=True)
        n = len(aaa)
        mn = aaa[-1]
        mx = aaa[0]
        if mx == 1:
            if k >= 2 and k + 1 == n:
                return restore_index(piles, {1: k - 1})
            return restore_index(piles, {1: min(k, n)})
        if mn == k + 1 and mx == k + 2:
            mx_cnt = sum(mx == a for a in aaa)
            return restore_index(piles, {mx: min(k, mx_cnt)})
        ddd = defaultdict(int)
        for i in range(min(n, k)):
            if aaa[i] == 1:
                break
            ddd[aaa[i]] += 1
        return restore_index(piles, ddd)

    print('Second')
    piles = [n - 1] * n
    while True:
        i, j = list(map(int, input().split()))
        if i == j == -1:
            break
        if i == j == 0:
            break
        i -= 1
        piles[i] -= j

        aaa = strategy(piles)
        print(len(aaa))
        print(*aaa, flush=True)
        for i in aaa:
            piles[i - 1] -= 1


n, k = list(map(int, input().split()))
solve(n, k)

証明付き解法

解説 - AtCoder Regular Contest 231

山と石を以下のようにイメージする。対角線上に空白が空いているが、右上の三角形をそのまま下に1段下ろしたのが本来の個数を表すヒストグラムとなる。（解説ではわかりやすさのため空いたままとする）

N=6
    □□□□□
↑□  □□□□
石□□  □□□
の□□□  □□
数□□□□  □
  □□□□□
  ←   山   →

後手は、常に先手と対角線で鏡映しになった戦法を採れる。よって後手必勝となる。

  □■□□□        □■□□□
□  ■□□□      □  ■□□□
□□  □□□  →  ■■  ■□□
□□■  □□      □□■  □□
□□□□  □      □□□□  □
□□□□□        □□□□□

  ●■□□□        ●■□□□
□  ■□□□      ●  ■●●□
■■  ■□□  →  ■■  ■□□
□●■  □□      □●■  □□
□●□□  □      □●□□  □
□□□□□        □□□□□

かしこい。

E - Odd Inversion

問題文

長さが $N$ の正整数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます．
- ここで，$A_1 \leq A_2 \leq \cdots \leq A_N$ が成立します．
以下の条件を満たす長さが $N$ の正整数列 $B$ としてありうる個数を $998244353$ で割ったあまりを求めてください．
- $1 \leq B_i \leq A_i$ ($1 \leq i \leq N$)
- $B$ の転倒数は奇数
ここで，$B$ の転倒数とは $1 \leq i \lt j \leq N$ を満たす整数の組 $(i, j)$ で $B_i \gt B_j$ であるものの個数を表します．

$1$ つの入力ファイルにつき，$T$ 個のテストケースを解いてください．

制約

$1 \leq T \leq 10000$
$1 \leq N \leq 200000$
$1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9$
$T$ 個のテストケースにおける $N$ の総和は $400000$ 以下
入力される値はすべて整数である

解法

主客転倒のアプローチは筋が悪い。
つまり、各 $(i,j)$ について「$B_i \gt B_j$ となる確率」みたいなのを求めたところで、各ペアの確率同士が独立ではないので、$B$ 全体の転倒の個数が偶数か奇数かはわからない。転倒数の“総和”とかなら求められるんだけど。。。

先頭 $i$ 項目までで、転倒数が偶数となる $B$ の個数を $E_i$、奇数となる $B$ の個数を $O_i$ とする。

$E_i,O_i$ を直接求めていくのは難しいのだが、「差分 $D_i=E_i-O_i$」がわかればよい。
$E_i+O_i=\prod_{1 \le j \le i}A_j$ なので、そこから $D_i$ を引いて2で割れば $O_i$ となる。

末尾2個をどうするか、を考えると良い性質が見える。

                     i-1  i
B  [    1～i-2    ]   ?   ?

$B_i \le A_{i-1}$ の時

$B_{i-1}=B_{i}$ の時

$B_1～B_{i-2}$ の中で $B_{i-1}$ と転倒関係にあるものと、$B_{i}$ と転倒関係にあるものの個数は等しい。
$B_{i-1}$ と $B_i$ の間では転倒していないので、このケースでは転倒数の偶奇は変化しないことになる。

このような $B_{i}$ の決め方は $A_{i-1}$ 通りあるので、$D_i+=D_{i-2} \times A_{i-1}$ だけ寄与する。

$B_{i-1} \neq B_{i}$ の時

                     i-1  i
B  [    1～i-2    ]   3   5
B  [    1～i-2    ]   5   3

入れ替えた2つの組で、転倒数が偶数のものと奇数のものが同数だけできる。打ち消しあい、$D_i$ に対する寄与は $0$ となる。

（$E_i,O_i$ のまま計算すると、この係数を求めるのが難しいが、差分を考えることで打ち消され楽になる）

$B_i \gt A_{i-1}$ の時

転倒数は、$D_{i-1}$ から変化しない。このような $B_i$ の決め方は $A_{i}-A_{i-1}$ 通りある。

$D_i+=D_{i-1} \times (A_{i}-A_{i-1})$ だけ寄与する。

以上の3ケースで網羅でき、$D_i=D_{i-2} \times A_{i-1} + D_{i-1} \times (A_{i}-A_{i-1})$ で表されることが分かる。

$D_0=1,D_1=A_1$ なので、$D_2,...,D_N$ を漸化式で求めていけばよい。

Python3

def solve(n, aaa):
    MOD = 998244353
    INV2 = 499122177
    total = aaa[0]
    diff0 = 1
    diff1 = aaa[0]
    for i in range(1, n):
        a1 = aaa[i - 1]
        a2 = aaa[i]
        total = total * a2 % MOD
        diff0, diff1 = diff1, (diff0 * a1 + diff1 * (a2 - a1)) % MOD
    ans = (total - diff1) * INV2 % MOD
    return ans


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

F - Two Unbalanced Subtrees

問題文

正整数 $N$ が与えられます．
頂点数が $2^N - 1$ の完全二分木があります．
頂点 $1$ が根であり，頂点 $i$ は頂点 $2i$ と頂点 $2i + 1$ を子として持ちます．($1 \leq i \lt 2^{N - 1}$)
以下の条件を満たすように各頂点に $1$ 以上 $2^N - 1$ 以下の整数を書き込みます．
- 書き込む $2^N - 1$ 個の整数は互いに相異なるようにする．
- 頂点 $i$ ($1 \leq i \lt 2^{N - 1}$) について，頂点 $i$ に書き込まれた整数は，頂点 $2i$ を根とする部分木の各頂点に書かれた整数の総和と，頂点 $2i+1$ を根とする部分木の各頂点に書かれた整数の総和の差の絶対値である．
頂点 $1$ に書き込まれる整数を最小化するものを一つ求めてください．
この問題の制約下で条件を満たす整数の書き込み方が必ず存在することが証明できます．

制約

$2 \leq N \leq 18$
入力される値はすべて整数である

解法

実験からの推測が効く問題は解きやすい。

対称性より、右の子の方が左の子より重い（部分木に書かれた整数の総和が大きい）という前提を置いてよい。

小さいサイズから考えると、書き込める整数には綺麗な制約が見える。

N=2
  ◎        ● - ○ = ◎ より、
  /\        ◎以下全体は 2×●
 ○●

N=3 △
   ／＼     ◇以下は 2×■
  ◇  ◎    ◎以下は 2×●
  /\  /\    よって△は 2×(●-■) より、必ず2の倍数
 □■○●   また、△以下全体では 4×●

N=4    ○        ←4の倍数
     ／  ＼
   ○      △    ←2の倍数
  ／＼    ／＼
 ○  ○  ◇  ◎  木全体は 8×●
 /\  /\  /\  /\   
○○○▲□■○●

このように、部分木全体の総和は必ず（右の子の方が大きいという前提の上で）右下の値の $2^{N-1}$ 倍となることがわかる。つまり、下2段以外は、下から $2,4,8,16,...$ の倍数である必要がある。
頂点 $1$ に書き込まれる値は、$2^{N-2}$ の倍数でなければならない。

いくつかの仮定を敷いた上で、一意に決まる値から埋めていき、機械的に構築しやすそうな例を探してみる。

右下（●）は、以下より最大値（$N=4$ では $15$）が確定する。

下2段以外は倍数制約より不可
下から2段目は、何かから何かを引いて最大値を作ることはできないので不可
最下段は、根までのトーナメントのどこかで他の最下段頂点と比べられ、右端が必ず勝ち上がる＝右端が最大値

下限 $2^{N-2}$ が可能と仮定して考えてみる。この時、▲+1=● が成り立つ。

また、下2段の末端で三角形上に並ぶ各3頂点は、その中では右下が一番大きくなければいけない。

 ○    この中では◎が一番大きい
 /\
○◎

なるべく法則性のある配置を見つけたいので、次に大きい $12,13$ も、この◎に相当する位置に配置すると仮定してみる。重複を避けると、以下のように決まる。

       ４
     ／  ＼
   ２      ６
  ／＼    ／＼
 ○  ○  ○  ○
 /\  /\  /\  /\
○13○14○12○15

残る数字は $1,3,5,7,8,9,10,11$ なのだが、これを端からペアにすると、ちょうど $12,13,14,15$ が作れることがわかる。

       ４
     ／  ＼
   ２      ６
  ／＼    ／＼
 ３  ５  １  ７
 /\  /\  /\  /\
⑩⑬⑨⑭⑪⑫⑧⑮

$N=2,N=3$ についても同様の方針で構築したのを並べて示す。

N=2  N=3        N=4
 １     ２           ４
 /\    ／＼        ／  ＼
２３  １  ３     ２      ６
      /\  /\    ／＼    ／＼
     ５６４７  ３  ５  １  ７
               /\  /\  /\  /\
              ⑩⑬⑨⑭⑪⑫⑧⑮

観察すると、$N-1$ から $N$ を再帰的に構築できそう。

$N-1$ の配置の最下段以外を2倍すると、$N$ の下2段以外になっている。
$N-1$ の最下段を、大小の順序はそのまま $2^{N-1}$ 未満の奇数に置き換えると、$N$ の下から2段目となっている。
- $N=3$ の最下段 $(5,6,4,7)$ を、$N=4$ においてこの順で奇数に置き換えると $(3,5,1,7)$
$N$ の新たな最下段は容易に構築できる。
- $N=4$ においては、下から2段目の小さい方から順に $(11,12),(10,13),(9,14),(8,15)$ としていく。

これを再帰的に構築するプログラムを提出すると、通る。

これで上手くいく理由

上記の構築方法は、$3$ 段目以降のどの階層においても、「同じ階層では兄弟要素の和が全て一定」であることが保証される。

$5+6=4+7$
$3+5=1+7$
$10+13=9+14=11+12=8+15$

この条件が満たされていることを、「階層が等しい」と呼ぶことにする。
全ての階層が等しい状態では、左右の子の部分木の総和において、 2階層以上、下の頂点の影響はなくなり、直接の子の差分だけが重要となる。

       ４
     ／  ＼       4は、直接の子の差分 6-2 だけに影響される。
   ２      ６
  ／＼    ／＼
 ⊂ニ⊃  ⊂ニ⊃   等しい
 /\  /\  /\  /\
⊂⊃⊂⊃⊂⊃⊂⊃  それぞれ等しい

その上で、以下を示す。

問題の条件を満たす数字の配置のうち、以下の2条件を満たすものを「良い配置」とする。
- 全ての階層が等しい
- 最下段以外に $1～2^{N-1}-1$、最下段に $2^{N-1}～2^{N}-1$ が配置されている。
この時、$N$ の良い配置から、$N+1$ の良い配置を構築できる。

ある頂点に対し、「左右の子の部分木の総和の差が、その頂点の値」という条件が満たされていることを「★」とする。
良い配置では、最下段以外の全ての頂点が★である。

良い配置から各頂点を2倍しても、全ての階層が等しいこと、また★である頂点は★のまま保たれる。

2倍した時点では、最下段は $2^N～2^{N+1}-2$ にある偶数（下例 $10,12,8,14$）が全て含まれる状態になっている。適切にシフトし、各兄弟要素の差と、階層が等しい状態を変えないまま、$1～2^N-1$ の奇数（$3,5,1,7$）が全て含まれる状態に変更できる。

最下段以外は、$2～2^N-2$ の偶数が全て含まれるので、あわせて $1～2^N-1$ の整数が全て含まれる状態になる。

   ２        ４        ４
  ／＼  →  ／＼  →  ／＼  
 １  ３    ２  ６    ２  ６
 /\  /\    /\  /\    /\  /\ 
５６４７  ⑩⑫⑧⑭  ３５１７

この最下段に $2^N～2^{N+1}-1$ を先述の方法で追加すると、その階層も等しくなり、$N+1$ の良い配置とすることができる。

       ４
     ／  ＼  
   ２      ６
  ／＼    ／＼
 ３  ５  １  ７
 /\  /\  /\  /\
⑩⑬⑨⑭⑪⑫⑧⑮

Python3

def solve(n):
    ans = [0] * (1 << n)
    ans[1] = 1
    ans[2] = 2
    ans[3] = 3
    for i in range(2, n):
        h = 1 << (i - 1)
        d = h + (1 << i)
        for j in range(1, h):
            ans[j] *= 2
        for j in range(h, h * 2):
            t = ans[j] - h
            ans[j] = t * 2 + 1
            ans[j * 2] = d - t - 1
            ans[j * 2 + 1] = d + t

    return ans[1:]


n = int(input())
ans = solve(n)
print(*ans)

目次

AtCoder Regular Contest 231 A～F問題メモ

A - Two Dimensional Invader

問題文

制約

解法

B - Three Mex

問題文

制約

解法

発展

$C=M$

$C \lt M, B=0$

$C \lt M, B \le 1, A \ge H$

$C \lt M, B \le 1, A \lt H$

C - One Sky, Many Stars

問題文

制約

解法

D - Choose Your Role

問題文

制約

解法

証明付き解法

E - Odd Inversion

問題文

制約

解法

$B_i \le A_{i-1}$ の時

$B_{i-1}=B_{i}$ の時

$B_{i-1} \neq B_{i}$ の時

$B_i \gt A_{i-1}$ の時

F - Two Unbalanced Subtrees

問題文

制約

解法