ABC解説

ABC346 B問題の解説（Python）

はじめに

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

今回はABC346のB問題を解説していきます。

ABC346　B – Piano

問題

問題

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

制約

  • \(0 \leqq W,B \leqq 100 \)
  • \(W+B \geqq 1 \)

思考の筋道

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

ピアノの鍵盤は周期12（”wbwbwwbwbwbw”）でループします。そのため、部分文字列の開始位置として考えられるのは12パターンです。

部分文字列の開始位置からW+B個の文字を調べ、その結果、白鍵の数がW個、黒鍵の数がB個となるかどうかを調べましょう。

12パターンの開始位置に対して、1つでも白鍵の数がW個、黒鍵の数がB個となるものがあればYes、1つもなければNoとなります。

なお、無限に長いピアノの表現方法ですが、下のコードのように余りを活用するか、あるいは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")

リンク

ABC346