目次
AtCoder Beginner Contest 154 D～F問題メモ
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$ 個の和の最大値を求めればよい。
n, k = map(int, input().split())
ppp = list(map(int, input().split()))
tot = sum(ppp[:k])
ans = tot
for i in range(k, n):
tot += ppp[i] - ppp[i - k]
ans = max(ans, tot)
print((ans + k) / 2)
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しか置かれていない」というのも加えることで、場合分けが可能になる。
n = input()
k = int(input())
dp = [[0] * (k + 2) for _ in range(2)]
dp[0][0] = 1
for d in n:
ndp = [[0] * (k + 2) for _ in range(2)]
for i in range(k + 1):
ndp[1][i] += dp[1][i]
ndp[1][i + 1] += dp[1][i] * 9
if d == '0':
ndp[0][i] += dp[0][i]
else:
ndp[1][i] += dp[0][i]
ndp[1][i + 1] += dp[0][i] * (int(d) - 1)
ndp[0][i + 1] += dp[0][i]
dp = ndp
print(dp[0][k] + dp[1][k])
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様にお伺いを立てます。
すると、こう変形できるとわかります。
$\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 であるとわかる
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7
facts, invs = prepare(r2 + c2 + 1, MOD)
ans = 0
for i in range(r1, r2 + 1):
d1 = facts[i + c2 + 1] * invs[c2] % MOD
d2 = facts[i + c1] * invs[c1 - 1] % MOD
ans = (ans + (d1 - d2) * invs[i + 1]) % MOD
print(ans)
別解
解説放送で紹介されていた解法。
この問題のように、長方形領域の和を求めるには、(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)$ で可能になる。
