AtCoder Beginner Contest 216 F,G問題メモ

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])