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

A問題

何色のボールが何個あるかを管理するリスト lsColor を作成する．
A の入力に対して， lsColor を更新していく．
それぞれの lsColor を 2 で割った時の商の合計値が捨てられる操作の最大値．

A.py

"""
<方針>
- 何色のボールが何個あるかを管理するリスト `lsColor` を作成する．
- `A` の入力に対して， `lsColor` を更新していく．
- それぞれの `lsColor` を `2` で割った時の商の合計値が捨てられる操作の最大値．
"""
# 入力
A1234 = list(map(int, input().split()))

# ボールを管理するリスト
lsColor = [0]*5
# A1~A4に対して処理を行う．
for A in A1234:
  # ボールを新しく登録する．
  lsColor[A] += 1

# 答え
ans = 0
for color in lsColor:
  # 2で割った時の商を答えに追加
  ans += (color//2)

# 出力
print(ans)

B問題

d を q で割ってみる．
- 余りが r であった時， d が答え．
- 余りが r より小さい時，余りを省いた分と r の和が答え．
- 余りが r より大きい時，余りを省いた分と q と r の和が答え．

B.py

"""
<方針>
- `d` を `q` で割ってみる．
  - 余りが `r` であった時， `d` が答え．
  - 余りが `r` より小さい時，余りを省いた分と `r` の和が答え．
  - 余りが `r` より大きい時，余りを省いた分と `q` と `r` の和が答え．
"""
# ゴミの種類
N = int(input())
# それぞれのゴミを捨てる日を記録する．
trash = [list(map(int, input().split())) for _ in range(N)]

# 質問の個数
Q = int(input())
for _ in range(Q):
  # 質問
  t, d = map(int, input().split())
  # ゴミの種類を記録しているlistは0-indexedなので
  t -= 1
  # ゴミを捨てる日の情報を取得
  q, r = trash[t]
  # 割ってみる
  di, mo = divmod(d, q)
  if(mo==r):
    ans = d
  if(mo<r):
    ans = di*q + r
  if(mo>r):
    ans = di*q + q + r
  # 質問の答え
  print(ans)

C問題

方針

毎回 A の配列を捜査してその数値が出たかどうかを確認すると， O(N^2) より TLE する．
今まででた値を O(1) で確認できる方法があれば良い．
- list を使うと， A が大きすぎて MLE の方向で良くない．
dict を使い， key を A の値とし， value を前回値が出た時の位置とすれば良い．
すると，全体では O(N) となって間に合う．

前提

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

C.py

"""
<方針>
- 毎回 `A` の配列を捜査してその数値が出たかどうかを確認すると， `O(N^2)` より `TLE` する．
- 今まででた値を `O(1)` で確認できる方法があれば良い．
  - `list` を使うと， `A` が大きすぎて `MLE` の方向で良くない．
- `dict` を使い， `key` を `A` の値とし， `value` を前回値が出た時の位置とすれば良い．
- すると，全体では `O(N)` となって間に合う．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 答え
ans = []
# 値が出たかどうかのdict
dic = dict()
# 位置と値を取得
for i, a in enumerate(A):
  # 値が既に発見されてる時
  if(a in dic):
    # 前回の位置を取得
    past = dic[a]
    # 位置を0-indexedを考慮して出力
    ans.append(past+1)
    # 位置を記録
    dic[a] = i
  # 値がまだ発見されてない時
  else:
    # 答えを-1とする．
    ans.append(-1)
    # 位置を記録
    dic[a] = i

# 出力
print(*ans)

D問題

計算量は気にするほど大きくない．実装できるかどうかである．
障害物が無いところ全てから始めて，順々に動いたところを盤面に記録していき， K 回移動したら，答えに追記する．
定数倍が怖いので，盤面 S を str ではなく， bool で管理し，多重リストでなく，一次元リストで管理する．

D.py

"""
<方針>
- 計算量は気にするほど大きくない．実装できるかどうかである．
- 障害物が無いところ全てから始めて，順々に動いたところを盤面に記録していき， `K` 回移動したら，答えに追記する．
- 定数倍が怖いので，盤面 `S` を `str` ではなく， `bool` で管理し，多重リストでなく，一次元リストで管理する．
"""
# 入力
H, W, K = map(int, input().split())
TT = [input() for _ in range(H)]

# 障害物があるところはFalseとして一次元リストで管理する．
S = []
for i in range(H):
  for j in range(W):
    S.append(TT[i][j] == ".")

# 再帰的に探索する関数
def rec(y, x, k, S):
  # 上下左右への移動
  for dy, dx in [
    (1, 0), 
    (0, 1), 
    (-1, 0), 
    (0, -1)
    ]:
      # 移動先の座標
      Y = y+dy
      X = x+dx
      # 枠内に収まってる時
      if(0<=Y<H and 0<=X<W):
        # 一次元に直した時のインデックス
        tar = Y*W + X
        # 障害物がなくて，まだ歩いてない時
        if(S[tar]):
          # 現在の盤面のコピーをとる．
          T = S[:]
          # 今の位置を歩いたところとして記録する．
          T[tar] = False
          # 歩いた回数がKに達した時
          if(k+1 == K):
            # 答えに追記する．
            global ans
            ans += 1
          # 歩いた回数がKに達さない時，
          else:
            # 再帰的に歩み進める
            rec(Y, X, k+1, T)

# 答え
ans = 0
# 全ての位置からスタートできるかを確認する．
for i in range(H):
  for j in range(W):
    # 一次元に直した時のインデックス
    tar = i*W + j
    # 障害物でない時，
    if(S[tar]):
      # 盤面のコピーをとる．
      T = S[:]
      # 現在の位置を歩いたところとして記録する．
      T[tar] = False
      # 再帰的に歩み始める．
      rec(i, j, 0, T)

# 出力
print(ans)

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

おねむねむ．やらなきゃいけないことをやってなくてやばい．