[ABC386] ABC 386(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

Posted at 2025-01-02

[ABC386] ABC 386(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

A問題

それぞれのカードの種類の枚数をカウントする cards 変数を使う．
フルハウスになるパターン
- 既に 3 枚セットができてる時
- 既に 2 枚セットが 2 つある時．

A.py

"""
<方針>
- それぞれのカードの種類の枚数をカウントする `cards` 変数を使う．
- フルハウスになるパターン
  - 既に `3` 枚セットができてる時
  - 既に `2` 枚セットが `2` つある時．
"""
# 入力
ABCD = list(map(int, input().split()))

# それぞれのカードの種類をカウントする変数
cards = [0]*(13+1)

# カウントする
for a in ABCD:
  cards[a] += 1

# 出力
if(cards.count(3) == 1):
  # 3枚セットがある
  print("Yes")
elif(cards.count(2) == 2):
  # 2枚セットが2つある時
  print("Yes")
else:
  # フルハウス不可能
  print("No")

B問題

文字を左から順番に見ていく．
- 現在の文字が "0" で，次の文字が存在し，次の文字が "0" のときは 2 つ先の文字を見る．
- それ以外は，次の文字を見る．
文字を見た回数を記録し，それを出力すれば良い．

B.py

"""
<方針>
- 文字を左から順番に見ていく．
  - 現在の文字が `"0"` で，次の文字が存在し，次の文字が `"0"` のときは `2` つ先の文字を見る．
  - それ以外は，次の文字を見る．
- 文字を見た回数を記録し，それを出力すれば良い．
"""
# 入力
S = list(input())

# 最小入力回数
ans = 0
# 現在の文字
i = 0
# 文字を左から順番に見ていく．
while i<len(S):
  # 現在の文字が `"0"` で，次の文字が存在し，次の文字が `"0"` のとき
  if(S[i] == "0" and i < len(S)-1 and S[i+1] == "0"):
    # 2つ先の文字を見る
    i += 2
  else:
    # 1つ先の文字を見る
    i += 1
  # 文字を見た回数
  ans += 1

# 出力
print(ans)

C問題

方針

計算量はそんな意識する必要がなさそう．
S と T をいい感じに比較すれば良さそう．
文字列の長さが一緒の時，
- それぞれの文字のうち，違う文字の数が 1 回以内のときは条件を満たす．
文字の長さが異なる時，
- 文字列の長さが 1 だけ違うとき，
  - 両方の文字列を手前から見ていく．
  - 文字が異なった時に，文字が少ない方の見る文字を一つ手前にする．
  - 最後まで文字を見るうちに，一つ手前を見るケースで最後まで問題なければ条件を満たす．
- 文字列の長さが 2 以上違う時，
  - 条件を満たさない．

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- 計算量はそんな意識する必要がなさそう．
- `S` と `T` をいい感じに比較すれば良さそう．
- 文字列の長さが一緒の時，
  - それぞれの文字のうち，違う文字の数が `1` 回以内のときは条件を満たす．
- 文字の長さが異なる時，
  - 文字列の長さが `1` だけ違うとき，
    - 両方の文字列を手前から見ていく．
    - 文字が異なった時に，文字が少ない方の見る文字を一つ手前にする．
    - 最後まで文字を見るうちに，一つ手前を見るケースで最後まで問題なければ条件を満たす．
  - 文字列の長さが `2` 以上違う時，
    - 条件を満たさない．
"""
# 入力
K = int(input())
S = input()
T = input()

# 文字列の長さが一緒の時
if len(S) == len(T):
  # 文字が異なった回数
  diff = 0
  for s, t in zip(S, T):
    # 文字が異なった時
    if s != t:
      # 回数をインクリメント
      diff += 1
  # 1回以内ならOK
  if(diff<=1):
    print("Yes")
  else:
    print("No")
# 文字列の長さが異なる時，
else:
  # len(S) < len(T) と設定する．
  if len(S) > len(T):
    S, T = T, S
  # 文字列の長さが1文字だけ違う．
  if len(S) + 1 == len(T):
    # 先読みしてる時1になる．
    diff = 0
    for i in range(len(S)):
      if S[i] != T[i+diff]:
        # まだ先読みしてない時，
        if diff == 0:
          # 先読みを開始
          diff = 1
          # 先読みした結果がダメならここで終了する．
          if S[i] != T[i+diff]:
            print("No")
            exit()
        else:
          # 既に先読みしてるので，NG
          print("No")
          exit()
    # 最後まで問題なし．
    print("Yes")
  # 文字列の長さが2以上違う．
  else:
    print("No")

D問題

なるべく左側に長めの黒を設置できれば良さそう．
左側から条件を見ていけるように sort する．
白色の条件 W は黒の長さを低くする条件に値するので，それを反映する．
黒色の条件 B は最低限欲しい黒色の長さになるので，それが，題の階段条件に違反しないかを確認する．

D.py

"""
<方針>
- なるべく左側に長めの黒を設置できれば良さそう．
- 左側から条件を見ていけるように `sort` する．
- 白色の条件 `W` は黒の長さを低くする条件に値するので，それを反映する．
- 黒色の条件 `B` は最低限欲しい黒色の長さになるので，それが，題の階段条件に違反しないかを確認する．
"""
# 入力
N, M = map(int, input().split())
XYC = []
for _ in range(M):
  X, Y, C = input().split()
  XYC.append([int(X), int(Y), C])

# 現在の黒の長さ
nowY = float("inf")
# 左から見れるようにsortしたものを閲覧していく．
for X, Y, C in sorted(XYC):
  # 白の条件のときは，
  if C=="W":
    # 長さを制限する．
    nowY = min(nowY, Y)
  # 黒条件のときは，
  else:
    # 長さが条件に違反しているかを確認する．
    if Y>=nowY:
      print("No")
      exit()

# 問題なければYes
print("Yes")

補足

関係するリンク(参考文献など)

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

あけおめことよろです．

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up