AtCoder Beginner Contest 216 F,G,H問題メモ

AtCoder Beginner Contest 216

F - Max Sum Counting

問題

（※表現しやすさのため、問題設定を一部改変）
$N$ 人の人がいて、$i$ 番目の人は $A_i$ リットルまで入る水筒と、水 $B_i$ リットルを持っている
$N$ 人から1人以上を選ぶ方法は $2^N-1$ 通りあるが、そのうち、以下の条件を満たす方法の個数を求めよ
条件
- 選んだ人が持つ中で最も大きい水筒1本に、選んだ人が持っている全ての水が入る
- つまり、選んだ人の集合を $S$ として、$\max_{i \in S} A_i \ge \sum_{i \in S} B_i$
$1 \le N \le 5000$
$1 \le A_i,B_i \le 5000$

解法

順番が大事なナップサックDP。

大枠の方針

選ばれた中で $A_i$ が最大値となる人 $m$ を固定すると、他は $A_m \ge A_i$ となるような人 $i$ しか選べない。

人 $m$ を選んだ時点で水 $B_m$ リットルは付いてくるので、残容量は $A_m-B_m$ リットル。
$m$ 以外で選ぶ人たちが持つ水 $B_i$ の総和がこれを超えてはいけない。

従って、$A_m \ge A_i$ となる $i$ から選ぶ選び方で、その $B_i$ の和が $A_m-B_m$ 以下となる選び方が、 $m$ を固定したときの答えとなる。

i   0  1  2  3  4    m=2 (Am=6) を固定すると、それよりAiの大きい i=0 は使えない。
A   9  2  6  5  3    その他から、Bi の和が Am-Bm = 6-4 = 2 を超えないように選ぶ。
B   3  1  4  1  5    iの組が {選ばない}, {1}, {3}, {1,3} の4通りが条件を満たす。

これを各 $m$ について足し合わせればよい。

求める順番

$B_1,B_2,...$ から和が $X=0,1,2,...$ となるような選び方は何通りあるか？は、DPの典型・ナップサック問題で求まる。

$DP[i][X]=i$ 番目の人まで考慮して、その和が $X$ となるような選び方のパターン数

$A_i$ の最大制約が $5000$ なので、ナップサックの上限もここまでを考えればよく、1回のナップサックは $O(N A_{max})$ で求まる。

しかし、毎回「$m$ を固定」→「$A_m \ge A_i$ となる $i$ を調べる」→「そのような $B_i$ だけを使ってナップサック」としていては間に合わない。

ここで、$A_i$ が小さい方から順に $i$ をソートし、番号を振りなおす。
答えに $A$ の初期の並び順は影響しないので、ソートしても問題ない。

すると、最大値を $A_m$ と固定した時にナップサックで使える $i$ の集合と、 $A_{m+1}$ とした時に使える $i$ の集合はほぼ同じとなり、前者に $m$ を加えたものが後者となる。

$i$ の昇順に処理すれば、$m$ について求める際に使ったナップサックの結果に、 $B_m$ を新たな1アイテムとして加えることで、$m+1$ について求める際に使い回すことができる。

i   0  1  2  3  4
A   2  3  5  6  9
B   1  5  1  4  3

i=0      X  0 1 2 3 4 5 6 ...    A0-B0 = 1 以下となるのは 1通り
パターン数  1 0 0 0 0 0 0 ...
   
↓B0=1 を反映

i=1      X  0 1 2 3 4 5 6 ...    A1-B1 = -2 以下となるのは 0通り
パターン数  1 1 0 0 0 0 0 ...

↓B1=5 を反映

i=2      X  0 1 2 3 4 5 6 ...    A2-B2 = 4 以下となるのは 2通り
パターン数  1 1 0 0 0 1 1 ...

↓B2=1 を反映

i=3      X  0 1 2 3 4 5 6 7 ...  A3-B3 = 2 以下となるのは 4通り
パターン数  1 2 1 0 0 1 2 1 ...
↓
...

これで、全体で $O(N A_{max})$ で求められるようになった。

なお、DPの初期値を 1 0 0 0 … とすると「ちょうど $X$ となるパターン数」が求まるが、 1 1 1 1 … から始めると「$X$ 以下となるパターン数」が求まるので、今回の場合はそちらの方がより高速になる。

Python3

import numpy as np

n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
MOD = 998244353

ab = list(zip(aaa, bbb))
ab.sort()
ma = ab[-1][0]

dp = np.ones(ma + 1, np.int64)
ans = 0

for a, b in ab:
    r = a - b
    if r >= 0:
        ans += dp[r]
        ans %= MOD

    if b <= ma:
        dp[b:] += dp[:-b]
        dp %= MOD

print(ans)

G - 01Sequence

問題

'0' と '1' のみからなる長さ $N$ の数列のうち、以下に示される $M$ 個の条件を満たすものを考える
条件
- $i$ 番目の条件は、$L_i,R_i,X_i$ で与えられる
- $A_{L_i}, A_{L_i+1},...,A_{R_i}$ に、'1' が $X_i$ 個以上含まれなければならない
そのような数列で、'1' の個数が最小となるものを1つ構築せよ
$1 \le N \le 2 \times 10^5$
$1 \le M \le 2 \times 10^5$
区間の長さより $X_i$ が大きいような条件は与えられない

解法

'1' をなるべく多くの条件で使い回せばよさそう。

暫定の答えを長さ $N$ の '0' の数列とし、ここに '1' を立てていくことにする。

区間スケジューリング問題のように、条件を $R_i$ の小さい順に見ていく。

$L_i～R_i$ 間に暫定で '1' が何個あるかは、Fenwick Treeなどで管理していれば $O(\log{N})$ で求められる。

既に $X_i$ 個以上あれば、その条件はもうクリアしている。

足りない場合は、不足分の '1' を $L_i～R_i$ 内に新たに決めないといけないのだが、ここで他の条件ともなるべく被らせたいことを考えると、$R_i,R_i-1,R_i-2,...$ と右端から遡るように埋めていって損しないことがわかる。

      Li            Ri
... 0 0 1 0 0 1 1 0 0 0 ...
     |---------------|        たとえばこの間に6個の'1'が必要とすると3個足りない
            v     v v
... 0 0 1 0 1 1 1 1 1 0 ...   こう埋めるのがいい

      v   v       v
... 0 1 1 1 0 1 1 1 0 0 ...   右端から詰めずに埋めてしまうと
               |-------|      次にこのような条件が来たとき、'1' の数を損する。
               
   |-------------------|      損しないこともあるが、Riを昇順に処理している以上、
                              今後、Li に近い方を含むような条件はRi に近い箇所も含んでいるので、
                              右端から詰めないで得することはない

なのでこの通りに貪欲に'1'を立てていくとよい。

新たに'1'を建てたい $i$ は、スタックで管理するか、または「$i$ より左で次に'0'である場所」を更新していくと求められる。

Python3

from operator import add, itemgetter


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


n, m = map(int, input().split())
ranges = [tuple(map(int, input().split())) for _ in range(m)]
ranges.sort(key=itemgetter(1))

next_left = list(range(-1, n + 1))

fwt = FenwickTreeInjectable(n + 1, int, add)
ans = [0] * (n + 2)

for l, r, x in ranges:
    already = fwt.sum(r) - fwt.sum(l - 1)
    if already >= x:
        continue

    i = r
    for _ in range(x - already):
        while ans[i] == 1:
            i = next_left[i]
        fwt.add(i, 1)
        ans[i] = 1
        i = next_left[i]
    next_left[r] = i

print(*ans[1:n + 1])

H - Random Robots

問題文

数直線上に $K$ 個のロボットが置かれています。$i \, (1 \leq i \leq K)$ 番目のロボットははじめ、座標 $x_i$ に存在します。
これから以下の操作をちょうど $N$ 回行います。
- $K$ 個のロボットそれぞれについて、「進む」か「止まる」かを確率 $\frac{1}{2}$ で決める。
  - 「進む」と決めたロボットたちは同時に正の方向に $1$ 進む。
  - 「止まる」と決めたロボットたちはその場から動かない。
- ただし、すべての確率的な決定は独立であるとします。

一連の操作の中で、複数のロボットが出会う、すなわち $2$ 個以上のロボットが同時に同じ座標に存在する、という事象が一度も起こらない確率を$\mod 998244353$ で求めてください。

制約

$2 \leq K \leq 10$
$1 \leq N \leq 1000$
$0 \leq x_1 \lt x_2 \lt \cdots \lt x_K \leq 1000$
入力は全て整数

解法

発想の元となる公式

LGV 公式（Lindström–Gessel–Viennot）の考え方を使う。

解説 - AtCoder Beginner Contest 216

DAG（有向非巡回グラフ）がある。
始点 $n$ 個 $A_1,...,A_n$ と終点 $n$ 個 $B_1,...,B_n$ が指定されている。
各始点から、終点のいずれかを結ぶ $n$ 本のパスを考える。
- 複数の始点が同じ終点を共有することは考えないので、終点の対応付け方は $n!$ 通り
- 対応付けを置換（順列）$P$ で表し、始点 $A_i$ と終点 $B_{P_i}$ を対応づけたとする。
前提条件
- $P \neq (1,2,...,N)$ の場合、必ず交差するパスが存在する（2本のパスが同じ頂点を共有する）。
主張
- $n \times n$ 行列 $M$ の各要素を以下で定義する。
  - $m_{i,j}=A_i$ から $B_j$ への経路数
- $n$ 本のパスの組であって、交差が存在しないものの個数は、$\text{det}(M)$ である。

かなり前提条件が厳しめに見えるが、平面グラフなどでは満たしやすい性質と言える。
今回の問題でも、時系列毎に頂点を作るとそのグラフは条件を満たす。

t   A1          A2      A3
 0  ○          ○      ○
    ↓↘        ↓↘    ↓↘
 1  ○  ○      ○  ○  ○  ○
    ↓↘↓↘    ↓↘↓↘↓↘↓↘
 2  ○  ○  ○  ○  ○  ○  ○  ○
    ↓↘↓↘↓↘↓↘↓↘↓↘↓↘↓↘
 3  ○  ○  ○  ○  ○  ○  ○  ○  ○
 :
    ↓↘↓↘↓↘↓↘↓↘↓↘↓↘↓↘↓ ...
 N  ○  ○  ○  ○  ○  ○  ○  ○  ○ ...
                B1          B2  B3        （終点の一例）

この証明は、ざっくり言うと、

主なアイデア: 対称性を利用した打ち消しあい
- ある $n$ 本のパスの組 $X$ の中で、パス $p,q$ が交差していたとする。
  - $p,q$ が最初に共有する頂点を $v$ とする。
- $p,q$ の $v$ 以降の経路をまるっと入れ替えたパスの組を $X'$ とする。
  - $X'$ も、あり得るパスの組の1つであり、交差が発生している。
- このような2つの組を互いに打ち消し合えたら、交差しないもののみが残る。
置換の偶奇
- 置換は、その転倒数の偶奇により、“偶置換”と“奇置換”に分かれる。
- 始点と終点の対応関係を示す置換 $P$ に着目する。
  - 上記の $X$ と $X'$ で、それぞれの置換は、$p,q$ に対応する2要素だけがswapされたものとなる。
  - ある2要素をswapした順列の転倒数は、必ず偶奇が切り替わる。
行列式の定義
- 行列式は、そもそもの定義が置換とその偶奇に深く関わっている。
  - $\displaystyle \text{det}M=\sum_{P \in T} \text{sgn}(P) \prod_{i} m_{i,P_i}$
    - $T$ は $1～n$ の順列全ての集合
    - $\text{sgn}(P)$ は、$P$ が偶置換なら $+1$、奇置換なら $-1$ となる関数
  - $\prod_{i} m_{i,P_i}$ は、ここでは、対応関係 $P$ を決めたときの、交差する/しないに関わらない $n$ 本のパスとしてあり得る総数

これより、$X$ が交差するパスを持っていた場合、必ず偶奇で打ち消しが発生し、交差しないもののみが行列式の値として残る。

この公式を直接使って解くとしたら、終点を $K$ 点、決めなければならない。
だが、終点の候補となる座標の個数は $\max(x)+N \simeq 2000$ ほどあるので、決め打ち方を全探索なんてすると当然、TLEとなる。

さらに、行列式の計算にも $O(K^3)$ かかる。

LGV公式の発想を元として、もう少し工夫が必要となる。

DPによる高速化

具体的な終点を決めず、置換 $P$ が同じとなる場合をまとめて考えてみる。

つまり、ロボット $1,2,...,K$ の最終的な並びが、同じ位置になるロボットは無く $(P_1,P_2,...,P_K)$ の順になっているような確率を考える。

この確率を $E(P)$ とすると、先ほどの行列式と同じ理屈から、答えは以下となる。

$\displaystyle \sum_{P \in T} \text{sgn}(P) E(P)$

$|T| = K! \simeq 3.6 \times 10^6$ なので、もし $P$ を固定した時の $E(P)$ を $O(K)$ 程度で求める方法が仮にあればこれで考察完了なのだが、、、

どうもそう簡単には求められない。

一応、以下の方法で、$O(K(\max(x)+N))$ では可能である。$\max(x)+N$ は、いずれかのロボットの終点となり得る座標の個数を表す。

$\mathrm{DP}_{仮}[i,j]:=$ 座標 $i$ までで、ロボット $P_1,...,P_j$ の終点座標が既に決まっているような確率

これだとまだ、全ての $P$ に対して求めていたらTLEだが、順列 $P$ を部分的に決めていきながら、全ての $P$ についてまとめておこなう。

$\mathrm{DP}[i,S]:=$
- 座標 $i$ までで、
- 集合 $S$ に含まれるロボットの終点座標が既に決まっているような状態のうち、
- 部分的な置換 $P_1,...,P_|S|$ の転倒数が「偶数であるものの確率」-「奇数であるものの確率」

$\mathrm{DP}[0,\phi]=1$ とする。

いま、座標 $i$ をロボット $k$ の終点座標として新たに定めることを考えると、

ロボット $k$ についてそこが終点となる確率: $N$ 回中、$i-x_k$ 回を右に動いた確率
- $E_{i,k}={}_NC_{i-x_k} \times \dfrac{1}{2^{N}}$
$S$ にある、$k$ より大きな番号のロボットの個数の偶奇
- 偶数なら $s=1$、奇数なら $s=-1$

として、次のように遷移できる。

$\mathrm{DP}[i,S \cup \{k\}] += s \times \mathrm{DP}[i-1,S] \times E_{i,k}$

これで、$O(2^KK(\max(x)+N))$ で求められる。

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(k, n, xxx):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)
    ncr_n = [facts[n] * finvs[i] * finvs[n - i] % MOD for i in range(n + 1)]

    full_bit = (1 << k) - 1
    upper_mask = []
    for i in range(k):
        upper_mask.append((full_bit << (i + 1)) & full_bit)

    s = xxx[0]
    t = xxx[-1] + n
    dp = [0] * (1 << k)
    dp[0] = 1
    for y in range(s, t + 1):
        for bitset in range(full_bit - 1, -1, -1):
            if dp[bitset] == 0:
                continue
            for i in range(k):
                if bitset & (1 << i) != 0:
                    continue
                if not (xxx[i] <= y <= xxx[i] + n):
                    continue
                is_odd = (bitset & upper_mask[i]).bit_count() % 2
                if is_odd:
                    dp[bitset | (1 << i)] -= dp[bitset] * ncr_n[y - xxx[i]]
                else:
                    dp[bitset | (1 << i)] += dp[bitset] * ncr_n[y - xxx[i]]
                dp[bitset | (1 << i)] %= MOD

    ans = dp[full_bit] * pow(2, -k * n, MOD) % MOD
    return ans


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

目次

AtCoder Beginner Contest 216 F,G,H問題メモ

F - Max Sum Counting

問題

解法

大枠の方針

求める順番

G - 01Sequence

問題

解法

H - Random Robots

問題文

制約

解法

発想の元となる公式

DPによる高速化