Educational DP Contest W,X,Y問題メモ
解法ネタバレ注意
W - Intervals
問題
'0'と'1'からなる $N$ 文字の文字列があるとき、文字列のスコアは以下で決まる- $M$ 個の条件があり、$i$ 番目の条件は $L_i,R_i,A_i$ によって与えられる
- 文字列の左から $L_i$ 文字目～$R_i$ 文字目に
'1'が１つでもあると、スコアに $A_i$ 加算する
- 文字列をうまく選んだ時、スコアの最大値を求めよ
- $1 \le N,M \le 2 \times 10^5$
- $-10^9 \le A_i \le 10^9$
解法
区間加算・区間MAXを必要とするDP。
区間加算と区間MAXを扱う場合は、遅延セグメント木を使う解法をよく見るが、どうも更新、伝播、確定をどのタイミングでどのノードに行えば良いか、こんがらがって苦手。
解法は、以下に解説してくださっている方のを参考に。
データ
$DP[i]=i$ 文字目まで考慮し、$i$ 文字目が'1'だった時の最高スコア（遅延セグメント木で実装）
初期条件
全て0
遷移
$DP[1]～DP[k-1]$ が決まっているとして、$k$ 文字目を'1'にすることについて考える。
パッと考えるのは、$DP[1]～DP[k-1]$ の最大値に、「$k$ 文字目を区間に含んでいる条件」のスコアを足し合わせると $DP[i]$ が求まりそう……。 なのだが、$k-1$ 文字目以前に既に加算していた場合は新たには加算されない。
k=6
1 2 3 4 5 6 7 8
文字列例1 0 0 1 0 0 DP[3] に対して……
条件1 |--------| 加算される
条件2 |-----| 加算される
条件3 |--------------| 既に3文字目で加算済みなので新たには加算されない
条件4 |--| 範囲外
条件5 |--| 範囲外
文字列例2 1 1 1 1 0 DP[4] に対して……
条件1 |--------| 加算される
条件2 |-----| 既に4文字目で加算済みなので新たには加算されない
条件3 |--------------| 既に4文字目で加算済みなので新たには加算されない
条件4,5 略
$k$ 文字目より前で最後に'1'が立った場所により、各条件が加算されたりされなかったりする。
上の例で、$DP[6]$ は、最後に'1'が立った場所を $t$ 文字目とすると、以下のスコアの最大値となる。
- $t \lt 2$ の時、$DP[t]$ に条件1～3のスコアを加算した値
- $2 \le t \lt 4$ の時、$DP[t]$ に条件1、2のスコアを加算した値
- $4 \le t \lt 5$ の時、$DP[t]$ に条件1のスコアを加算した値
- $5 \le t$の時、$DP[t]$（どのスコアも加算されない）
しかし、これを毎回別々に計算していては、間に合わない。
上の場合分けを、各条件を主軸にまとめると、以下のようになる。
- $t \lt 5 (=L_1)$ なら、$DP[t]$ に条件1のスコアを加算
- $t \lt 4 (=L_2)$ なら、$DP[t]$ に条件2のスコアを加算
- $t \lt 2 (=L_3)$ なら、$DP[t]$ に条件3のスコアを加算
足し込む範囲を図化すると、以下のようになる。
1 2 3 4 5 6 7 8 条件1 ********** |--------| * の範囲のDPに A1 を加算 条件2 ******* |-----| * の範囲のDPに A2 を加算 条件3 * |--------------| * の範囲のDPに A3 を加算 DP[6] = MAX( DP[1]+A1+A2+A3, DP[2]+A1+A2, DP[3]+A1+A2, DP[4]+A1, DP[5] )
あらかじめ、DP配列に直接、$k$ を含む各条件のスコアをそれぞれ $1 ～ L_i-1$ の範囲に加算しておいてやる。
すると、$DP[k]$ は、ただ1つの区間MAXクエリ $\max(DP[1]～DP[k-1])$ （DPは加算後の値）で求められるようになる。
個人的に「DP配列で、決定済みの部分の数値がいじられる」ことにちょっと抵抗感があるが、この方法で効率的に更新を行えるのだから仕方ない。
ここで、現在の $k$ を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 つまり、まだ手前だったり、既に通過した条件のスコアが足されていてはいけない。
※ *** ... スコアが加算されている
k=6
1 2 3 4 5 ⑥ 7 8
条件1 ********** |---------|
条件2 ******* |-----|
条件3 * |---------------|
条件5 |--| まだ範囲外
↓
k=7
1 2 3 4 5 6 ⑦ 8
条件1 ********** |---------|
条件2 |-----| 範囲外となったので、もう加算していてはいけない
条件3 * |--------------|
条件5 **************** |---| 範囲内となったので、新たに加算
加算していたのを元に戻すには、同じ範囲に $-A_i$ を加算すればよい。
まとめると、$k$ を1つずつ見て、$DP[k]$ を小さい方から確定させていく過程で、
- $k=L_i$ となる条件があった場合、$DP[1]～DP[k-1]$ にスコア $A_i$ を加算する
- $\max(DP[1]～DP[k-1])$ を求め、$DP[k]$ に加算する。
- $k=R_i$ となる条件があった場合、$DP[1]～DP[L_i-1]$ にスコア $-A_i$ を加算する
以上で、$DP[k]$ の最大値が答え。区間加算するタイミングと、最大値を得るタイミングに注意。
実装
遅延セグメント木はPythonが苦手とする(?)配列参照が多く、普通に実装しても間に合わないことがある。何らかの高速化を試みたい。
ここで、必要なクエリを整理すると、以下の3つのみである。
- Add to [1, k)
- GetMax of [1, k)
- Add to k
Add to kは別として、残りは必ず区間の左端が 1 なので、Add時やGetMax時、配列に加算したり参照する必要のある要素は $k$ によって固定である。
このindexの特定には、Binary Indexed Tree(Fenwick Tree) の概念を利用できる。
たとえば $[1, 7]$ に対する加算なら以下の右図のようにBITで更新されるindexは「4, 6, 7」で、SegmentTreeに対応するのは「2, 6, 14」となるので、これを事前計算して保持しておくと、毎回indexを求める計算を省略できる。
BinaryIndexedTreeの | SegmentTree に対応する位置
更新で訪れられる頂点 |
８ | １
④ | ② ３
２ ⑥ | ４ ５ ⑥ ７
１ ３ ５ ⑦ | ８ ９ 10 11 12 13 ⑭ 15
import sys
class LazySegmentTree:
""" [0, k) Add, [0, k) Max """
# For speeding up index calculation, [data] [lazy] are implemented 1-rooted
# but 'update' and 'get' query requires 0-indexed
def __init__(self, n):
n2 = 1 << n.bit_length()
self.n = n2
self.offset = n2
self.data = [0] * (n2 << 1)
self.lazy = [0] * (n2 << 1)
update_base = [0] * n
propagate_indices = [[] for _ in [0] * n]
update_indices = [[] for _ in [0] * n]
for i in range(n):
j = i + n2 + 1
b = (j >> (j & -j).bit_length() - 1) - 1
update_base[i] = b
while b > 1:
b >>= 1
propagate_indices[i].append(b)
for i in range(n):
k = i + 1
while k:
update_indices[i].append(update_base[k - 1])
k -= k & -k
self.propagate_indices = propagate_indices
self.update_indices = update_indices
def _push(self, k):
for i in reversed(self.propagate_indices[k]):
v = self.lazy[i]
if v == 0:
continue
j = i << 1
self.data[j] += v
self.data[j + 1] += v
self.lazy[j] += v
self.lazy[j + 1] += v
self.lazy[i] = 0
# [0, k)
def add(self, k, x):
for i in self.update_indices[k]:
self.data[i] += x
self.lazy[i] += x
for i in self.propagate_indices[k]:
self.data[i] = max(self.data[i * 2], self.data[i * 2 + 1]) + self.lazy[i]
# [0, k)
def get(self, k):
self._push(k)
ret = max(map(self.data.__getitem__, self.update_indices[k]))
# This addition is specific for the problem.
i = k + self.offset + 1
self.data[i] += ret
tmp = self.data[i]
while i > 1:
parent = i >> 1
sibling = i ^ 1
tmp = self.data[parent] = max(tmp, self.data[sibling]) + self.lazy[parent]
i = parent
return ret
n, m = map(int, input().split())
range_ls = [0 for _ in [0] * n]
range_rs = [[] for _ in [0] * n]
for line in sys.stdin.readlines():
l, r, a = map(int, line.split())
range_ls[l - 1] += a
range_rs[r - 1].append((l - 1, a))
lst = LazySegmentTree(n)
ans = 0
for i, (la, rs) in enumerate(zip(range_ls, range_rs)):
if la != 0:
lst.add(i, la)
ans = max(ans, lst.get(i))
for l, a in rs:
lst.add(l, -a)
print(ans)
X - Tower
問題
- $N$ 個のブロックのそれぞれに 重さ $w_i$, 丈夫さ $s_i$, 価値 $v_i$ が決まっている
- 何個かのブロックを一列に積み重ね、タワーを作る
- タワーを構成するブロックは、以下のルールを満たす
- 自分より上に乗っているブロックの重さの和 ≦ 自分の丈夫さ
- 用いるブロックの価値の総和を最大化せよ
- $1 \le N \le 10^3$
- $1 \le w_i,s_i \le 10^4$
- $1 \le v_i \le 10^9$
解法
優先順位付きナップサック問題。
自分より上のブロックの重さは丈夫さに関わるため、実際のタワーのように下から積み上げるのではなく、上から決めていく。
データ
$DP[i][j]=i$ 番目のブロックまで考慮し、重さ合計が $j$ の時の最大価値
初期条件
$DP[0][0]=0$
他は、重さ $j$ が実現可能/不可能であることが区別できるよう、-1など正しい重さになり得ない値で埋めておく
優先順位
遷移の前に、優先順位を求める。 重たいブロックを上に積むのは非効率なので、優先的に積んだ方がよいブロックの順序があると予測する。
ある2つのブロック $i,j$ があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を $X$ とする。
$i$ を上にすると両方積めるが、$j$ が上だと積めなくなる場合があったとすると、次が同時に成立しているはずである。
- $X+w_i \le s_j$
- $X+w_j \gt s_i$
これを移項してXを消去すると、$s_i+w_i \lt s_j+w_j$ となる。重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。
遷移
あとは普通のナップサックDP。
重さと丈夫さの上限が $10^4$ なので、考慮すべき重さの総計は多くとも $2 \times 10^4$ まででよい。 （$w_i=10^4,s_i=10^4$ のブロックに、重さの合計が $10^4$ のタワーを乗せた場合が、タワー全体の重さの取り得る最大値）
import sys
n = int(input())
blocks = []
for line in sys.stdin.readlines():
w, s, v = map(int, line.split())
blocks.append((w + s, w, s, v))
blocks.sort()
dp = [-1] * 20001
dp[0] = 0
for _, w, s, v in blocks:
for i in range(s, -1, -1):
if dp[i] == -1:
continue
dp[i + w] = max(dp[i + w], dp[i] + v)
print(max(dp))
Y - Grid 2
問題
- 縦 $H$ 行、横 $W$ 列のグリッド
- 各マスは、「空マス」「壁マス」のいずれか
- 壁マスは $N$ 個あり、$i$ 番目の壁マスの座標は $(r_i, c_i)$
- 左上 $(1,1)$ から右下 $(H,W)$ まで、隣り合う下または右の空マスへの移動を繰り返す
- 壁マスは通れない
- $(H,W)$までの経路数を $\mod{10^9+7}$ で求めよ
- $2 \le H,W \le 10^5$
- $1 \le N \le 3000$
解法
H - Grid 1 と似たような問題だが、$H,W$ の上限が大幅に増えているので1マスずつ求めるのは無理。
こういう、序盤の敵がアレンジされて強くなって終盤に出てくるのって、RPG的でいいよね。
方針
$N$ の制約がそこまで多くないので、包除原理DPを行う。
壁マスでも通過できるとして、“少なくとも $k$ 個の壁マスを通過した” 経路のパターン数を $f(k)$ とすると、包除原理より
答え$=f(0)-f(1)+f(2)-f(3)+ ... = (k$ が偶数の時の総和$)-(k$ が奇数の時の総和$)$ となる。
“少なくとも”の表現がややわかりづらい。
Ｓ・・・・・・・ ・・・❷・・・・ ・❶・・・・・・ ・・・・・❸・・ ・・・・・・・Ｇ
●が壁マスとして、
- $f(0)$: Ｓ→Ｇの経路数
- 途中で壁を通ったかどうかは関係ない
- $f(1)$: Ｓ→❶→Ｇの経路数＋（❷、❸について同様の経路数）
- たとえば❶を経由した後、❸を通ったかどうかは関係ない
- $f(2)$: Ｓ→❶→❸→Ｇの経路数 ＋ Ｓ→❷→❸→Ｇの経路数
- 3つの壁マスを通過することはできないので、ここまで
この「他の●を通ったかどうかは関係ない」というところが、経路数の計算を単純明快にしてくれる。
下に $x$ マス、右に $y$ マス移動する経路数は、合計 $x+y$ 回の移動から下移動に当てはまる $x$ 回の移動の選び方になるので、${}_{x+y}C_{x}$ 通りと計算できる。
それを踏まえて、必要なDPを考える。
データ
$DP[i][j]=$ Ｓマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め $j=[0:偶数,1:奇数]$ 個の場合の経路数
さらに、最終的に必要なのは通過した壁マスが（偶数個）-（奇数個）の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える（＝分配法則が成り立つ）ので、以下のようにするとより省計算量・省メモリになる。
$DP[i]=$ Ｓマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め(偶数個の場合の経路数)-(奇数個の場合の経路数)
初期条件
DP[0]=1
遷移
$(r, c)$ の小さい順に壁マスをソートすると、通過する可能性順になる。 つまり、右か下に移動する特性上、ソート順で後→前の順番で通過することはできない。
これにより、$i$ 番目の壁マスを考えるとき、$DP[1]～DP[i-1]$ については確定していることを保証できる。
$i$ 番目の壁マスを考える。Ｓマスと $1～i-1$ 番目の壁マスの、それぞれからの$i$ 番目の壁への経路数を求める。
$j$ 番目の壁マス$(j \lt i)$から $i$ 番目の壁マスへの移動パターン数 $p_{j,i}$ は、ソートで $r_j \le r_i$ であることは保証されているので、
- $c_j \gt c_i$ の時、$p_{j,i}=0$
- $c_j \le c_i$ の時、$p_{j,i}={}_{dx+dy}C_{dx}$で求められる経路数
計算の便宜上、Ｓマスも“0番目の壁マス”と見做すとして、以下で遷移できる。
$\displaystyle DP[i] = \sum_{k=0}^{i-1}(-DP[k] \times p_{k,i})$
DP[k] では（偶数個）-（奇数個）の値だったものが、遷移すると $i$ 番目の壁マスを踏むことによって一律1個ずつ増えて（奇数個）-（偶数個）を示す値になるので、更新時に正負逆転させておくのが重要。
計算の便宜上、Ｇマスも“N+1番目の壁マス”と見做して同様に計算すると、答えは $-DP[N+1]$ となる。 （本来は壁マスでないＧマスを壁マスとして計算しているため、DP上では正負逆転した値となっている）
c++ の場合は負数%正数が負になるので注意。Pythonでは正となるので、そのまま出力できる。
import sys
def prepare(n):
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
inv = [1] * (n + 1)
inv[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n - 1, 0, -1):
inv[i] = inv[i + 1] * (i + 1) % MOD
return fact, inv
MOD = 10 ** 9 + 7
h, w, n = map(int, input().split())
walls = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
walls.append((1, 1))
walls.append((h, w))
walls.sort()
fact, inv = prepare(h + w)
dp = [1]
for i, (cy, cx) in enumerate(walls[1:], start=1):
res = 0
for j, (py, px) in enumerate(walls[:i]):
if cx < px:
continue
dy, dx = cy - py, cx - px
res -= dp[j] * fact[dy + dx] % MOD * inv[dy] % MOD * inv[dx] % MOD
res %= MOD
dp.append(res)
print(-dp[-1] % MOD)
