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

# [ABC385] ABC 385(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)

# A問題
- `3` グループに分ける方法と `2` グループに分ける方法を全て試す．
- どの篩にもかからなかったら `No` を出力すれば良い．
```A.py
"""
<方針>
- `3` グループに分ける方法と `2` グループに分ける方法を全て試す．
- どの篩にもかからなかったら `No` を出力すれば良い．
"""
# 入力
A, B, C = map(int, input().split())

if(A==B==C): # 3グループ
  print("Yes")
elif(A+B==C): # 2グループ
  print("Yes")
elif(B+C==A): # 2グループ
  print("Yes")
elif(C+A==B): # 2グループ
  print("Yes")
else: # どの篩にもかからなかったとき
  print("No")
```

# B問題
- シミュレーションを行う．
  - 常にサンタの位置を保持する変数 `santa` を持っておく．
  - 巡回した家の数は逐次 `ans` に保存しておく．
  - 通行済みのお家は `@` から `.` に変化させれば，重複はなくなる．
- `0-indexed` に注意
- 下方向が `x`，右方向が `y`であることに注意．
```B.py
"""
<方針>
- シミュレーションを行う．
  - 常にサンタの位置を保持する変数 `santa` を持っておく．
  - 巡回した家の数は逐次 `ans` に保存しておく．
  - 通行済みのお家は `@` から `.` に変化させれば，重複はなくなる．
- `0-indexed` に注意
- 下方向が `x`，右方向が `y`であることに注意．
"""
# 入力
H, W, X, Y = map(int, input().split())
SS = [list(input()) for _ in range(H)]
T = input()
# サンタがどの位置にいるか．
santa = [X-1, Y-1] # 初期位置は[X-1, Y-1]
# 巡回した家の数
house = 0

# シミュレーション
for t in T:
  # サンタの現在地を取得
  x, y = santa
  # サンタを移動させる
  match t:
    case "U":
      x -= 1
    case "D":
      x += 1
    case "L":
      y -= 1
    case "R":
      y += 1
  
  # 移動先が枠内のときのみ考える
  if(0<=x<H and 0<=y<W):
    # サンタの移動先の状態
    match SS[x][y]:
      # 通過可能
      case ".":
        # 座標を更新
        santa = [x, y]
      # 通過不可能
      case "#":
        # 座標は更新せず
        continue
      # お家
      case "@":
        # 座標を更新
        santa = [x, y]
        # 重複しないように，ただの通過可能な位置に変換
        SS[x][y] = "."
        # 巡回した家の数を増やす
        house += 1

# 出力
print(santa[0]+1, santa[1]+1, house)
```

# C問題
## 方針
- それぞれの建物を使うか使わないかの `bit` 探索を行うと，それだけで `O(2^N)` かかってしまい，絶対に `TLE`．
- 現実的なラインとして，`O(N^2)` でなんとかする方法を考える．
- 建物をどの間隔で選択するかで `O(N)`．
- 建物をどこから選ぶかと，それを実際に見ていく処理が `O(N)` になりそう．
- 全体として，`O(N^2)` で処理ができそう．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- それぞれの建物を使うか使わないかの `bit` 探索を行うと，それだけで `O(2^N)` かかってしまい，絶対に `TLE`．
- 現実的なラインとして，`O(N^2)` でなんとかする方法を考える．
- 建物をどの間隔で選択するかで `O(N)`．
- 建物をどこから選ぶかと，それを実際に見ていく処理が `O(N)` になりそう．
- 全体として，`O(N^2)` で処理ができそう．
"""
# 入力
N = int(input())
H = list(map(int, input().split()))

# 答え．最悪建物一つを選べばいいので，初期値は1
ans = 1
# i: どの間隔で建物を選ぶか
for i in range(1, N):
  # j: どの建物から選ぶか
  for j in range(0, i):
    # 解候補
    tmp = 0
    # 現在の建物の高さ．初期値はどれにも該当しない-1
    h = -1
    # k: 建物を見ていく
    for k in range(j, N, i):
      # 建物が一緒であれば
      if(H[k] == h):
        # 数を増やす
        tmp += 1
      # 建物が異なれば
      else:
        # 答えを更新
        ans = max(ans, tmp)
        # 建物の高さを更新
        h = H[k]
        # 建物の数を更新
        tmp = 1
    # 答えを更新
    ans = max(ans, tmp)

# 出力
print(ans)
```


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