AtCoder Beginner Contest 154 D～F問題メモ

AtCoder Beginner Contest 154

8時くらいに「きょうはねむいな～」と思っている日のコンテストはだいたい寝過ごす。

D - Dice in Line

• $N$ 個のダイスが横一列に並ぶ
• 左から $i$ 番目のダイスは、$1～p_i$ の $p_i$ 種類の目が等確率で出る
• 連続する $K$ 個のサイコロを同時に振ったとき、出目の和の期待値の最大値を求めよ
• $1 \le K \le N \le 2 \times 10^5$
• $1 \le p_i \le 1000$

出目の和の期待値＝1個1個の出目の期待値の和（期待値の線形性）

1個1個の出目の期待値は $\displaystyle \frac{p_i+1}{2}$

なので、$\displaystyle \frac{p_i+1}{2}～\frac{p_{i+K-1}+1}{2}$ の連続する $K$ 個の和の最大値を求めればよい。

E - Almost Everywhere Zero

• 1以上 $N$ 以下の整数のうち、10進法で表したとき、0以外の数字をちょうど $K$ 個含むものの個数を求めよ
• $1 \le N \le 10^{100}$
• $1 \le K \le 3$

典型的な桁DP。$K$ の制約がメチャ小さい。

以下のDPを考える。

$dp[i][j][k]=$ 先頭から $i$ 桁目まで見たとき、そこまで $N$ と $[j=0:一致/1:未満]$ で、0以外の数字を $k$ 個使っているものの個数

先頭 $i$ 桁の時点で $j=1$（$N$ より小さいことが確定）していれば、それ以下の数字は好きなものを選べる。 逆に $j=0$ であれば、次の桁以降、$N$ を越えないように選べる数字に制約が生じる。

dp[1]→dp[2]の遷移は以下のようになる。

N = 345  K = 2

dp[1]
j\k  0  1  2    dp[1][0][1] ... 3を置いた状態
0    0  1  0    dp[1][1][0] ... 0を置いた状態
1    1  2  0    dp[1][1][1] ... 1,2を置いた状態

dp[2]への遷移

まず、j=1からの場合を考える。好きな数字を選べる。
  dp[2][1][k]   +=  dp[1][1][k]     : 0を置いた状態
  dp[2][1][k+1] +=  dp[1][1][k] * 9 : 0以外を置いた状態

j=0からの遷移は制限が生じる。Nのi桁目をdiとする。
・di='0'の場合
  dp[2][0][k]   +=  dp[1][0][k]     : 0しか置けない。0を置いてもj=0である状態は変わらない
・di='0'以外の場合
  dp[2][1][k]   +=  dp[1][0][k]          : 0を置く。Nより小さくなったのでj=1に遷移
  dp[2][1][k+1] +=  dp[1][0][k] * (di-1) : 1～(di-1)のいずれかを置く
  dp[2][0][k+1] +=  dp[1][0][k]          : diを置く。j=0は維持される

これを $i$ ごとに各 $k$ について回すことで、$O(Nの桁数 \times K)$ で計算できる。

初期状態は $dp[0][0][0]=1$、答えは $dp[Nの桁数][0][K]+dp[Nの桁数][1][K]$ となる。

今回は0以外という条件だったので、「0052」など先頭に0の付く数字（10進数で表したときには実質消える）も場合分けせずに済んで楽だった。

これが「1以外」などとなると、「0052」に含まれる1以外の数字は「4」でなく「2」と捉えるべきなので、ちょっとだけ複雑になる。

$j$ の状態に「$j=2$:まだ0しか置かれていない」というのも加えることで、場合分けが可能になる。

F - Many Many Paths

• 関数 $f(r,c)$ を以下のように定義する
  • $f(r,c)=$ 2次元グリッドを $(0,0)$ から $x$ または $y$ 方向に1移動することを繰り返して $(r,c)$ まで移動する経路の数
• $r_1 \le r \le r_2$、$c_1 \le c \le c_2$ を満たす $(r,c)$ の組全てについて $f(r,c)$ を求め、その総和を $\mod{10^9+7}$ で求めよ
• $1 \le r_1 \le r_2 \le 10^6$
• $1 \le c_1 \le c_2 \le 10^6$

前提として、経路数え挙げは二項係数となる。 $f(r,c)={}_{r+c}C_{r}$

なので、答えは以下を求めればよい。

$\displaystyle \sum_{i=r_1}^{r_2}\sum_{j=c_1}^{c_2}{}_{i+j}C_{i}$

ここでWolfram Alpha様にお伺いを立てます。

• sum (i+j)!/j!, j = p to q - Wolfram|Alpha

すると、こう変形できるとわかります。

$\displaystyle \sum_{i=r_1}^{r_2} \frac{\frac{(i+c_2+1)!}{c_2!} - \frac{(i+c_1)!}{(c_1-1)!}}{i+1}$

見た目には何じゃこりゃとなるが、$\sum$ のループは1つ減っているので計算量としては階乗を事前計算しておけば $O(r_2-r_1)$ となり、間に合う。階乗の事前計算が $O(r_2+c_2)$ で、こちらの方が時間がかかる。

一応ひもといておくと、これは $\displaystyle \sum_{k=0}^{n}{}_{m+k}C_{k} = {}_{n+m+1}C_{n}$ という公式を利用している。

$$\begin{eqnarray} \sum_{j=c_1}^{c_2}{}_{i+j}C_{j} &=& \sum_{j=0}^{c_2}{}_{i+j}C_{j} - \sum_{j=0}^{c_1-1}{}_{i+j}C_{j} \\ &=& {}_{i+c_2+1}C_{c_2} - {}_{i+c_1}C_{c_1-1} \\ &=& \frac{(i+c_2+1)!}{c_2!(i+1)!} - \frac{(i+c_1)!}{(c_1-1)!(i+1)!} \end{eqnarray}$$

この公式は、「二項係数で1段下の行は、上の行の累積和となっている」ことから説明できる。 二項係数の表は左と上を合計しながら埋めていくので、累積和となることは直感的にわかりやすい。

r\c  0  1  2  3  4 ...
0    1  1  1  1  1  1
1    1  2  3  4  5  6
2    1  3  6 10 15 21 ↙この列は
3    1  4 10 20 35 56 ↖この列の累積和となっている

1～21 の合計は、21の1つ下の 56 であるとわかる

解説放送で紹介されていた解法。

この問題のように、長方形領域の和を求めるには、(0,0) からの2次元累積和を高速に求められればよい。4つの領域の足し引きで求められる。

r\c  0  1  2  3  4  5      (r1,c1)～(r2,c2) の総和
0    1  1  1  1  1  1
1    1  2  3  4  5  6    =   ( 0, 0)～(r2  ,c2  ) の総和     
2    1  3  6 10 15 21      - ( 0, 0)～(r2  ,c1-1) の総和
3    1  4 10 20 35 56      - ( 0, 0)～(r1-1,c2  ) の総和
4    1  5 15 35 70 126     + ( 0, 0)～(r1-1,c1-1) の総和

で、二項係数においては、長方形領域の総和は非常に簡潔に求めることができる。

$\displaystyle \sum_{i=0}^{r}\sum_{j=0}^{c}{}_{i+j}C_{i} = {}_{r+c+2}C_{r+1}-1$

これは、表を用いて次のように導出できる。

$r$ を固定して一つの行だけ見たときに、$c=0～c_1$ の総和は既述の通り、${}_{r+1+c_1}C_{c_1}$ となる。

さらにこれを縦にまとめると、

r\c  0  1  2  3  4  5
0    1  1  1  1  1  1      ( 0, 0)～( 3, 4) の総和
1    1  2  3  4( 5) 6    = ( 1, 4)～( 4, 4) の総和(括弧を付けた数字)
2    1  3  6 10(15)21    = ( 0, 4)～( 4, 4) の総和 - (0, 4)
3    1  4 10 20(35)56    = ( 4, 5) - 1
4    1  5 15 35(70)126   = 126 - 1
                   ~~~   = 125

階乗の事前計算は相変わらず $O(r_2+c_2)$ かかるが、それを使って長方形領域の和を計算する部分は $O(1)$ で可能になる。