全国統一プログラミング王決定戦本戦 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

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$ 進法同士の比較。

桁数が小さい方、同じなら上位桁から見ていって、最初に小さい数字が現れた方。

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$ 座標の中央値となる。

または、下に凸の形をしているので、三分探索でも求められる。

D - Deforestation

• 竹が $N$ 本あり、初期の高さはいずれも0。時刻1につき1m伸びる
• $M$ 回、竹を切る
  • $i$ 回目に切る時は、時刻 $T_i$ に、$[L_i, R_i]$ の範囲の竹を切る
  • 切った竹の長さの合計値が得点として加算される
• 切られた竹は高さ0になるが、再び伸び続ける
• 最終的に得られる得点を求めよ

途中で何回切ったかに関わらず、ある竹1本から得られるスコアは、その竹を「最後に切った時刻」に等しくなる。

なので、RangeUpdateQuery を処理できるセグメント木を作成し、時刻で更新していき、最後に1つ1つの最終的な数を合計すればよい。

セグ木はそれなりに配列参照が多く、Pythonでは間に合わないこともあるためPyPyを検討することになるが、PyPyは関数の再帰呼び出しがあまり得意では無いため、なるべく再帰を使わない書き方で実装した方がよいっぽい。

• Emerge Technology: pypyは本当に速いのか？試してみた

セグ木上の各要素にsentinel以外の値が入っていれば、その区間の下は全て同じ値、ということにしている。（変数名が実態と合ってないのでよくない）

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-1][1～i-1]$ まで求められていて、$DP[i][1～i]$ を求める。まずは、$DP[i][i]$ を求める。

$i$ の箱は覆わなければならないが、$i+1$ の箱は覆われてはいけないため、「$i$ を右端に持つ区間」を1つは使う必要がある。

 1  2  3  ...    i
|-----------------|
      |----|          ←残りは自由

この場合、他の区間は完全に使うも使わないも自由。他の区間は $(i-K-1) \times (i-K+2)/2$ 個あるので、選び方は $2^{(i-K-1) \times (i-K+2)/2}$ 通りある。

場合分けのため、$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[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$ まで繰り返せば答えとなる。

解説pdfにあった、$DP[i][j]=i$ より左の区間のみを使って、$1～j$ が覆われて $j+1$ がまだ覆われていないような区間の組の選び方 とする解法（後で考えたら $i$ の条件が右端→左端になっただけ？）