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

はじめに

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

参加者はレーティングによってランク分けされます。私は8ランクあるうち、下から2番目のランク（茶色）のため、まだまだひよっこです。一つ上のランク（緑色）を目指して、現在精進しています。

ABCでは毎回8題の問題が出題され、後半の問題ほど、難易度が高くなります。ここでは私が戦える前半4題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC289

A – flip

問題

A問題

文字列の0と1を反転させる問題です。

解説

文字列を一文字づつ反転させていくのみです。

コード

s = input()

ans = ""
for char in s:
    if char == "0":
        ans += "1"
    else:
        ans += "0"

print(ans)

B – レ

問題

B問題

漢文のレ点をテーマとした問題です。レ点が与えられている文字列に対し、どの順番に文字を読むかを答えます。

解説

私はこの問題に非常に苦戦しました。コンテスト中は、先にC問題とD問題が解けたくらいです。B問題にしてはちょっと難しくないですかね……。

解答用の配列ansと一時保存用のスタックdを準備します。

文字をスタックdに詰める
その文字の位置にレ点がある場合は次の文字へ
その文字の位置にレ点がない場合はスタックの全中身をpopし、ansに格納し、次の文字へ

この繰り返しで解くことができます。
スタックの後から入れた要素が先に取り出される性質（LIFO）を利用しています。

コード

from collections import deque
N, M = map(int, input().split())
A = set(map(int, input().split()))

ans = []
d = deque() # レ点でない整数に当たるまで一時保存

for i in range(1, N + 1):
    d.append(i)
    if i not in A:
        while d:
            ans.append(d.pop())

print(*ans)

C – Coverage

問題

C問題

いくつかの集合が与えられ、対象の要素全体を被覆する集合の組み合わせは何通りあるかを考える問題です。

解説

この問題のポイントは条件から、集合が10個以下である点です。M個の集合から1個以上の集合を選ぶ組合せは2^M – 1通りしかありません。（2^Mは、M個の集合について、使う/使わないの2通りの選択肢があるため）

M=10の場合でも1023通りしかなく、この程度であれば、全て調べ上げることができます。ただし、M重のfor文は作りたくありませんので、このような時にはbit全探索という手法を用います。

（bit全探索の分かりやすい記事はたくさんあるため、ここでは説明を省きます。）

コード

N, M = map(int, input().split())
l = []
for i in range(M):
    c = int(input())
    s = set(map(int, input().split()))
    l.append(s)

count = 0
# bit全探索
for i in range(2 ** M):
    s = set()
    for j in range(M):
        if (i >> j) & 1:
            s = s.union(l[j])
    if len(s) == N:
        count += 1

print(count)

D – Step Up Robot

問題

D問題

階段昇りをテーマにした問題です。跳べる段数は複数パターンあり、また、特定の段は昇れない設定もあります。

解説

昇る前後の関係が重要ですので、動的計画法（DP）を考えるのが自然でしょうか。下の段から順に、その段に昇ることができるかどうかをメモしていくことで、解くことができます。

ABCではこのような動的計画法の問題がたくさん出ます。

（動的計画法についても分かりやすい記事はたくさんあるため、ここでは説明を省きます。ただ、私も近日中に動的計画法の記事を書きたいと考えています。）

コード

N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))
X = int(input())

# 動的計画法
# dp[i]:i段目に登ることができるなら1、できないなら0
dp = [0] * (X + 1)
dp[0] = 1

for i in range(1, X + 1):
    if i not in B:
        for num in A:
            if i - num >= 0 and dp[i - num] == 1:
                dp[i] = 1

if dp[X] == 1:
    print("Yes")
else:
    print("No")