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

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