AtCoder ABC386 復習(緑コーダーがPythonでA〜D問題まで)

ABC 386 感想まとめ

AtCoder Beginner Contest 386 - AtCoder

2024年最後のABC。何故か上振れして、個人的に半年ぶり2度目の水色パフォが出ました。

C問題は場合分けして力技で解きました。D問題は、過去問で類題があったような記憶があります。

なんか偶然解きやすい問題が出て、棚ぼた的に水色パフォが出たような気もします。ただ、おかげさまで2024年を緑色に復帰して終わることができ、綺麗な年末になったと思います。ありがとうございました。

---

2024年のグラフ

A - Full House 2

「4枚の中に、2種類のみ存在していればフルハウスの可能性がある」と考えられれば、良いと思います。

解答はdictonaryで解いていますが、setのほうが良かったかも。listからの変換が楽ですし。

from collections import defaultdict

A = list(map(int, input().split()))
dict = defaultdict(int)

for i in range(4):
    dict[A[i]] += 1

# 札の種類が2種類なら、フルハウスが作れる
if len(dict.keys()) == 2:
        print("Yes")
        exit()

print("No")

B - Calculator

"00"のときだけ2文字分を1プッシュで入力できるので、文字列の先頭から走査して"00"のときだけ場合分けする感じでした。

S = input()

count = 0
index = 0

while index < len(S):
    if S[index] == "0" and index + 1 < len(S) and S[index + 1] == "0":
        # "00"のとき
        count += 1
        index += 2
    else:
        # 普通の数字のとき
        count += 1
        index += 1

print(count)

C - Operate 1

この問題は F 問題の部分問題とのこと。できる人はF問題を解いてそのコードをC問題にも使うのでしょうけども、庶民には無理なのでC問題限定で解きます。

文字列長で場合分けして考えました。

• S,T の長さが同じ の場合
  • 異なる文字が1個以下ならYes. そうでないならNo.
• S,T の長さが1文字分だけ異なる場合
  • 異なる文字を探す。異なる文字以外の部分が一致していればYes、そうでないならNo
• S,T の長さが2文字分以上異なる場合
  • No

K = int(input())
S = input()
T = input()

# 長さが同じ場合
if len(S) == len(T):
    # 異なる文字が 0個 or 1個なら Yes
    diff_count = 0
    for i in range(len(S)):
        if S[i] != T[i]:
            diff_count += 1
    if diff_count > K:
        print("No")
    else:
        print("Yes")
    exit()

shorter = S if len(S) < len(T) else T
longer = S if len(S) > len(T) else T

# S,T 長さが２文字以上異なる場合はNo
if len(longer) - len(shorter) != 1:
    print("No")
    exit()

# 異なる文字の位置を探す
diff_index = -1
for i in range(len(shorter)):
    if S[i] != T[i]:
        diff_index = i
        break

if diff_index == -1:
    print("Yes")
    exit()

# 異なる文字以外の部分が一致していればYes、そうでないならNo
if shorter[:diff_index] == longer[:diff_index] and shorter[diff_index:] == longer[diff_index + 1:]:
    print("Yes")
else:
    print("No")

D - Diagonal Separation

まず、最小の黒領域は何なのか...を求めます。コードでは black_border_dict という変数に情報をもたせます。

あとは、白マスが、黒領域のボーダーラインより下に位置するかどうか...を、白マス1つ1つ調べていけば大丈夫です。白マスのある列に対応するボーダーラインはどこか...を求めるときは、2分探索を使っています。

図なしでは説明が難しい...

この問題文では X=行・Y=列 になっており、通常のX軸・Y軸とは向きが異なるため、混乱しがちです。そのため、プログラムでは 行=row, 列=col と変数名を統一して、混乱を避けるようにしました。

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

black_cr = []
white_cr = []
for i in range(M):
    row, col, C = input().split()
    row = int(row)
    col = int(col)
    if C == "B":
        black_cr.append((col, row))
    else:
        white_cr.append((col, row))

black_cr.sort()
white_cr.sort()

# 黒の最小の領域を求める
black_border_dict = defaultdict(int)
black_cr_reverse = black_cr[::-1] # 座標系の右側から探索するため、配列を逆転させる
current_max = 0
for i in range(len(black_cr_reverse)):
    col, row = black_cr_reverse[i]
    if row > current_max:
        black_border_dict[col] = row
        current_max = row

# 2分探索しやすいように、右端の値を入れておく
black_border_dict[10**10] = 0

# 各 白マスが、黒領域のボーダーラインより下にあるかを判定する
black_border_change_cols = list(black_border_dict.keys())
black_border_change_cols.sort()
for i in range(len(white_cr)):
    # 白マスの列に対応する、ボーダーラインを求める
    wcol, wrow = white_cr[i]
    border_index = bisect.bisect_left(black_border_change_cols, wcol)
    border_value = black_border_dict[black_border_change_cols[border_index]]

    # white の行が、黒領域のボーダーラインより上にあったらNo
    if wrow <= border_value:
        print("No")
        exit()

print("Yes")