ABC346 with Python (A～F)

今回は、初めてのQiita記事投稿がてら、ABC346のA-F問題までの解説をPythonで書いてみました。誰かのお役に立てれば幸いです。。。

A - Adjacent Product

問題

$N$ 個の整数 $A=(A_1,A_2,\cdots,A_N)$が与えられます。
また、$B_i = A_i \times A_{i+1} (1 \leq i \leq N-1)$ と定めます。
$B_1,B_2,\cdots,B_{N-1}$ をこの順に空白区切りで出力してください。

考察

隣り合っている要素同士の積を計算してリストに代入、それを答えとして表示する。

コード

A.py

N = int(input())
A = list(map(int, input().split())
B = []
for i in range(N - 1):
    B.append(A[i] * A[i + 1])
print(*B)

B - Piano

問題

無限に長いピアノの鍵盤があります。
この鍵盤内の連続する区間であって、白鍵 $W$ 個と黒鍵 $B$ 個からなるものは存在しますか？

文字列 wbwbwwbwbwbw を無限に繰り返してできる文字列を $S$ とおきます。

$S$ の部分文字列であって、$W$ 個の w と $B$ 個の b からなるものは存在しますか？

考察

今から長さ$W+B$の$S$の部分文字列を見ていくが、よく考えると、このときの始点はベースとなるwbwbwwbwbwbwのうちのどれかであることがわかる。文字列baseは、$i+L-1$が範囲外参照にならないよう、50回繰り返した。(この回数は適当)

コード

B.py

base = "wbwbwwbwbwbw"
LB = len(base)
base *= 50 # 範囲外参照防止
W, B = map(int, input().split())
L = W + B
for i in range(LB): # 始点の全探索
    targ = base[i : i + L]
    if targ.count("w") == W and targ.count("b") == B:
        print("Yes")
        exit()
print("No")

C - Σ

問題

長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ および正整数 $K$ が与えられます。

$1$ 以上 $K$ 以下の整数のうち、$A$ の中に一度も現れないものの総和を求めてください。

考察

もし$A$が空だとしても、$\sum_{i=1}^{K} i$を計算しようとすると、$K\leq2 \times 10^9$よりTLEする。よって、等差数列の和の公式を用いてこれを計算し、この中で$A$に含まれているものを後から引く、という形をとることにした。

コード

C.py

from collections import *
N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
ans = (K + 1) * K // 2 # 等差級数の和の公式
for key in cnt.keys():
    if 1 <= key <= K:
        ans -= key
print(ans)

D - Gomamayo Sequence

問題

0, 1 からなる長さ $N$ の文字列 $S$ が与えられます。

0, 1 からなる長さ $N$ の文字列 $T$ は以下の条件を満たすとき、またそのときに限り 良い文字列 であると定義します。

• $1 \leq i \leq N - 1$ を満たす整数 $i$ であって、$T$ の $i$ 文字目と $i + 1$ 文字目が一致するようなものがちょうど $1$ つ存在する。

$i = 1,2,\ldots, N$ について以下の操作を $1$ 度行うか行わないか選ぶことができます。

• $S$ の $i$ 文字目が 0 であるとき $S$ の $i$ 文字目を 1 に、そうでないとき $S$ の $i$ 文字目を 0 に置き換える。操作を行った場合、$C_i$ のコストがかかる。

$S$ を良い文字列にするために必要なコストの総和の最小値を求めてください。

考察

$i+1$文字目を$0,1$のどちらにしたらどうなるかについては、$i$文字目の数字と、今までで隣同士が一致した回数を知っていればわかる。したがって、

$dp[i][j][k]:=i$文字目まで見ていて、$i$文字目の値が$j$、今まで隣同士が一致した回数を$k$としたときのコストの総和の最小値

とすれば、答えは$min(dp[N][0][1], dp[N][1][1])$で求めることができる。

コード

D.py

INF = float("inf")
N = int(input())
S = list(input())
C = list(map(int,input().split()))
S = [int(s) for s in S]
dp = [[[INF] * 2 for _ in range(2)] for _ in range(N)]
if S[0] == 0:
    dp[0][0][0] = 0
    dp[0][1][0] = C[0]
else:
    dp[0][1][0] = 0
    dp[0][0][0] = C[0]
for i in range(N - 1):
    for j in range(2):
        if S[i + 1] == j:
            dp[i + 1][j][1] = min(dp[i + 1][j][1], dp[i][j][0])
            dp[i + 1][j ^ 1][1] = min(dp[i + 1][j ^ 1][1], dp[i][j][1] + C[i + 1])
            dp[i + 1][j ^ 1][0] = min(dp[i + 1][j ^ 1][0], dp[i][j][0] + C[i + 1])
        else:
            dp[i + 1][j ^ 1][0] = min(dp[i + 1][j ^ 1][0], dp[i][j][0])
            dp[i + 1][j ^ 1][1] = min(dp[i + 1][j ^ 1][1], dp[i][j][1])
            dp[i + 1][j][1] = min(dp[i + 1][j][1], dp[i][j][0] + C[i + 1])
ans = INF
for j in range(2):
    ans = min(ans, dp[-1][j][1])
print(ans)

E - Paint

問題

$H$ 行 $W$ 列のグリッドがあり、はじめすべてのマスは色 $0$ で塗られています。

これから $i = 1, 2, \ldots, M$ の順で以下の操作を行います。

$T_i = 1$ のとき、$A_i$ 行目のマスをすべて色 $X_i$ に塗り替える
$T_i = 2$ のとき、$A_i$ 列目のマスをすべて色 $X_i$ に塗り替える
すべての操作を終えたとき、最終的に色 $i$ で塗られたマスが存在するような各色 $i$ についてその色で塗られたマスの個数を求めてください。

考察

既に色が塗ってあったとしても、後から塗り替えられる可能性があるのがポイントっぽい。よって、簡単のためクエリを逆から見ていくことを考えてみる。このとき、例えばある行$A$を$X$で塗り替える時、前にこの行$A$を塗り替えていたなら無視すればいいし、そうでないなら前に塗られた列の種類数を今塗られるマス数から引けばよい。ある列$B$を$Y$で塗り替える時は、先ほどの議論の、行と列を逆にすればよい。

コード

E.py

from collections import *

H, W, M = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(M)]
memo = defaultdict(int)
cnt = [0] * 3
ans = defaultdict(int)
for t, a, x in reversed(query):
    if memo[t, a] == 1:
        continue
    if t == 1:
        ans[x] += W - cnt[2] # 前に塗られた列の種類数を引く
    else:
        ans[x] += H - cnt[1] # 前に塗られた行の種類数を引く
    memo[t, a] = 1
    cnt[t] += 1
res = []
tmp = 0
for key, val in ans.items():
    if key == 0:
        continue
    tmp += val
if H * W - tmp > 0:
    res.append((0, H * W - tmp))
keys = list(ans.keys())
keys.sort()
for k in keys:
    if k == 0 or ans[k] <= 0:
        continue
    res.append((k, ans[k]))
print(len(res))
for a, b in res:
    print(a, b)

F - SSttrriinngg in StringString

問題

長さ $n$ の文字列 $X$ に対して、$X$ を $k$ 回繰り返して得られる文字列を $f(X,k)$ と表記し、$X$ の $1$ 文字目、$2$ 文字目、$\dots$、$n$ 文字目を $k$ 回ずつこの順に繰り返して得られる文字列を $g(X,k)$ と表記します。
例えば、$X=$ abc のとき、$f(X,2)=$ abcabc、$g(X,3)=$ aaabbbccc です。
また、任意の文字列 $X$ に対して、$f(X,0)$ と $g(X,0)$ は共に空文字列です。

正整数 $N$ および文字列 $S,T$ が与えられます。
$g(T,k)$ が $f(S,N)$ の（連続とは限らない）部分列であるような最大の非負整数 $k$ を求めてください。
なお、定義より、$g(T,0)$ は常に $f(S,N)$ の部分列であることに注意してください。

考察

条件を満たすような最大の$k$を求める問題である。ここで、$k$が大きくなればなるほど条件を満たしづらくなるという性質があることから、二分探索を思いつく。
あとは、ある$k$が条件を満たすかどうかチェックするのを効率よく行うだけ。(ある文字が範囲$[l:r)$で何個出現するかは累積和を使って$O(1)$で求めた)

コード

F.py

import bisect

N = int(input())
S = input()
T = input()

alpha = [[0] for _ in range(26)]
for i in range(len(S)):
    s = S[i]
    for j in range(26):
        alpha[j].append(alpha[j][-1])
    alpha[ord(s) - ord("a")][-1] += 1

ng = 10**17 + 1
ok = 0
while ng - ok > 1:
    mid = (ok + ng) // 2
    idx = len(S)
    check = 0
    for t in T:
        K = mid
        targ = ord(t) - ord("a")
        tmp = alpha[targ][-1] - alpha[targ][idx]
        if tmp >= K:
            idx = bisect.bisect_left(alpha[targ], alpha[targ][idx] + K)
            continue
        K -= tmp
        cnt = alpha[targ][-1]
        if cnt == 0:
            print(0)
            exit()
        p, nokori = divmod(K, cnt)
        if nokori == 0:
            check += p
            idx = bisect.bisect_left(alpha[targ], alpha[targ][-1])
        else:
            check += p + 1
            idx = bisect.bisect_left(alpha[targ], nokori)
    if check <= N:
        ok = mid
    else:
        ng = mid
print(ok)