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$ 個の和の最大値を求めればよい。

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)$ で可能になる。

programming_algorithm/contest_history/atcoder/2020/0210_abc154.txt · 最終更新: 2020/02/19 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0