AtCoder Regular Contest 217 A,B,C問題メモ

AtCoder Regular Contest 217

A - Min of Sum of XOR

問題文

正整数 $N$ が与えられます。
$(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ であって、 $\displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j$ を最小化するものを一つ求めてください。
ただし、 $\displaystyle \bigoplus_{1\le j\le i} P_j$ は $P_1,P_2,\ldots,P_i$ のビット単位 $\mathrm{XOR}$ として定義されます。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

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

解法

実験あるべし。$O(N!)$ の愚直解を書いて調べれば、

N   最小値を与えるP（のうち辞書順最小のもの）
3   1 3 2
4   1 3 2 4
5   1 3 2 4 5
6   1 3 2 4 5 6
7   1 3 2 4 5 7 6
8   1 3 2 4 5 7 6 8
...

なので、2番目と3番目、6番目と7番目、、、$4k+2$ 番目と $4k+3$ 番目が入れ替わったものが最適と推測できる。

Python3

def naive(n):
    from itertools import permutations
    ans = 1 << 60
    best = ()
    for ppp in permutations(range(1, n + 1)):
        result = 0
        tmp = 0
        for p in ppp:
            tmp ^= p
            result += tmp
        if ans > result:
            ans = result
            best = ppp
    return ans, best


def check():
    print(naive(3))
    print(naive(4))
    print(naive(5))
    print(naive(6))
    print(naive(7))
    print(naive(8))
    print(naive(9))
    print(naive(10))


def solve(n):
    ans = list(range(1, n + 1))
    for i in range(1, n - 1, 4):
        ans[i], ans[i + 1] = ans[i + 1], ans[i]
    return ans


# check()

t = int(input())
for _ in range(t):
    n = int(input())
    ans = solve(n)
    print(*ans)

ちゃんと解く

あるbitだけについて見たとき、$1～N$ でその bit が立った数が $k$ 個あったら、

そのbitが立っている数を、できる限り2個ずつ隣接させて並べる
奇数だったら、余った1つは最後に持ってくる

とすると、そのbitに関しての総和は最小化できる。
その時、$\left \lceil \frac{k}{2} \right \rceil$ 回、そのbitは和に計上される。

あるbitだけ取り出したP   1 1 0 0 0 1 1 0 1 1 1 1 0 1
累積xor                  1 0 0 0 0 1 0 0 1 0 1 0 0 1
                           ^         ^     ^   ^      1が立ったらすぐさま打ち消すのが良い

全てのbitについてこのように配置できれば全体としても下限になるのだが、実際には他のbitとの兼ね合いで、必ずしも“1”を2個隣接させられなかったり、奇数の時に最後を“1”にできない可能性がある。

さて、上記の「$4k+2,4k+3$ をswap」解法がどうなっているかというと、

:        |→下2bit
... 1 0 1 0 0
... 1 0 1 0 1
... 1 0 1 1 1
... 1 0 1 1 0
... 1 1 0 0 0
... 1 1 0 0 1
... 1 1 0 1 1
... 1 1 0 1 0
:

4個1セットで考えると、

下2bit以外は4つずつ同じ要素が隣接しているので、すぐ打ち消される
下2bitも、うまく2個ずつ“1”が隣接する構造になっている

ので、セットが揃っていた場合、全てのbitで下限を達成できる構造になっているのが分かる。

後は、最後の $N$ 付近で、セットの途中で打ち切られるときにどうなるかだが、、、

下2bit以外は、全て“0”か全て“1”かのどちらかであり、途中で切られても下限を達成できる。（立ったらすぐ打ち消し、奇数なら最後に“1”が立つ）

下2bitは

$N=4k+3$ の時
- ちょうど4個セットの切れ目となるので、下限を達成できる。
$N=4k$ の時、“00” で終わる。
- 下限を達成できる。
$N=4k+1$ の時、“00”,“01” で終わる。
- 下1bit目は奇数個だが、最後に“1”が立つのでOK。下限を達成できる。
$N=4k+2$ の時、“00”,“01”,“10” で終わる。
- この場合だけ、下1bit目、2bit目がともに奇数個となるが、両方の“1”を同時に最後に持ってくることができないため、下限を達成できない。
- 最も影響の少ない1bit目の“1”を最後から2番目にすることで、下限+1 は達成できている。

$N=4k+2$ の時以外は下限を達成できる。
$N=4k+2$ の時、他の並べ方でも下限を達成できる方法が無いことを示す。

$1～N-1$ までで各bit毎に“1”が立っている個数を考えると、下1bitのみ奇数、他は全て偶数である。つまり、$1～N$ まででは「$N$ で立っているbit + 下1bit」が奇数個になる。下限を達成するためにはこれらを最後、同時に“1”にしなければいけないが、その整数は確実に $N+1$ 以上なので、使うことはできない。
よって、下限を達成する方法はない。

多くは下限を達成でき、達成不可能なとき下限+1ができるので、$4k+2,4k+3$ 番目のswapが最適であることが分かる。

B - Not High Element

問題文

整数 $N,K$ と長さ $K$ の整数列 $A=(A_1,A_2,\ldots,A_K)$ が与えられます。
- $A$ の各要素は $1$ 以上 $N$ 以下で相異なることが保証されます。
$(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ に対して $f(P)$ を以下のように定義します。
- $P$ に対して以下の操作を行うことのできる回数の最大値。
  - $P_i \lt \max(P_1,P_2,\ldots,P_{i-1})$ を満たす $2\le i\le N$ を選び、$P_i$ を先頭に移動させる。
  - つまり、$P$ を $(P_i,P_1,P_2,\ldots,P_{i-1},P_{i+1},\ldots,P_N)$ で置き換える。
$A$ をprefixに持つような $P$ は $(N-K)!$ 通りありますが、それら全てに対する $f(P)$ の総和を $998244353$ で割ったあまりを求めてください。

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

制約

$1\le T\le 10^5$
$1\le K\le N$
全てのテストケースにおける $N$ の総和は $5\times 10^5$ 以下
$1\le A_i\le N$
$A$ の各要素は相異なる
入力される値は全て整数

解法

実験により、以下の仮定に気付く。

操作回数を最大化するには、その時点で操作できる最も小さな $P_i$ に操作するのが最適である。
はじめて要素 $x$ を先頭に持ってきてから、$1～x$ が昇順に並ぶまで（＝$x$ 以下のどの要素にも操作できなくなるまで）、$2^{x-1}$ 回の操作が可能となる。

3 1 5 4 2
1 3 5 4 2    コ はじめて1を先頭に持ってきてから 1～1 が昇順に並ぶまで1回
2 1 3 5 4    ┐ はじめて2を先頭に持ってきてから 1～2 が昇順に並ぶまで2回
1 2 3 5 4    ┘   この時点で3には操作できないので飛ばして、、、
4 1 2 3 5    ┐ はじめて4を先頭に持ってきてから 1～4 が昇順に並ぶまで8回
1 4 2 3 5    │
2 1 4 3 5    │
1 2 4 3 5    │
3 1 2 4 5    │
1 3 2 4 5    │
2 1 3 4 5    │
1 2 3 4 5    ┘

略証

$P$ が固定された問題を考える。

ある時点で操作可能な値の集合を $S$ とする。

3 1 5 4 2  →  S = {1,2,4}

この時、$S$ の要素のうち $x$ に操作したとすると、変化は

$x$ 自身: 左端に移動するので必ず操作できなくなる。つまり $S$ から除外される。
$x$ より小さい値: 左端に $x$ が来るので、$S$ に含まれていないものも全て含まれるようになる。
$x$ より大きい値: 変わらない。

と一意に決まるので、具体的な並び順は捨象して、$S$ に対する操作と考えていい。

この性質から、最も小さい要素以外に操作した場合（$x$ とする）、その推移先は、最も小さい要素を選択し続ける操作手順において、始めて $x$ に操作した推移先と一致する。

最も小さい要素から              それ以外の操作例
{1,2,4}                         {1,2,4}
{2,4}─┐はじめて                ↓1を飛ばして2に対して操作
{1,4}←┘2に操作    ←一致→    {1,4}
{4}
{1,2,3}
{2,3}
...

つまり、1回以上操作を損しているため、最も小さい要素に操作し続けるのが最適である。

また回数は、$S$ を「その要素の位置だけ bit が立った整数」と捉えると、綺麗な性質がある。

                      4321
S={1,2,4}  →  f(S) = 1011（2進数）

「$S$ の最も小さい要素に対して操作する」というのは、ちょうど $f(S)$ を1減らす操作と一致する。

S              f(S)
{1,2,4}  →    1011
{2,4}    →    1010
{1,4}    →    1001
{4}      →    1000
{1,2,3}  →    0111
{2,3}    →    0110
...

よって、初期状態の $S$ に対する $\displaystyle f(S)=\sum_{x \in S}2^{x-1}$ が、答えとなる。

初期状態で自身より大きい値が左側にあるような $P_i$ に対し、$2^{P_i-1}$ の合計が答えとなる。

さて、元の問題に戻って、prefix $A$ のみが固定されている場合を考える。

期待値で考える。操作する要素 $x=1～N$ に対して、$2^{x-1}$ が答えに寄与するかどうかは独立に考えられる。$A$ の最大値を $m$ とする。

$x$ が $A$ に含まれ、かつ自身より大きい値が左側にある: 確定で $2^{x-1}$
$x$ が $A$ に含まれ、かつ自身より大きい値が左側にない: 確定で $0$
$A$ に含まれず、$m$ より小さい: 確定で $2^{x-1}$
$A$ に含まれず、$m$ より大きい: ※後述

4つめ（※）が、prefix以外の並び順によって寄与が変化するところである。
「$A$ に含まれず、$m$ より大きい」値が全部で $k$ 個あるとすると、この部分の期待値は以下の和となる。

$x=N-k+1$
- $k$ 個のうち、$x$ が最初に出現する場合のみダメ。→期待値 $2^{N-k} \times \frac{k-1}{k}$
$x=N-k+2$
- $k-1$ 個のうち、$x$ が最初に出現する場合のみダメ。→期待値 $2^{N-k+1} \times \frac{k-2}{k-1}$
：
$x=N-1$
- $2$ 個のうち、$x$ が最初に出現する場合のみダメ。→期待値 $2^{N-2} \times \frac{1}{2}$
$x=N$
- $1$ 個のうち、$x$ が最初に出現する場合のみダメ。（必ずダメ）

期待値に場合の数 $(N-K)!$ をかけたものが答えとなる。

Python3

def solve(n, k, aaa):
    MOD = 998244353
    aaa = [a - 1 for a in aaa]
    tmp_max = -1
    exp = 0
    used = [False] * n
    for a in aaa:
        if tmp_max > a:
            exp += pow(2, a, MOD)
            exp %= MOD
        else:
            tmp_max = a
        used[a] = True
    for a in range(n):
        if used[a]:
            continue
        if a < tmp_max:
            exp += pow(2, a, MOD)
        else:
            exp += pow(2, a, MOD) * (1 - pow(n - a, -1, MOD))
        exp %= MOD
    ans = exp
    for i in range(2, n - k + 1):
        ans *= i
        ans %= MOD
    return ans


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

C - Greedy Customers 2

問題文

AtCoder 商店には $N$ 個の品物があります。$i$ 番目の品物は $A_i$ 円です。
AtCoder 商店に $N$ 人の人が順番にやってきます。各人の所持金は $C$ 円で、以下の手続きを行います。
- 買い物に使う予算として、$1$ 以上 $C$ 以下の整数 $x$ を一様ランダムに選ぶ。
- AtCoder 商店に残っている品物の中に $x$ 円以下のものが存在すれば、その中で最も高価なものを $1$ つ購入する。存在しない場合は何も購入せず店を去る。
AtCoder 商店の経営者であるあなたは、品物が何個売れるか知りたくなりました。$k=0,1,2,\ldots,N$ について、最終的に品物がちょうど $k$ 個売れる確率を $\ \text{mod}\ 998244353$ で求めてください。

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

制約

$1\le T$
$1\le N$
全てのテストケースにおける $N$ の総和は $100$ 以下
$1\le A_i \le C \lt 998244353$
入力される値は全て整数

解法

$N$ 人の客が選んだ予算の多重集合が等しければ、順番に依らず、品物の売れ方は変わらない。

更に言うと、商品の値段のユニークな種類数を $M$ 個として、実質的に品物の売れ方に差異が生じる予算は $M+1$ 種類の区間に分けられる。「各客の予算が属する区間」の多重集合が等しければ、品物の売れ方は変わらないと言える。

N=6  A=[2,2,5,9,9,9]  C=15  →  M=3

予算 1    2    5    9   15
区間 [   )[   )[   )[    ]   予算が異なっても、入る区間が一緒なら、品物の売れ方は一緒。
      ↑   ↑   ↑    ↑     4個の区間のそれぞれに計6人の客の予算を配置

つまり、問題はこう言い換えられる。

$0～M$ の番号が付いた $M+1$ 個の箱に、$1～N$ の番号が付いた $N$ 個のボールを入れる。
箱 $i$ に入ったボール $j$ が処理される順番になったら、客 $j$ は、$A$ の（ユニークな）$i$ 番目に小さい値以下の品物が残っていたら購入できる。
- 箱 $0$ に入っていたら何も購入できない

ここで、問題文の通りの処理では「ボール $1,2,...,N$ の順に処理」することになるが、「全体でいくつの品物が購入されるか」という点では「箱 $0,1,...,M$ の順に、中に入ったボールを処理」しても変わらない。
つまり、ボールの番号は一旦忘れて、各箱に入った個数のみを添字としたDPができ、番号の付け方は後から考えればよい。

以上を念頭に置きつつ、ひとまず、各箱へボールをいくつ入れるかを固定した時、何個の商品が売れるかを考える。
$Y_i$ を「箱 $i$ に入れたボールの個数」とし、ボールの入れ方の一例を $Y=(Y_0,...,Y_M)$ で表す。

左の箱から累積和を取ったとき、「商品の個数の累積和 < 実際に商品を購入できたボールの累積和」となることはできない。
つまり以下の表で、$X_i \lt Z_i$ となる $i$ があってはいけない。

          予算    1    2    5    9   15
          区間    [   )[   )[   )[    ]
         index     0    1    2    3

        商品数     0    2    1    3
商品数の累積和 X   0    2    3    6

    ボールの数 Y   1    1    3    1
購入数の累積和 Z   0    1    3    4

例えば $i=2$ の箱に $3$ 個のボールが入れられているとする（$Y_2=3$）。
また $i$ 未満の箱の処理で購入された商品の数は $Z_{i-1}$ で表され、$Z_1=1$ だとわかっている。

         index     0    1    2    3
商品数の累積和 X   0    2   [3]   6    Z2 = min(X2, Z1+Y2)
          客数 Y   1    1   [3]   1       = min( 3, 1 + 3)
購入数の累積和 Z   0   [1]   ?            = 3

この時、$Z_i = \min(X_i,Z_{i-1}+Y_i)$ が成り立つ。上記の“?”には $3$ が入ることとなる。
$Z_0=0$ であり、$i=1,...,M$ の順に計算していくことで、$Y$ を固定した時の全体の購入数が求められた。

これを元に、元の問題を解くためのDPを定義する。

$\mathrm{DP}[i,j,k]:=i$ 個目の箱までのボールの入れ方および相対的な番号の付け方を決めて、$j$ 個のボールを入れ $k$ 個の商品が売れている確率

$\mathrm{DP}[i-1,j,k]$ からは、新たに箱 $i$ に入れるボールの数を $l=0,...,N-j$ で決めて、

$\mathrm{DP}[i,j+l,\min(k+l,X_i)]+=\mathrm{DP}[i-1,j,k] \times \left ( \frac{w}{C} \right )^l \times {}_{j+l}C_{l}$

のようにして更新できる。

ただし $w$ は箱が表す区間長を示す。例えば上例の箱 $i=2$ は元の予算に立ち返ると $[5,9)$ の区間を表すので $w=4$ となる。
$ \left ( \frac{w}{C} \right )^l$ は、その箱に $l$ 個のボールが入る確率を表している。

また ${}_{j+l}C_{l}$ は、ボールの番号の付け方も考慮した値とするためにかけている。

最終的に $\mathrm{DP}[M,N,*]$ が答えとなる。

計算量は $O(N^4)$ だが、$j \lt k$ となる $k$ や、$j+l \gt N$ となる $l$ は処理しないという自明な枝刈りをすると、$1/6$ 程度の定数倍がかかるため、間に合う。

Python3

from collections import Counter


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, c, aaa):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    cnt = Counter(aaa)
    aaa = sorted(cnt.keys())
    m = len(aaa)
    bw = [aaa[0] - 1]
    limit = [0]
    for i in range(m - 1):
        bw.append(aaa[i + 1] - aaa[i])
        limit.append(limit[i] + cnt[aaa[i]])
    bw.append(c - aaa[-1] + 1)
    limit.append(limit[-1] + cnt[aaa[-1]])

    # dp[(i),j,k] = i番目までの隙間にj個置いて有効なのがk個である状態の数
    inv_c = pow(c, -1, MOD)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for j in range(n + 1):
        dp[j][0] = pow(bw[0] * inv_c, j, MOD)
    for i in range(m):
        ndp = [[0] * (n + 1) for _ in range(n + 1)]
        p = bw[i + 1] * inv_c % MOD
        for j in range(n + 1):
            for k in range(j + 1):
                for l in range(n - j + 1):
                    av = min(k + l, limit[i + 1])
                    ndp[j + l][av] += dp[j][k] * pow(p, l, MOD) * ncr(j + l, l)
                    ndp[j + l][av] %= MOD
        dp = ndp

    return dp[n]


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

目次

AtCoder Regular Contest 217 A,B,C問題メモ

A - Min of Sum of XOR

問題文

制約

解法

ちゃんと解く

B - Not High Element

問題文

制約

解法

C - Greedy Customers 2

問題文

制約

解法