全国統一プログラミング王決定戦本戦 A~E問題メモ

A - Abundant Resources

問題

  • $N$ 要素の数列 $A_1,A_2,\ldots,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} + \ldots + 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} + \ldots + 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),\ldots,(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, \ldots$ は加えても加えなくても良い。

よって、$\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])

programming_algorithm/contest_history/atcoder/2019/0217_nikkei2019-final.txt · 最終更新: 2019/02/20 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0