京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）

A - Century

答えは $\left\lfloor\dfrac{N-1}{100}\right\rfloor+1$ ．

実装 (Python)

print((int(input()) - 1) // 100 + 1)

B - 200th ABC-200

毎回愚直に操作してよい．多くの言語は % 演算子で剰余を取ることが出来る．

実装

N, K = map(int, input().split())
for _  in range(K):
    if N % 200:
        N = N * 1000 + 200
    else:
        N //= 200
print(N)

C - Ringo's Favorite Numbers 2

$A _ i - A _ j$ が $200$ の倍数という条件は $A _ i \equiv A _ j\pmod{200}$ と言い換えられるので， $\mathrm{cnt} [ i ] = \# \{j\mid A _ j \bmod 200 = i \}$ を計算しておく．すると，答えは

$\displaystyle \sum_{j=0}^{199}\frac{\mathrm{cnt} [ i ](\mathrm{cnt} [ i ] - 1)}{2}$

と表される．

実装 (Python)

N = int(input())
A = list(map(int, input().split()))
cnt = [0] * 200
for v in A:
    cnt[v % 200] += 1
ans = 0
for c in cnt:
    ans += c * (c - 1) // 2
print(ans)

D - Happy Birthday! 2

私の解法は after_contest で落ちました...

E - Patisserie ABC 2

$k$ 個の非負整数 $A _ 1,\ldots, A _ k$ であって， $0\leq A _ i\lt N\;(i=1,\ldots,k)$ かつ和が $M$ であるようなものの個数は

$\displaystyle [x^M](1+\cdots x^{N-1})^k=[x^M]\left(\frac{1-x^N}{1-x}\right)^k$

と表せる．今回は $k=1,2,3$ に対してこの多項式を ( $\mathrm{mod}\; x ^ {3N}$ で) 予め計算しておくことで， $i+j+k\to i\to j\to k$ の順に全体 $O(N)$ で確定していくことができる．

$1 - x ^ N$ を掛けるのは各係数 $c _ i$ に対して $c _ i\leftarrow c _ i - c _ {i - N}$ とすればよく， $1 - x$ で割るのは $c _ i\leftarrow c _ 0 + \cdots + c _ i$ とすればよい．in-place に計算を行う場合は，前者は次数の降順に，後者は次数の昇順に計算を行うようにすると良い．

なお，数学をすることで各多項式の係数の prefix sum あるいは suffix sum は $O(1)$ で求められるので，二分探索により $O(\log N)$ で解くことも可能である．

実装 (Python)

N, K = map(int, input().split())
f1 = [0] * (3 * N + 1)
f1[0] = 1
f1[N] = -1
for i in range(3 * N):
    f1[i + 1] += f1[i]
f2 = f1[:]
for i in range(3 * N):
    f2[i + 1] += f2[i]
for i in range(3 * N, N - 1, -1):
    f2[i] -= f2[i - N]
f3 = f2[:]
for i in range(3 * N):
    f3[i + 1] += f3[i]
for i in range(3 * N, N - 1, -1):
    f3[i] -= f3[i - N]
for x in range(3 * N - 2):
    if K > f3[x]:
        K -= f3[x]
        continue
    for i in range(min(N, x + 1)):
        if K > f2[x - i]:
            K -= f2[x - i]
            continue
        for j in range(min(N, x - i + 1)):
            if K > f1[x - i - j]:
                K -= f1[x - i - j]
                continue
            k = x - i - j
            print(i + 1, j + 1, k + 1)
            exit(0)

F - Minflip Summation

まず，? を 0 または 1 に決めた後の問題の答えを考える．文字列を円環として見る (即ち，先頭の文字と末尾の文字も隣接しているとみなす) ことにすると，「全て同じ文字である」という条件は，「隣接する文字の xor を取ってできる文字列が全て $0$ である」と言い換えられる．つまり，元の文字列 $S$ に対して隣接 xor を取った文字列 $T$ を以下のように定めたとき， $T$ の全ての項が $0$ となるまでに必要な最小の操作回数を考えればよい．

$\displaystyle T_i=S_{i-1}\oplus S_{i}\quad(i=0,\ldots,|S|-1)$

ここで， $\oplus$ は xor 演算， $S _ {-1} = S _ {|S| - 1}$ とする．

$S$ に対する区間 flip 操作は， $T$ において，任意の $2$ 項を選択して flip する操作となる．従って，最小の操作回数は $T _ i = 1$ となる $i$ の個数を $2$ で割ったものに等しい． $T _ i = 1$ となる $i$ の個数が奇数だと困ったことになるが，実は必ず偶数になることが証明できる．厳密な証明は置いておくことにしてお気持ちを説明すると，円環 $S$ を $S _ 0$ を始点に時計回りに順番に見ていった場合に，仮に変化点が奇数個であれば，最後に $S _ 0$ に戻ってきたときに $S _ 0$ とは異なる文字を見ているはずなので矛盾する，という寸法である．

? を決め打ちした場合の答えが分かったので，元の問題を考える． $S$ の隣接項の関係のみが重要であるということが分かったので， $S _ {i - 1}, S _ i$ の答えへの寄与を各々考えると，次のようになる．ただし， $q$ は $S _ i =$ ? となる $i$ の個数である．

$S _ {i - 1}$	$S _ i$	寄与
$0$	$0$	$0$
$0$	$1$	$k\cdot 2^{kq}$
$0$	`?`	$k\cdot 2^{kq-1}$
$1$	$0$	$k\cdot 2^{kq}$
$1$	$1$	$0$
$1$	`?`	$k\cdot 2^{kq-1}$
`?`	$0$	$k\cdot 2^{kq-1}$
`?`	$1$	$k\cdot 2^{kq-1}$
`?`	`?`	$k\cdot 2^{kq-1}$

全てを説明していると冗長になるので最後のパターンだけ説明する． $S _ {i - 1} = S _ i =$ ? のとき，答えに正の寄与をもたらすのは $S _ {i - 1} = 0, S _ i = 1$ および $S _ {i - 1} = 1, S _ i = 0$ のケースであり，他の $kq - 2$ 個の ? の決め方はそれぞれ $2 ^ {kq-2}$ 通りずつある．従って，この場合の寄与は $2\cdot 2 ^ {kq-2} = 2 ^ {kq - 1}$ と計算できる．表で $k$ が掛かっているのは，文字列が $k$ 回繰り返されるためである．以上より，表に従って寄与の和を計算し，最後に $2$ で割ったものが答えである...

と言いたいところだが，実はコーナーケースが存在する． $S =$ ?, $K = 1$ の場合，上で説明した $S _ {i - 1} = S _ i =$ ? での議論が破綻する．というのは，最終的にできる円環において，先頭と末尾が同一項を指してしまうためである．このとき，先頭と末尾が異なるような ? への割り当ては存在しないので，答えへの寄与は $0$ となるはずである．しかし，表中の式に従って寄与を計算すると $1$ となり間違った答えを出してしまう．同様に $S=$ 0， $S=$ 1 のケースでも先頭と末尾の項が同一項を指すことになるが，この場合はもともと寄与が $0$ であったので不具合は起こらない．

$K\gt 1$ であったり，あるいは $|S|\gt 1$ であれば最終的にできる円環の長さが $2$ 以上となるのでこのようなことは起こらない．

実装 (Python)

以下は $P := 10 ^ 9 + 7$ として全体 $O(|S| + \log K + \log P)$ で動作する．

P = 10 ** 9 + 7

def solve(S: str, k: int):
    if S == '?' and k == 1:
        return 0

    ans = 0
    for prv, cur in zip(S[-1] + S, S):
        if prv == '?' or cur == '?':
            ans += 1
        elif prv != cur:
            ans += 2
    return ans * k * pow(2, k * S.count('?') - 2, P) % P

if __name__ == '__main__':
    S = input()
    k = int(input())
    print(solve(S, k))

短くしてみた (135 byte)．

S,K=input(),int(input())
print((K>(S=='?'))*sum([1,2*(b!=a)][b<'?'>a]for a,b in zip(S,S[-1]+S))*K*pow(2,S.count('?')*K-2,P:=10**9+7)%P)