ABC346 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC346

A – Adjacent Product

問題

A問題

N個の整数が与えられます。隣接する2数の積を順に表示していく問題です。

思考の筋道

繰り返し文で、インデックス i の数とインデックス i + 1 の数の積を求めます。インデックスの動く範囲に注意しましょう。

コード

N = int(input())
A = list(map(int, input().split()))

l = []
for i in range(N - 1):
    l.append(A[i] * A[i + 1])
print(*l)

B – Piano

問題

B問題

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

思考の筋道

周期性がテーマの問題です。

ピアノの鍵盤は周期12（”wbwbwwbwbwbw”）でループします。そのため、切り取る区間の開始位置は12パターンだけ考えれば良いです。

12パターンの切り取りに対して、wとbの数が入力値と等しくなるか調べましょう。

なp、無限に長いピアノの表現方法ですが、下のコードのように余りを活用するか、あるいはWとBが100以下なので、その調べに足るだけの有限な長さのピアノを考えればよいでしょう。

コード

W, B = map(int, input().split())

s = "wbwbwwbwbwbw"
for i in range(12):
    w, b = 0, 0
    for j in range(W + B):
        if s[(i + j) % 12] == 'w':
            w += 1
        else:
            b += 1
    if W == w and B == b:
        print("Yes")
        exit()
print("No")

C – Σ

問題

C問題

正整数列Aと整数Kが与えられます。1以上K以下の整数のうち、Aの中に一度も現れないものの総和を求める問題です。

思考の筋道

正整数列Aの長さは2×10^5以下、Kの大きさは2×10^9以下です。

1〜Kのループを回すとTLEになります。

そこで、Aの中に一度も現れない数の総和を直接求めるのではなく、反対に、1〜K全体の総和からAに現れた数を引くことを考えましょう。全体の総和は、等差数列の和の公式（(初項+末項)×項数÷2）で求められます。

この方法であれば、Aに関するループのみなので時間内に解くことができます。

コード

N, K = map(int, input().split())
A = set(map(int, input().split()))

sum = K * (K + 1) // 2
for num in A:
    if num <= K:
        sum -= num

print(sum)

D – Gomamayo Sequence

問題

D問題

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

Sに操作を行い、一箇所のみ0か1が隣接し、それ以外の箇所は0と1が交互に並ぶ「良い文字列」にしたいです。（例：0100101）

操作とは、i文字目の0と1を反転させることです。それぞれのiに対し、この反転操作のコストが決まっています。

Sを「良い文字列」にするために必要なコストの総和の最小値を求める問題です。

思考の筋道

遷移性のある問題であり、最大値・最小値・個数を求める問題にも該当します。DP（動的計画法）が使えるのではないでしょうか。

私は遷移を調べるにあたり、各文字について、最終文字が0と1のどちらかと、それまでに隣接が発生したかしていないかで、4種類の値を管理すれば良いと考えました。

i：何文字目か
j：i文字目が0か1か
k：i文字目までに隣接発生済みかどうか
dp[i][j][k]：この条件でのコストの最小値

これをもとに、4種類の漸化式を作成しましょう。

なお、DPの組み立て方のパターンは、この解法の他にも色々あるはずです。

コード

N = int(input())
S = input()
C = list(map(int, input().split()))

dp = [[[INFTY] * 2 for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 0
dp[0][1][0] = 0

for i in range(N):
    if S[i] == "0":
        dp[i + 1][0][0] = dp[i][1][0]
        dp[i + 1][1][0] = dp[i][0][0] + C[i]
        if i >= 1:
            dp[i + 1][0][1] = min(dp[i][1][1], dp[i][0][0])
            dp[i + 1][1][1] = min(dp[i][0][1], dp[i][1][0]) + C[i]
    else:
        dp[i + 1][0][0] = dp[i][1][0] + C[i]
        dp[i + 1][1][0] = dp[i][0][0]
        if i >= 1:
            dp[i + 1][0][1] = min(dp[i][1][1], dp[i][0][0]) + C[i]
            dp[i + 1][1][1] = min(dp[i][0][1], dp[i][1][0])

print(min(dp[N][0][1], dp[N][1][1]))