AtCoder Regular Contest 223 A,B,C,D問題メモ

AtCoder Regular Contest 223

A - Unusual-Constraint Knapsack

問題文

$N$ 個の荷物 $1,2,\dots,N$ があります。荷物 $i$ は重さが $w_i$ で、価値が $v_i$ です。
$i=2,3,\dots,N$ について、以下が成り立っています。
- $\sum_{j=1}^{i-1}{w_j}\lt w_i$
重さの合計が $W$ 以下になるようにいくつか（$0$ 個でもよい）の荷物を選びます。
選んだ荷物の価値の合計としてあり得る値の最大値を求めてください。

$1$ つの入力につき、$T$ 個のテストケースを解いてください。

制約

$1 \leq T \leq 2 \times 10^5$
$1 \leq N \leq 60$
$1 \leq w_i \leq W \leq 10^{18}$
$\sum_{j=1}^{i-1}{w_j}\lt w_i \; (2 \leq i \leq N)$
$1 \leq v_i \leq 10^{16}$
すべてのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
入力される値はすべて整数

解法

荷物の重さに特徴があるナップサック。荷物 $i$ は、$i-1$ 以下の荷物全部の総和より重い。

重い荷物から、採用する/しないを場合分けしていく。現在の残容量を $R$ とする。

残容量が足りない場合（$R \lt w_i$）
- 当然、採用できない。$i-1$ へ。
残容量が足りる場合、以下の価値の高い方
- 採用する場合、採用して $i-1$ へ。
- 採用しない場合、$i-1$ 以下の全ての荷物は採用できる。$i-1$ 以下で採用できる価値は $\sum_{j=1}^{i-1}v_j$ 確定。

要は、「重い方から貪欲」のアプローチから外れた瞬間、それ以下の最適解が確定する。
貪欲に採用しつつ、「どこで外れるか」（最後まで外れないか）を $O(N)$ 通り試せばよい。

Python3

from itertools import accumulate


def solve(n, limit, items):
    memo = {}
    acc = [0] + list(accumulate(v for w, v in items))

    def sub(i, limit):
        if i < 0:
            return 0
        if (i, limit) in memo:
            return memo[i, limit]
        w, v = items[i]
        if limit >= w * 2 - 1:
            result = v + sub(i - 1, limit - w)
            memo[i, limit] = result
            return result
        if limit < w:
            result = sub(i - 1, limit)
            memo[i, limit] = result
            return result
        if acc[i] <= v:
            result = v + sub(i - 1, limit - w)
            memo[i, limit] = result
            return result

        res1 = sub(i - 1, limit)
        res2 = v + sub(i - 1, limit - w)
        result = max(res1, res2)
        memo[i, limit] = result
        return result

    ans = sub(n - 1, limit)
    return ans


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

B - Valid Arrays by K-Divisible Swaps

問題文

長さ $N$ の整数列 $A$ と正整数 $K$ が与えられます。$A$ に対して、以下の操作を何回でも行うことができます。
- $A_i+A_{i+1}$ が $K$ で割り切れるような $1$ 以上 $N-1$ 以下の整数 $i$ を選び、$A_i$ と $A_{i+1}$ を入れ替える。
操作を $0$ 回以上行った後の $A$ としてあり得る数列の総数を $998244353$ で割った余りを求めてください。

$1$ つの入力につき、$T$ 個のテストケースを解いてください。

制約

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

解法

ひとまず、どのような移動が可能か考えるため、$B_i=A_i \bmod{K}$ として、$B$ で考える。（最終的な数列の総数を出すときは、元の $A_i$ で考える必要がある）

例えば以下を考えたとき、$(0,)(4,)(1,7),(2,6),(3,5)$ の各グループの要素が連続するそれぞれの中では入れ替えられる。
ただし、異なるグループが隣り合う箇所では、どうやっても入れ替えられない。

K=8
B  2 2 6 6 2 6|3 5 5 3|1 7 1 7|0 0 0 0|4 4 4

$B_i=0$ または $\frac{K}{2}$ の場合
- 自由に並べ替えられる。
- 1つの連続の中で、$A_i=8$ が $c_1$ 個、$16$ が $c_2$ 個、、、出現する場合、$\dfrac{(区間長)!}{c_1!c_2!...}$ 通り
それ以外の場合
- 例えば $(2,6)$ の連続において入れ替えられるのは「$2$ と $6$」であり、$2$ 同士、$6$ 同士は入れ替え不可。
- よって、一方が $c$ 個、もう一方が $d$ 個出現する場合、$\dbinom{c+d}{c}$ 通り

各連続に付き、これらの総積が答えとなる。

Python3

from collections import defaultdict


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, k, aaa):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def calc1(cur_pos, cur_neg):
        if cur_pos == 0 or cur_neg == 0:
            return 1
        result = facts[cur_pos + cur_neg] * finvs[cur_pos] % MOD * finvs[cur_neg] % MOD
        return result

    def calc2(values):
        result = 1
        total = 0
        for c in values.values():
            result *= finvs[c]
            result %= MOD
            total += c
        result *= facts[total]
        result %= MOD
        return result

    cur_values = defaultdict(int)
    cur_pos = 0
    cur_neg = 0
    ans = 1
    key = -1
    for a in aaa:
        d = a % k
        x = min(d, k - d)
        if key != x:
            if key == 0 or key * 2 == k:
                ans *= calc2(cur_values)
                ans %= MOD
                cur_values.clear()
            else:
                ans *= calc1(cur_pos, cur_neg)
                ans %= MOD
                cur_pos = 0
                cur_neg = 0
            key = x
        if key == 0 or key * 2 == k:
            cur_values[a] += 1
        else:
            if key == d:
                cur_pos += 1
            else:
                cur_neg += 1
    if key == 0 or key * 2 == k:
        ans *= calc2(cur_values)
        ans %= MOD
    else:
        ans *= calc1(cur_pos, cur_neg)
        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 - Whole Product of Pairwise Distances

問題文

$N$ 個の正整数からなる数列 $A$ が与えられます。
$\prod_{1 \leq i \lt j \leq N}|A_i-A_j|$ を $N$ で割った余りを求めてください。

$1$ つの入力につき、$T$ 個のテストケースを解いてください。

制約

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

解法

まず、総積なので、1つでも $0$ があると $0$。
つまり答えが $0$ でない場合、$A_i \bmod{N}$ には $0,1,...,N-1$ が1つずつ出現することになる。

$A$ は並べ替えても答えに影響しないので、$\bmod{N}$ が $0,1,...,N-1$ の順になるように並べ替える。

N = 8
A     16  9 26 11  4 29 14  7
modN   0  1  2  3  4  5  6  7

この時、$i$ と $i+d$ に対し、$A_i \lt A_{i+d}$ なら $d$ だけ答えに寄与し、 $A_i \gt A_{i+d}$ なら $-d \bmod{N}$ だけ答えに寄与することになる。

これはまさに、順序が入れ替わっているペア数＝$A$ の転倒数が関わっていることになる。

差が $d$ のペアは $N-d$ 個ある。これらを全て掛け合わせた $\displaystyle \prod_{d=1}^{N-1}d^{N-d}$ をベースとして、転倒数が偶数ならそのまま。奇数なら $-1$ をかけたものが答えとなる。

Python3

from atcoder.fenwicktree import FenwickTree


def solve(n, aaa):
    appeared = set()
    fwt = FenwickTree(n)
    inv = 0
    aaa = sorted(aaa)
    for i in range(n):
        a = aaa[i]
        m = a % n
        if m in appeared:
            return 0
        appeared.add(m)
        inv += fwt.sum(m, n)
        fwt.add(m, 1)

    ans = 1
    for d in range(2, n):
        ans *= pow(d, n - d, n)
        ans %= n

    # print(f'{inv=}')
    if n % 2 == 1 and inv % 2 == 1:
        ans = (-ans) % n

    return ans


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

D - Xpectation of Cards in Hand with Laboratory

問題文

ドローカード $A$ 枚と普通のカード $B$ 枚があります。
これら $A+B$ 枚のカードからなる順列は $(A+B)!$ 通りありますが、そのうちの $1$ つを一様ランダムに選び、その順番に上下に積み重ねて山札とします。そして山札の上から $K$ 枚を引き、手札にします。
手札にドローカードが $1$ 枚以上ある限り、以下の操作を繰り返します。
- 手札にあるドローカードを $1$ 枚捨てる。捨てたカードは手札からなくなり、山札にも戻らない。
- 山札にあるカードの枚数を $c$ として、山札の上から $\min(c,2)$ 枚のカードを手札に加える。
最終的な手札のカード枚数の期待値を $\text{mod } 998244353$ で求めてください。

$1$ つの入力につき、$T$ 個のテストケースを解いてください。

制約

$1 \leq T \leq 10^5$
$1 \leq A,B$
$1 \leq K \leq A+B \leq 10^7$
すべてのテストケースにおける $A+B$ の総和は $10^7$ 以下
入力される値はすべて整数

解法

最初に $K$ 枚を一度に引くという設定だが、これは “ドロー権” $d$（あと何枚ドローできるか）が最初 $K$ あるとして、ドロー権がある限り1枚ずつ引くと考えてもよい。

そうすると、途中で引いたドローカードも「ドロー権を増やす」という作用で、最初の $K$ 枚と同一視できて考えやすくなる。

ドローカードを引くと、$d$ を $1$ 消費して $2$ 得る（差し引き $+1$）。スコアは変わらない。
普通のカードを引くと、$d$ を $1$ 消費し、スコアを $+1$ 得る。

あるカードの並びを先頭から見ていき、$d=0$ になるか、スコアが $B$ になったら、その時点のスコアが、そのカードの並びに対する結果である。

また、「スコアが $B$ になったら」の条件は、 $d \ge 普通カード残数$ となったら残り全ての普通カードは必ず引くことができるので、その時点で打ち切って良い。（ドローカードを引くことで $d$ は減らないので）

つまり、初期状態で $B \le K$ の場合、答えは $B$ である。以下、$B \gt K$ の場合を考える。

グリッド状の経路数え上げに言い換える。

$(0,0)$ から右か上のみの移動を繰り返し、$(A,B)$ まで行く。
- ドローカードを引くと→、普通のカードを引くと↑に移動することに対応させる。
$y=x+K$ の直線を最初に踏むと、スコアは（踏んだ時点の）$y$ に確定する。
$x=B-K$ の直線を最初に踏むと、スコアは $B$ に確定する。
- ※$(A,B)$ まででいずれかの直線には必ず触れる。

  ↑    ／|
  │  ／  |
K │／    |
  │      |
  │      |
  ┼─────→
         B-K

$P_i:=$「$x=i$ ではじめて斜線上の点 $(i,i+K)$ を踏むような経路数」とする。
これは、$C_i:=$「斜線を踏まずに $(i,i+K-1)$ に行く経路数」として、

$\displaystyle C_i = \frac{K}{2i+K} \binom{2i+K}{i}$
$\displaystyle P_i = C_i \times \binom{A+B-2i-K}{A-i}$

と計算できる。$C_i$ は、反射原理を使って求められる。

これを $i$ 毎に計算する。いずれでもない残った経路は $x=B-K$ を踏むことになり、スコアは $B$ で確定する。

よって、$L = \min(A,B-K-1)$ として、以下が答えとなる。

$\displaystyle \frac{\sum_{i=0}^{L}P_i(i+K) + B \times (\binom{A+B}{A} - \sum_{i=0}^{L}P_i)}{\binom{A+B}{A}}$

Python3

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(queries):
    MOD = 998244353
    facts, finvs = precompute_factorials(2 * 10 ** 7, MOD)

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

    buf = []
    for a, b, k in queries:
        if b <= k:
            buf.append(b)
            continue
        ans = 0
        rem_p = ncr(a + b, a)
        for x in range(min(a + 1, b - k)):
            p = k * facts[2 * x + k - 1] % MOD * finvs[x] % MOD * finvs[x + k] % MOD
            p *= ncr(a + b - x * 2 - k, a - x)
            p %= MOD
            rem_p -= p
            rem_p %= MOD
            ans += (x + k) * p
            ans %= MOD
        ans += rem_p * b
        ans %= MOD
        ans *= facts[a] * facts[b] % MOD * finvs[a + b] % MOD
        ans %= MOD
        buf.append(ans)

    return buf


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

目次

AtCoder Regular Contest 223 A,B,C,D問題メモ

A - Unusual-Constraint Knapsack

問題文

制約

解法

B - Valid Arrays by K-Divisible Swaps

問題文

制約

解法

C - Whole Product of Pairwise Distances

問題文

制約

解法

D - Xpectation of Cards in Hand with Laboratory

問題文

制約

解法