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

# [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回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`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)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc378)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc378/submissions/59403148)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc378/submissions/59403538)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc378/submissions/59403729)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc378/submissions/59403965)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- おねむねむ．やらなきゃいけないことをやってなくてやばい．