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

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
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