目次
全国統一プログラミング王決定戦本戦 A～E問題メモ
A - Abundant Resources
問題
- $N$ 要素の数列 $A_1,A_2,...,A_N$
- $1～N$ のそれぞれについて（$K$ とする）以下を求めよ
- 「連続する $K$ 個の要素の和」の最大値
解法
まず $A$ について累積和をとる。これを $Acc$ とする。
連続する $K$ 要素の和は、$Acc$ から、$Acc$ を $K$ 要素ずらした配列を引くと求まる。
A 10 20 30 40 50
Acc 0 10 30 60 100 150
K=3 0 10 30 60 100 150
- 0 10 30
= 60 90 120 → 最大値は120
import numpy as np
n = int(input())
aaa = np.fromiter(map(int, input().split()), dtype=np.int64)
aaa = np.insert(aaa, 0, 0)
aaa = np.cumsum(aaa)
buf = [(aaa - np.roll(aaa, k))[k:].max() for k in range(1, n + 1)]
print('\n'.join(map(str, buf)))
B - Big Integers
問題
- 長さ $N$ の整数列 $A$、長さ $M$ の整数列 $B$、整数 $K$ が与えられる
- 値 $X,Y$ を以下のように定義する
- $\displaystyle X=\sum^{N}_{i=1}A_i \times K^{N-i} = A_1 \times K^{N-1} + A_2 \times K^{N−2} + ... + A_N \times K^0$
- $\displaystyle Y=\sum^{M}_{i=1}B_i \times K^{M-i} = B_1 \times K^{M-1} + B_2 \times K^{M−2} + ... + B_M \times K^0$
- $X$ と $Y$ のどちらが小さいか求めよ
- $0 \le A_i,B_i \le K-1$
- $1 \le A_1,B_1$
解法
ややこしい書き方をしているが、$K$ 進法同士の比較。
桁数が小さい方、同じなら上位桁から見ていって、最初に小さい数字が現れた方。
def solve(n, m, k, aaa, bbb):
if n < m:
return 'X'
if n > m:
return 'Y'
if aaa < bbb:
return 'X'
if aaa > bbb:
return 'Y'
return 'Same'
n, m, k = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(solve(n, m, k, aaa, bbb))
C - Come Together
問題
- $H \times W$ の各マス目にコマが1つずつ置かれている
- $K$ 個のコマを取り除く（$(R_1,C_1),(R_2,C_2),...,(R_K,C_K)$ で与えられる）
- 取り除いた後、以下の操作を繰り返して、盤面に残る全てのコマを1箇所のマスに集める
- 1つのコマを、上下左右に隣接するいずれかのマスに移動させる
- 操作回数の最小値を求めよ
解法
どこのマスに集めるかを決める。
縦に動かす動作・横に動かす動作は互いに干渉しないので、縦横を独立に考えられる。なので以下 $X$ 座標を考える。
仮に集める座標を $x$ とする。 これを $x+1$ に変更すると、$x$ より右にある全てのコマの必要回数が1回ずつ減り、$x$ 以左にある全てのコマの必要回数が1回ずつ増える。
なので、最適な $x_a$ は、全てのコマの $X$ 座標の中央値となる。
または、下に凸の形をしているので、三分探索でも求められる。
import bisect
import sys
import numpy as np
def search(aaa, size):
l, r = 0, size
coef_base = np.arange(size, dtype=np.int64)
while l < r:
m1 = (l + r) // 2
m2 = m1 + 1
cost1 = (abs(coef_base - m1) * aaa).sum()
cost2 = (abs(coef_base - m2) * aaa).sum()
if cost1 < cost2:
r = m1
elif cost1 > cost2:
l = m2
else:
return cost1
return (abs(coef_base - l) * aaa).sum()
h, w, k = map(int, input().split())
rrr = np.full(h, w, dtype=np.int64)
ccc = np.full(w, h, dtype=np.int64)
for line in sys.stdin:
r, c = map(int, line.split())
rrr[r - 1] -= 1
ccc[c - 1] -= 1
print(search(rrr, h) + search(ccc, w))
D - Deforestation
問題
- 竹が $N$ 本あり、初期の高さはいずれも0。時刻1につき1m伸びる
- $M$ 回、竹を切る
- $i$ 回目に切る時は、時刻 $T_i$ に、$[L_i, R_i]$ の範囲の竹を切る
- 切った竹の長さの合計値が得点として加算される
- 切られた竹は高さ0になるが、再び伸び続ける
- 最終的に得られる得点を求めよ
解法
途中で何回切ったかに関わらず、ある竹1本から得られるスコアは、その竹を「最後に切った時刻」に等しくなる。
なので、RangeUpdateQuery を処理できるセグメント木を作成し、時刻で更新していき、最後に1つ1つの最終的な数を合計すればよい。
セグ木はそれなりに配列参照が多く、Pythonでは間に合わないこともあるためPyPyを検討することになるが、PyPyは関数の再帰呼び出しがあまり得意では無いため、なるべく再帰を使わない書き方で実装した方がよいっぽい。
セグ木上の各要素にsentinel以外の値が入っていれば、その区間の下は全て同じ値、ということにしている。（変数名が実態と合ってないのでよくない）
import sys
class RangeUpdateTree:
def __init__(self, n, initial=0, sentinel=-1):
n2 = 1 << n.bit_length()
self.n = n2
self.offset = n2
self.data = [initial] * (n2 << 1)
self.sentinel = sentinel
def update(self, a, b, x):
stack = [(1, 0, self.n)]
while stack:
i, l, r = stack.pop()
if a <= l and r <= b:
self.data[i] = x
continue
y = self.data[i]
j = i << 1
if y != self.sentinel:
self.data[i] = self.sentinel
self.data[j] = self.data[j + 1] = y
m = (l + r) // 2
if a < m:
stack.append((j, l, m))
if m < b:
stack.append((j + 1, m, r))
def aggregate(self):
stack = [1]
ans = 0
while stack:
i = stack.pop()
if self.data[i] != self.sentinel:
ans += self.data[i] * (self.n >> i.bit_length() - 1)
continue
i <<= 1
stack.append(i)
stack.append(i + 1)
return ans
def debug_print(self):
i = 1
while i <= self.offset:
print(self.data[i:2 * i])
i <<= 1
n, m = map(int, input().split())
rut = RangeUpdateTree(n)
for line in sys.stdin:
t, l, r = map(int, line.split())
rut.update(l - 1, r, t)
print(rut.aggregate())
E - Erasure
問題
- 箱が $N$ 個、横一列に並んでいる
- 整数 $K$ が与えられる
- 連続する箱の選び方のうち、長さ $K+1$ 以上の区間は、$(N-K)(N-K+1)/2$ 通りある
- つまり、それぞれの区間を選ぶか選ばないかで「区間の選び方の組」は $2^{(N-K)(N-K+1)/2}$ 通りある
- このうち、全ての箱がいずれかの区間に入っているような「区間の選び方の組」の個数を $\mod{10^9+7}$ で求めよ
- $1 \le N \le 5000$
解法
以下の説明では、以下の記号を用いる。
1 2 ... i |------------------| 1～iを覆う単一の区間 |==================| 1～iを覆える区間の組（単一とは限らないが、いずれかでは覆われている） |..................| 特に覆う覆わないに関係なく、1～iの範囲
ひとまず、こんなDPを試してみる。
$DP[j]=1～j$ 個目の箱まで覆うが、$j+1$ 個目の箱はまだ覆われていないような区間の組の選び方
これで $DP[j]$ から $DP[j+1]$ に遷移を考える。$j+1$ を覆わねばならず、$j+2$ は覆われてはいけないので、$j+1$ が右端である区間をどれか1つは使わなくてはならない。
1 2 3 .. j-K .. j j+1
|======================| DP[j]
|---------------------------| ┐
|------------------------| │ j-K+1 個の内
|---------------------| │ 少なくともどれか1つあればいい
... │ DP[j+1] = DP[j] * (2^(j-K+1) - 1) ???
|-------------| ┘
という感じで遷移したいが、以下のようなケースで困る。
|---------------------| ←例えばこれを追加するときは
|========| |------| 追加区間で覆われていない区間さえ覆われていれば、
途中で途切れていてもよい
この途中で途切れた選び方の数は、DPに入っていない
改めてDPをこう定義する。
$DP[i][j]=$右端が $i$ 個目までで終わる区間だけを使って、$1～j$ 個目の箱は覆われ、$j+1$ 個目は覆われていないような区間の組の選び方
$DP[N][N]$ が答えとなる。実際は、$i+1$ を求める際には $i$ の情報があれば良いので、$DP[j]$ を逐次的に更新していくことで1次元配列で実装できる。
違いは、途切れた区間でもパターン数を数え上げられる点。
1 j i
|========| |------| |--| 表現するパターン数
^ ^
旧DP[j] 新DP[i][j]
$1～j$ まで覆われ、$j+1$ が覆われていなければ、「$j+2～i$ はどうなっていてもよい」という部分を織り込んだ値となる。
DP[i][i]の遷移
$DP[i-1][1～i-1]$ まで求められていて、$DP[i][1～i]$ を求める。まずは、$DP[i][i]$ を求める。
$i$ の箱は覆わなければならないが、$i+1$ の箱は覆われてはいけないため、「$i$ を右端に持つ区間」を1つは使う必要がある。
1～iを覆う単一の区間を使う場合
1 2 3 ... i
|-----------------|
|----| ←残りは自由
この場合、他の区間は完全に使うも使わないも自由。他の区間は $(i-K-1) \times (i-K+2)/2$ 個あるので、選び方は $2^{(i-K-1) \times (i-K+2)/2}$ 通りある。
1～iを覆う区間を使わない場合
場合分けのため、$i$ を右端に持つ区間の内、最も長いものを $x～i$ とする。
すると、遷移元が $DP[i-1][x-1]～DP[i-1][i-1]$ のいずれかであれば、$1～i$ が全て覆われた状態を保てる。 また、自身より短い$i$ を右端に持つ区間 $x+1～i, x+2～i, ...$ は加えても加えなくても良い。
よって、$\displaystyle \sum^{i-1}_{z=x-1}(DP[i-1][z]) \times 2^{i-x-K}$ 通りが加えられる。
1 2 3 .. x-1 x ... i
|-----------------|
遷移元
|==============| DP[i-1][x-1]
|==================| DP[i-1][x]
...
|=============================| DP[i-1][i-1]
新規任意追加
|-------------|
|----------| i-x-K 個
|------|
$x$ は$2～i-K$ まで動くので、$\displaystyle \sum^{i-K}_{x=2}\sum^{i-1}_{z=x-1}(DP[i-1][z]) \times 2^{i-x-K}$ となる。うわあ、式で書くとややこしい。
でもこれ、DP[i-1]の後ろからの累積和と、2の累乗を事前計算しておけば、それらのドット積となり、そこそこ簡単にはなる。
K=2
1 2 3 4 5 6 7
DP[i-1] 0 0 1 5 50 904
ACC 960 960 960 959 954 904
2^x 8 4 2 1 __ __ (末尾K個は不使用)
----------------------------
ACC*2^x 7680 3840 1920 959 --合計-> 14399
これに区間 $1～i$ を使う場合の$2^{14}=16384$ を加えて、30783 が $DP[i][i]$ となる。
DP[i][j]の更新
$DP[i][j]$ は、$DP[j][j]$（旧$DP[j]$）に、$j+2～i-1$ の間の箱だけで取れる区間のパターン数をかけた値となる。
1 j j+2 i-1 i
|========| |...............|
^ ここだけで何パターンできるか？
旧DP[j]
なので区間の長さ $i-j$ が $K+1$ に満たないと1（何も置かない）
置ける場合は、DP[i-1][j] の値に「$2^{i-1 が右端となる区間の数}$」をかけていくと更新できる。
K=2
1 2 3 4 5 6 7 8
DP[7] 0 0 2 5 50 904 30783
16 8 4 2 ※ ※ ※ ※: 置けない
-----------------------------------------
DP[8] 0 0 8 10 50 904 30783 2032629
これで $DP[i]$ が全て求まったので、$N$ まで繰り返せば答えとなる。
import numpy as np
n, k = map(int, input().split())
MOD = 10 ** 9 + 7
pow2 = [0] * (n - k + 1)
pow2[0] = 1
for i in range(1, n - k + 1):
pow2[i] = pow2[i - 1] * 2 % MOD
pow2 = np.array(pow2, dtype=np.int64)
dp = np.array([0] * k + [1, 5], dtype=np.int64)
p = 5
for i in range(k + 2, n):
if i > (k + 1) * 2:
tmp = dp[k:i - k - 1] * pow2[:i - 2 * k - 1][::-1] % MOD
dp[k:i - k - 1] = tmp
dp_acc = np.cumsum(dp[::-1]) % MOD
dp = np.append(dp, (pow(2, p, MOD) + ((dp_acc[k:] * pow2[:i - k]) % MOD).sum()) % MOD)
p += i - k + 2
print(dp[n - 1])
解説pdfにあった、$DP[i][j]=i$ より左の区間のみを使って、$1～j$ が覆われて $j+1$ がまだ覆われていないような区間の組の選び方 とする解法（後で考えたら $i$ の条件が右端→左端になっただけ？）
n, k = map(int, input().split())
MOD = 10 ** 9 + 7
pow2 = [0] * (n - k + 1)
pow2[0] = 1
for i in range(1, n - k + 1):
pow2[i] = pow2[i - 1] * 2 % MOD
dp = [0] * n
dp_acc = [1] * n
for i in range(n - k):
ndp = [0] * n
for j in range(i + k, n):
ndp[j] = (dp[j] * pow2[j - i - k + 1] +
dp_acc[j - 1] * pow2[j - i - k]) % MOD
dp = ndp
if i > k:
r = dp_acc[i - 1]
for j in range(i - 1, n):
dp_acc[j] -= r
if i == 0:
dp_acc[k - 1] = 0
for j in range(i + k, n):
dp_acc[j] = (dp_acc[j - 1] + dp[j]) % MOD
print(dp[-1])
