AtCoder Beginner Contest 154

今回のコンペは、何というか…タイピング速度のコンペではないか。

D - Dice in Line

import sys
read = sys.stdin.read

n, k, *p = map(int, read().split())
res = tmp = sum(p[:k])
for i in range(k, n):
    tmp = tmp - p[i - k] + p[i]
    if tmp > res:
        res = tmp
print((res + k) / 2)

E - Almost Everywhere Zero

一番早いコードを参考した。
$1≤K≤3$ですから、各々設定しても楽です。
再帰関数で高速計算できる。

import sys
read = sys.stdin.read
n, k = map(int, read().split())


def count(digit, k):
    if k == 0:  # とても重要な設定。「digit個0」という解答が存在するためreturnが1
        return 1
    elif k == 1:
        return digit
    elif k == 2:
        return digit * (digit - 1) // 2
    else:
        return digit * (digit - 1) * (digit - 2) // 6


def solve(n, k):
    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:  # 末尾桁を0で、他の桁からk個位置を抽選し1~9を入れる。
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10**(digit - 1)
    d, mod = n // pow10, n % pow10
    res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
    res += solve(mod, k - 1)
    return res


print(solve(n, k))

F - Many Many Paths

https://atcoder.jp/contests/abc154/submissions/9997279
を参考した。
解説で言ってなかったことが一つ：
$g(r,c)+1=f(r+1,c+1)$

g(r,c):
	f(0,0)	f(0,1)	...	f(0,c)
	f(1,0)	f(1,1)	...	f(1,c)
	f(2,0)	f(2,1)	...	...
	...	...	...	...
	f(r,0)	f(r,1)	...	f(r,c)
合計	f(r,1)	f(r,2)	...	f(r,c+1)

合計の合計にf(r,0)を加算すればf(r+1,c+1)になる。
よって、
$\quad g(r2,c2)−g(r2,c1−1)−g(r1−1,c2)+g(r1−1,c1−1)$
$=f(r2+1,c2+1)−f(r2+1,c1)−f(r1,c2+1)+f(r1,c1)$

import numpy as np
import sys
read = sys.stdin.read
r1, c1, r2, c2 = map(int, read().split())
MOD = 10 ** 9 + 7


def cumprod(A, MOD=MOD):
    L = len(A)
    Lsq = int(L**.5 + 1)
    A = np.resize(A, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        A[:, n] *= A[:, n - 1]
        A[:, n] %= MOD
    for n in range(1, Lsq):
        A[n] *= A[n - 1, -1]
        A[n] %= MOD
    return A.ravel()[:L]


def make_fact(U, MOD=MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    fact.flags.writeable = False
    fact_inv.flags.writeable = False
    return fact, fact_inv


fac, finv = make_fact(2 * 10**6 + 10, MOD)


# 組合せ計算
def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


answer = comb(r2 + c2 + 2, r2 + 1) - comb(c1 + r2 + 1, c1) - \
    comb(r1 + c2 + 1, r1) + comb(r1 + c1, r1)

answer %= MOD
print(answer)