AtCoder ABC415 振り返り(ほぼ緑コーダーがPythonでABC問題)

ABC415を振り返ります

今回はABCまで3問解答でした。

C問題にかなり手間取りまして、正解まで80分かかった上に4回誤答しております...（3回WA, 1回TLE/MLE/WA）。解法は深さ優先探索で良かったのですけども、PyPyは再帰が遅いのを忘れていたり、細かい条件を書ききれなかったりしてしまって、WAを出しまくっていました...。

レーティングは微減です。次は緑復帰を目指したい。

A - Unsupported Type

配列の中から特定の数があるのかをチェックします。

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

# X があればYes
for i in range(N):
    if A[i] == X:
        print("Yes")
        exit()
print("No")

if X in A と書くと、より短く書けます。

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

# X があればYes
print("Yes" if X in A else "No")

B - Pick Two

Sの中から"#"を探して、もし存在すれば"."に変換する...という操作を "#" がなくなるまで行います。

S = list(input())

answers = []
exist = True

# "#"が存在するならループ
while exist:
    exist = False

    # "#" 2個の位置を記録
    pos1 = 0
    pos2 = 0
    for i in range(len(S)):
        # "#"があれば"."に置換
        if S[i] == "#":
            S[i] = "."
            pos1 = i+1
            exist = True
            break
    for i in range(len(S)):
        if S[i] == "#":
            S[i] = "."
            pos2 = i+1
            exist = True
            break
    if pos1 > 0:
        answers.append((pos1,pos2))
    else:
        break

for i in range(len(answers)):
    ans = answers[i]
    print(str(ans[0]) + "," + str(ans[1]))

C - Mixture

深さ優先探索(DFS)を使用して解きました。（3回WA, 1回TLE/MLE/WA）

Pythonの場合、基本的に Python (PyPy 3.10-v7.3.12) の実行速度が速いです。しかし、再帰関数を使う時は、メモリを使いすぎたり処理が遅かったりするので、この場合は Python (CPython 3.11.4) を使いましょう。

---

また、この問題は文章の理解が難しかったような...。

・状態 13 = 1101(2) は薬品 1,3,4 が混ざった状態
・S の i 文字目が 1 であるとき、状態 i は 危険 である。

このあたり、「ちょっと何言ってるかわかんないですね」状態になりました...。

visited_set = set()
added_set = set()
success = False

# 深さ優先探索(現在地と2進数での桁数)
def dfs(value, digit):
    global success

    # 桁が全部1で埋まったら、終了
    if value == 2**digit - 1:
        success = True
        return

    # 次の状態に移行
    for i in range(digit):
        # 次の状態(現在値に2のi乗を足すことで、薬品を一つ入れる)
        next = value + 2**i

        # 既に追加した薬品かチェック
        if 2**i in added_set:
            continue
        # 値がオーバチェック
        if next > 2**digit - 1:
            continue
        # 危険な状態チェック
        if S[next-1] == "1":
            continue 
        # 既にチェックした値か
        if next in visited_set:
            continue

        visited_set.add(next)
        added_set.add(2**i)
        dfs(next, digit)

        # 戻ってきたら、入れた薬品を戻す(他の箇所に影響を出さないため)
        added_set.discard(2**i)


T = int(input())
for i in range(T):
    # 各テストケースで実行
    N = int(input())
    S = input()

    visited_set = set()
    added_set = set()
    success = False

    # (空の状態、N桁)でDFSを実行
    dfs(0, N)
    print("Yes" if success else "No")

D - Get Many Stickers (解説AC)

D問題は解説を読んで復習しました。ポイントは以下ですかね...

・交換で減る数(A-B)が小さい順に、交換できるだけ交換する
・交換回数 x は、 (空き瓶の数) - (交換で減る数) * x >= A を満たす

ポイントが分かれば解ける問題ですが、コンテスト中に思いつくのは時間がかかりそうです...。（実際、自分で解こうとしたらあれこれ考えしてしまってうまく出来なかった）

N, M = map(int, input().split())

# A,Bと 差(A-B)を保存
diff_list = [] 
for i in range(M):
    A, B = map(int, input().split())
    diff = A - B
    diff_list.append((diff, A, B))

# 交換の差が小さい順にソート
diff_list.sort()

count = 0
bin_count = N # 残りの瓶の個数

# 交換の差が小さい順に、交換できるだけ交換する
for i in range(len(diff_list)):
    diff, a, b = diff_list[i]

    if bin_count >= a:
        # bin_count - diff * change_count >= a まで交換できる
        change_count = (bin_count - a) // diff + 1
        bin_count = bin_count - diff * change_count

        count += change_count

print(count)