−目次

CODE FESTIVAL 2018 qual A
- A - 配点
  - 問題
  - 解法
- B - みかん
  - 問題
  - 解法
- C - 半分
  - 問題
  - 解法
- D - 通勤
  - 問題
  - 解法

CODE FESTIVAL 2018 qual A

A - 配点

問題

問題を3問作り、配点を決めようとしている
以下の条件を満たす配点にできるか、判定せよ
- 1問目は $A$ 点または $A+1$ 点
- 2問目は $B$ 点または $B+1$ 点
- 3問目は $C$ 点または $C+1$ 点
- 3問の合計は $S$ 点

解法

合計は $(A+B+C)～(A+B+C+3)$ の間の任意の値を取れる。この中に $S$ が入っていればよい。

        
              a = int(input())
b = int(input())
c = int(input())
s = int(input())
print('Yes' if a + b + c <= s <= a + b + c + 3 else 'No')

B - みかん

問題

$N$ 個のみかんがあり、 $1～N$ の番号が付いている
それぞれの房の数は、ちょうど $A$ または $B$ である
- $A \lt B$
$M$ 個の情報がある
$i$ 個目の情報では「 $l_i～r_i$ のみかんの房は $A$ 個である」ことがわかる
全てのみかんの房の数の合計として、考えられる最大値を求めよ
$1 \le N,M \le 100$

解法

未確定の房は $B$ であった方が明らかに合計が大きくなるので、最大値を求める上では $B$ と考えてよい。

制約が小さいので、シミュレーションする。

$N$ 要素の配列を用意して、 $B$ で初期化する。

それぞれの情報で $l_i～r_i$ のみかんを $A$ にする。

        
              n, m, a, b = map(int, input().split())
mikan = [b] * n
for _ in range(m):
    l, r = map(int, input().split())
    for m in range(l - 1, r):
        mikan[m] = a
print(sum(mikan))

C - 半分

問題

数列 $A=\{a_1,a_2,...,a_N\}$
以下の操作をちょうど $K$ 回行う
- $A$ の1要素を選び、2で割る。余りは切り捨てる
$K$ 回の操作後の $A$ の状態としてあり得るものの数を、 $\mod{10^9+7}$ で答えよ
$1 \le N \le 50$
$0 \le a_i \le 10^{18}$
$0 \le K \le 10^9$

解法

0は2で割っても0のまま
他の数は2で割ると、数字が変化し、0までの必要回数が1回減る
$a_i$ を2で割って0にするために必要な回数を $cnt_i$ とすると、
- $a_i=0$ の時は0
- それ以外は $\log_2{a_i}+1$ （小数点以下切り捨て）

これらを踏まえ、以下のように問題は言い換えられる。

石の山が $N$ 個あり、それぞれ $cnt_1,cnt_2,...,cnt_N$ 個の石が積まれている
以下の操作をちょうど $K$ 回行う
- 山を1つ選び、石が残っていたら1個取る。残ってなかったら何もしない
$K$ 回の操作後、各石山に石が何個残っているかの状態数を求める

実際にやってみると、以下のことが分かる。

0個の石山が存在すると、それを選べば状態を変化させること無く何回でも操作を行える
0個の石山が存在しないと、どれかから1個取って状態を変化させざるを得ない

まず思いつくDP

解法としてDPと当たりを付け、 $dp_{i,k}$ を「 $1～i$ 番目までの石山だけに注目して、 $k$ 回操作した後の状態数」としたとする。

だがこのままでは、なかなか遷移が難しい。実際に簡単な例で試してみる。

石山の初期状態 : {1, 2, 3}

i=1
iまでの石山の初期状態: {1}
0回操作で       {1} の1通り
1回(以上)操作で {0} の1通り

i=2
iまでの石山の初期状態: {1, 2}
0回操作で {1, 2} の1通り
1回操作で {0, 2}, {1, 1} の2通り
2回操作で {0, 2}, {0, 1}, {1, 0} の3通り
3回操作で {0, 2}, {0, 1}, {1, 0}, {0, 0} の4通り
4回以上の操作ではずっと4通り

i=3
iまでの石山の初期状態: {1, 2, 3}
操作回数    0   1   2   3   4   5   6以上
パターン数  1   3   6  10  14  17  18

どういう計算で遷移させればよいか？法則性が見えづらい。

ややこしくしている原因は0個の石山の扱いにあって、

遷移
- $dp_{i,k}$ の中で0個の石山が含まれている状態数は、そのまま $dp_{i,k+1}$ に引き継ぐことができる
- $dp_{i,k}$ の中で0個の石山が含まれていない状態数は、引き継ぐことができない
空間・計算量
- dpの計算量は $O(N \times (kの上限))$
- 全ての石山が0になっても操作は続けられるので $k$ の上限は $K$ となるが、 $K \le 10^9$ なのでとても間に合わない
- ただ、これは回避する方法がある（後述）

改良版DP

もう一つDPに区別を設け、 $dp_{i,k,j}$ とし、 $j$ を0か1の値を取る「0個の石山が含まれるかフラグ」とすれば遷移はやりやすそう。

また区別することで「各操作で、0個の石山は選ばない（常にどこかから石を取る）」とルールを設けてもよくなり、これにより空間の問題も解消する。

どういうことかというと、 $k$ 回の操作後に0個の石山が含まれている場合は、 $k+1,k+2,...$ 回の操作後の全ての場合においてその状態が実現可能。なので $K=k+1$ の時の答えを求めたければ、 $K=1～k$ の、0個の石山を含む状態数から取ってこれるので、dp(k+1)自身が持つ必要が無い。

これにより考慮すべき $k$ の上限が $cnt_i$ の総和までとなり、各 $cnt_i$ は $log_2{10^{18}}=60$ 程度までなので、 $N=50$ でも3000程度となり、十分小さくなる。

石山の初期状態 : {1, 2, 3}
便宜上、dp(i,k,j) の j=0をdp0, j=1をdp1と表現する

i=1
  k  __0__1___
dp0 :  1  0    # 0個の石山を含まない場合
dp1 :  0  1    # 0個の石山を含む場合
0回の操作後は {1} の、0個の石山を含まない場合が1通り
1回の操作後は {0} の、0個の石山を含む場合が1通り
2回以上は操作を行えない

i=2
  k  __0__1__2__3__
dp0 :  1  1
dp1 :     1  2  1
1回の操作後は {0, 2}, {1, 1}  それぞれ0個の石山を含む場合と含まない場合が1通りずつ
2回の操作後は {0, 1}, {1, 0}  0個の石山を含む場合が2通り
                              ※{0, 2} も元のルールでは2回の操作後に実現可能だが、
                                0個の石山に対して操作しないとならず、
                                1回の操作後で既にカウントされているのでここでは考慮しない
3回の操作後は {0, 0}          0個の石山を含む場合が1通り

i=3
  k  __0__1__2__3__4__5__6__
dp0 :  1  2  2  1
dp1 :     1  3  5  5  3  1
各操作後の状態は省略

K=3の時の状態数を求める時は、
dp0からはそのまま取ってきて1通り。
dp1からは、3以下の状態数を合計して 1+3+5=9通り。
計10通り

遷移

いずれの遷移も、 $dp_i$ の状態のみから $dp_{i+1}$ を決定できる。

dp0 からの遷移

$dp0_{i,k}$ からは、 $dp0_{i+1}$ と $dp1_{i+1}$ の両方に遷移する。

まず、 $dp0_{i+1,k+q}$ （ただし $q=0,1,...,cnt_{i+1}-1$ ）に状態数は引き継がれる。

これは、 $i+1$ 個目の石山を、0個減らした場合、1個減らした場合、……、 $cnt_{i+1}-1$ 個減らした場合を意味している。石山は0にしてはいけないのでその直前まで。

また、 $dp1_{i+1,k+cnt_{i+1}}$ に引き継がれる。

これは、 $i+1$ 個目の石山に $cnt_{i+1}$ 回操作を加えて0にした場合を意味している。

dp1 からの遷移

$dp1_{i,k}$ からは、 $dp1_{i+1}$ に遷移する。

$dp1_{i+1,k+q}$ （ただし $q=0,1,...,cnt_{i+1}$ ）に引き継がれる。

これは、 $i+1$ 個目の石山を、0個減らした場合、1個減らした場合、……を意味している。こちらは0まで減らしてもよい。

余談: 改良前のDPでKが大きい時の回避方法

$K$ が $cnt_i$ の総和（ $cnt_1+cnt_2+...+cnt_N$ ）以上の場合、つまり、全ての石山を0にするのに十分な場合、簡単に計算できる。 $cnt_i$ の総和以上の $K$ では、既に取り得る全ての状態を数え上げているので、それ以上 $K$ が増えても答えが増えることはない。

$i$ 個目の石山のみに着目すると、 $0,1,2,...,cnt_i$ の $cnt_i+1$ 通りの状態を取れる。

全ての状態数(仮)は、 $(cnt_1+1)\times(cnt_2+1)\times ... \times(cnt_N+1)$ となる。

ただしこの中には、 $K$ 回の操作では不可能なものもある。それは全ての石山が0でない状態。 $K$ 回操作すると、少なくとも1つの石山は必ず0にせざるを得ない。逆に少なくとも1つの石山が0であれば、 $K$ 回の操作後でも可能となる。

よって、状態数(仮)から全ての石山が0でない $cnt_1 \times cnt_2 \times ... \times cnt_N$ 通りを除けば、答えが求まる。

この枝刈りをしておけば、保持すべき $K$ の上限は $cnt_i$ の総和までとなり、空間の問題については解決する。（まぁ結局遷移が難しいんですけど）

        
          
          
              
              def dividable(a):
    if a == 0:
        return 0
    return len(bin(a)) - 2
 
 
def solve(n, k, aaa):
    ddd = list(map(dividable, aaa))
    s = sum(ddd)
    if k >= s:
        ans = 1
        exc = 1
        for d in ddd:
            ans *= (d + 1)
            ans %= MOD
            exc *= d
            exc %= MOD
        return (ans - exc) % MOD
 
    dp0 = [1]
    dp1 = [0]
    for d in ddd:
        ndp0 = [0] * (len(dp0) + d)
        ndp1 = [0] * (len(dp0) + d)
        for i, (p0, p1) in enumerate(zip(dp0, dp1)):
            for q in range(d):
                ndp0[i + q] += p0
                ndp1[i + q] += p1
            ndp1[i + d] += p0 + p1
        dp0 = ndp0
        dp1 = ndp1
        print(dp0)
        print(dp1)
    return (dp0[k] + sum(dp1[:k + 1])) % MOD
 
 
MOD = 1000000007
 
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, k, aaa))

            

        
      

D - 通勤

問題

1次元上の座標 0 から $D$ まで車で移動する
車のガソリンタンクは出発時、満タンで $F$ リットル入っている
座標1移動するのに1リットル消費する
$N$ 個のガソリンスタンドが座標 $0 \lt x_1 \lt x_2 \lt ... \lt x_N \lt D$ にある
ガソリンスタンドの前を通過する時、以下のルールでガソリンを補充する
- ガソリンの残りが $T$ リットル以上あればスルー
- それ未満ならそこで満タンまで補充

いくつかのガソリンスタンドを取り壊したい
$D$ までたどり着けるような取り壊し方は、何通りあるか、 $\mod{10^9+7}$ で答えよ

解法

$i$ 番目のガソリンスタンドを $GS_i$ と表す。

$GS_i$ で補充後、次に補充できる可能性のあるGSは、座標 $x_i+(F-T) \lt x_k \le x_i+F$ にある $GS_k$ となる。

FULL                   NEXT  NEXT  NEXT
 ↓
 x1 --- x2 x3 x4 ------ x5 -- x6 -- x7 ----- x8
  <--- F-T --->
  <----------------- F ----------------->

DPを考える。 $dp_{i}=$ 「 $GS_i$ で補充することになるような、 $GS_1,GS_2,...,GS_{i-1}$ の取り壊され方のパターン数」とする。

上の例で、 $GS_1$ で補充し、次に補充するGSを考える。

$GS_2,GS_3,GS_4$ は残ってても壊されてても通過するので関係ない
$dp_1$ から $dp_5$ へは、通過した3箇所分の取り壊され方が自由のため $2^3$ 倍して遷移する
$dp_1$ から $dp_6,dp_7$ へも同様
- $GS_1$ の次に $GS_6$ で補充するためには $GS_5$ は取り壊されていないといけないので、そこでパターン数が増える余地は無い

これを先頭からDPで配っていけばよい。座標0の出発地点を $GS_0$ と見なし、 $dp_0=1$ としてそこから始める。

答えの数え上げは、最後に給油することになりえる（つまり、 $x_i+F \ge D$ ）各 $GS_i$ につき、残ってても通過するGSの数 $t$ を求め、 $dp_i \times 2^t$ を加算する。

最後に給油
↓
xi --- x x x -------- x x x ----- D
 <----- F-T ----->
 <-------------------- F -----------...->
 
 `---------------'|`--------------'
残ってても通過する|xiを最後の給油地点にするためには
      GSは3個     |必ず取り壊されてないといけない

ANS += dp[i] * 2^3

実装は、区間への足し込みを行うため、BITなどを使って累積和で管理する。が、もっと速い提出があるのでよりよい方法はありそう（たぶんbisectで探してる部分は尺取り法でいける）。BITではMODを取ることに注意。

        
          
          
              
              import bisect
 
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s % MOD
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            self.tree[i] %= MOD
            i += i & -i
 
 
MOD = 1000000007
d, f, t, n = map(int, input().split())
xxx = [0] + list(map(int, input().split()))
r = f - t
dp = Bit(n + 2)
dp.add(1, 1)
dp.add(2, -1)
reachable = d - f
ans = 0
for i, x in enumerate(xxx):
    i += 1
    s = dp.sum(i)
    if s == 0:
        continue
    ti = bisect.bisect(xxx, x + r, lo=i)
    fi = bisect.bisect(xxx, x + f, lo=ti)
    inc = s * pow(2, ti - i, MOD) % MOD
    if ti < fi:
        dp.add(ti + 1, inc)
        dp.add(fi + 1, -inc)
    if x >= reachable:
        ans += inc
        ans %= MOD
print(ans)

            

        
      