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

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

# A問題
- `最初の空き箱の数` + `経過した日数`

```A.py
"""
<方針>
- `最初の空き箱の数` + `経過した日数`
"""
# 入力
N, D = map(int, input().split())
S = input()

# 最初の空き箱の数 + 経過した日数
ans = S.count(".") + D

# 出力
print(ans)
```

# B問題

- シミュレーションして愚直に解く．
- `D` 日，一番右のクッキー `@` を空箱 `.` にする．
- `S` を書き換え可能にするため，`list` で受け取る．
```B.py
"""
<方針>
- シミュレーションして愚直に解く．
- `D` 日，一番右のクッキー `@` を空箱 `.` にする．
- `S` を書き換え可能にするため，`list` で受け取る．
"""
# 入力
N, D = map(int, input().split())
S = list(input())

# D日シミュレーション
for _ in range(D):
  # 右から順番に見る
  for i in reversed(range(N)):
    # クッキーがあったら
    if(S[i] == "@"):
      # クッキーを食べて空箱にする．
      S[i] = "."
      # 次の日に行く
      break

# 出力
print("".join(S))
```

# C問題
## 方針
- 流れてきた寿司を誰が食べるかを順番に見ていては，`O(N^2)` かかってしまい，間に合わない．
- `A` の情報から，あらかじめ特定の美味しさの寿司は誰が食べるかのリスト `who_eat` を計算しておく．`O(N)`
  - 既に食べられている美味しさ `min_taste` を用いると `O(N)` でできそう．
- あとは，計算しておいたリスト `who_eat` を用いて全ての `B` の値について計算すると `O(N)` で処理ができる．
- 全体として，`O(N)` で処理ができた．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 流れてきた寿司を誰が食べるかを順番に見ていては，`O(N^2)` かかってしまい，間に合わない．
- `A` の情報から，あらかじめ特定の美味しさの寿司は誰が食べるかのリスト `who_eat` を計算しておく．`O(N)`
  - 既に食べられている美味しさ `min_taste` を用いると `O(N)` でできそう．
- あとは，計算しておいたリスト `who_eat` を用いて全ての `B` の値について計算すると `O(N)` で処理ができる．
- 全体として，`O(N)` で処理ができた．
"""
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 想定される美味しさの最大値+1
MAX = 2*10**5 + 1

# 誰が食べるかのリスト
## index: 美味しさ
## value: 誰が食べるか
who_eat = [-1]*MAX

# 既に食べられた最低の美味しさ
min_taste = MAX
# 手前の人から美食度をみる
for i, a in enumerate(A):
  # 未だに誰も食べたことのない低い美味しさの場合
  if(a<min_taste):
    # その人間が食べることを示していく．
    while min_taste != a:
      # 最低の美味しさを更新
      min_taste -= 1
      # 誰が食べるかを記録
      who_eat[min_taste] = (i + 1)

# 誰が食べるかを出力
for b in B:
  # 答え
  print(who_eat[b])
```

# D問題

- 頑張って再帰で実装する．
- 左の値から考えて，次の値はどこまでありえるかを考えればいける．
```D.py
"""
<方針>
- 頑張って再帰で実装する．
- 左の値から考えて，次の値はどこまでありえるかを考えればいける．
"""
# 再帰のおまじない
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
import sys
sys.setrecursionlimit(10**6)

# 入力
N, M = map(int, input().split())

# 再帰
def rec(ANS):
  # 現在の一つあたりの長さ
  n = len(ANS[0])
  # 目的の長さになったら終了
  if n == N:
    return ANS
  else:
    # 戻り値
    RET = []
    # 入力値を一つずつ見る
    for ans in ANS:
      # 次の値を考える
      for new in range(ans[-1]+10, M-10*(N-n-1)+1):
        # 次の値を加えたものを追加する．
        RET.append(ans[:] + [new])
    # さらなる次を追加してもらったものが答え
    return rec(RET)

# 再帰の実行．
ANS = rec([[x] for x in range(1, M-10*(N-1)+1)]) # 初期値は[[1], [2], ...[M-10*(N-1)]]

# 出力
print(len(ANS))
for ans in ANS:
  print(*ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc382)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc382/submissions/60464596)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc382/submissions/60464683)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc382/submissions/60465075)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc382/submissions/60465476)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- とある友人へ．「謝　罪　の　何　様」でしたね．すみません．