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

Posted at 2025-04-12

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

A問題

S を int で受け取る。
int で大小関係を考える。

A.py

"""
<方針>
- `S` を `int` で受け取る。
- `int` で大小関係を考える。
"""
# 入力
S = int(input())

# 200~299のとき
if(200 <= S <= 299):
  print("Success")
# それ以外のとき
else:
  print("Failure")

B問題

ログイン状態を保持する login 変数を利用する。
match 文で切り替えて処理する。

B.py

"""
<方針>
- ログイン状態を保持する `login` 変数を利用する。
- `match` 文で切り替えて処理する。
"""
# 入力
N = int(input())

login = False # ログイン状態を保持。初期はログインしていない。
ans = 0 # 認証エラーした回数。

for _ in range(N):
  # 入力分岐
  match input():
    # ログインする。
    case "login":
      login = True
    # ログアウトする。
    case "logout":
      login = False
    # プライベートページにアクセスする。
    case "private":
      # ログインしてなければ、
      if(not login):
        # 認証エラー
        ans += 1

# 出力
print(ans)

C問題

方針

毎回 K 個前のやつを全て足していては、N 回処理できず、O(NK) かかってしまう。
K 個前全てを足さずに、一個前がちょっと手前の部分を含んでいることを考える。
一個前と一個前を足すと（つまり、一個前の２倍）、K+1 個前を多く含んでいるだけになるので、それを減らしてあげれば良い。
ただし、N==K のときは最初に K 個前を全て足す状態なので、純粋に 1*K == K とすれば良い。
よって、O(N) として処理ができる。

前提

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

C.py

"""
<方針>
- 毎回 `K` 個前のやつを全て足していては、`N` 回処理できず、`O(NK)` かかってしまう。
- `K` 個前全てを足さずに、一個前がちょっと手前の部分を含んでいることを考える。
- 一個前と一個前を足すと（つまり、一個前の２倍）、`K+1` 個前を多く含んでいるだけになるので、それを減らしてあげれば良い。
- ただし、`N==K` のときは最初に `K` 個前を全て足す状態なので、純粋に `1*K == K` とすれば良い。
- よって、`O(N)` として処理ができる。
"""
# 入力
N, K = map(int, input().split())

# Aの値。
A = [None]*(N+1)

# 割る値
mod = 10**9

# 前から順番に計算する。
for i in range(N+1):
  if(i<K):
    # 普通に1
    A[i] = 1
  elif(i == K):
    # 前K個を足す。全て1なので、Kになる。
    A[i] = 1*K
  else:
    # 一個前の２倍からK+1個前を引けば良い。
    A[i] = (2*A[i-1] - A[i-(K+1)])%mod

# 出力
print(A[N])

D問題

大前提として、全てのパターンを列挙するにはあらゆるものがとても足りない。
まず、o の隣の ? は必ず . となる。
次に、既に o が足りていれば、? は全て . とする。
最後に、o を最大敷き詰めれる時を考えて、奇数のところは oxoxoxo のように埋める。

D.py

"""
<方針>
- 大前提として、全てのパターンを列挙するにはあらゆるものがとても足りない。
- まず、`o` の隣の `?` は必ず `.` となる。
- 次に、既に `o` が足りていれば、`?` は全て `.` とする。
- 最後に、`o` を最大敷き詰めれる時を考えて、奇数のところは `oxoxoxo` のように埋める。
"""
N, K = map(int, input().split())
S = list(input())
T = ["?"]*N

# 一旦自明なところを転写する。
for i in range(N):
  # "o"の左右は必ず"."になる
  if(S[i] == "o"):
    for dx in [-1, 1]:
      I = i + dx
      if(0<=I<N):
        T[I] = "."
  # "o" or "." はそのまま転写
  if(S[i] != "?"):
    T[i] = S[i]

# 既に"o"が十分足りている時、
if(T.count("o") == K):
  for i in range(N):
    if(T[i] == "?"):
      T[i] = "."

o_vague = 0 # "?"が偶数回連続しているところに打ち込める"o"の最大数
o_idx = [] # "?"が奇数回連続しているところに最大"o"を打ち込んだ時の位置
x_idx = [] # "?"が奇数回連続しているところに最大"o"を打ち込んだ時の"."の位置
q_start = None # qが連続し始めた位置
for i in range(N+1):
  if(
    # 番兵
    i < N and 
    # "?" のとき
    T[i] == "?"):
    if(q_start is None):
      q_start = i
  else:
    if(q_start is not None):
      # 奇数回連続
      if((i - q_start)%2 == 1):
        # 位置登録
        for j in range(q_start, min(i+1, N)):
          # 奇数番目
          if(j - q_start)%2 == 0:
            o_idx.append(j)
          # 偶数番目
          else:
            x_idx.append(j)
      # 偶数回連続
      else:
        o_vague += (i - q_start)//2
    q_start = None

# oを最大打ち込んでちょうどの時
if(len(o_idx) + T.count("o") + o_vague == K):
  # 奇数の場所は確定させる
  for i in o_idx:
    T[i] = "o"
  for i in x_idx:
    T[i] = "."

# 出力
print("".join(T))

補足

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

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
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