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

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

# A問題

- シミュレーションをしよう．
- あらかじめ数値は受け取っておく．
- 時間 `t` を `1` ~ `100` で遷移させて，💧を入れてみる．
- 💧 `water` を毎時蒸発させる．💧 `water` がマイナスにならないように注意．
```A.py
"""
<方針>
- シミュレーションをしよう．
- あらかじめ数値は受け取っておく．
- 時間 `t` を `1` ~ `100` で遷移させて，💧を入れてみる．
- 💧 `water` を毎時蒸発させる．💧 `water` がマイナスにならないように注意．
"""
# 入力
N = int(input())
TV = [list(map(int, input().split())) for _ in range(N)]

look = 0 # 現在参照してるTVのindex
water = 0 # 現在の💧の量
# シミュレーション
for t in range(1, 100+1):
  # 現在参照してるTVの値
  T, V = TV[look]
  # 💧を追加するとき
  if(t == T):
    # 水を追加する
    water += V
    # 参照するindexをインクリメントする
    look += 1
    # 全ての水を入れ終わったら
    if (look == N):
      # 終了
      break
  # 💧を蒸発させる
  if(water>0):
    water -= 1

# 出力
print(water)
```

# B問題
- 実際に加湿器を置く全パターンを試して，一番良かったのを出力しよう．
- 地獄の `for-loop` を実装しよう！！
- `0-indexed` に注意しよう．
```B.py
"""
<方針>
- 実際に加湿器を置く全パターンを試して，一番良かったのを出力しよう．
- 地獄の `for-loop` を実装しよう！！
- `0-indexed` に注意しよう．
"""
# 入力
H, W, D = map(int, input().split())
SS = [input() for _ in range(H)]

# 加湿器を一つA(y, x)の位置に置いた時に加湿される面積を計算する関数．
def area(A):
  y, x = A
  cnt = 0
  # 全ての場面を見る
  for i in range(H):
    for j in range(W):
      # 床のとき
      if(SS[i][j] == "."):
        # 加湿器が届く範囲のとき
        if(abs(i-y)+abs(j-x)<=D):
          cnt += 1
  return cnt

ans = 0 # 一番良かったパターン
# 全てのパターンを試す．加湿器をそれぞれ A(iA, jA) B(iB, jB) とおく．
for iA in range(H):
  for jA in range(W):
    for iB in range(H):
      for jB in range(W):
        # 両方とも床である必要がある．
        if(SS[iA][jA] == ".") and (SS[iB][jB] == "."):
          tmp = 0 # 加湿された床の数
          # どの床が加湿されるかを見る．
          for i in range(H):
            for j in range(W):
              # 対象が床である．
              if(SS[i][j] == "."):
                # Aによって加湿される or Bによって加湿される
                if(abs(iA-i)+abs(jA-j)<=D) or (abs(iB-i)+abs(jB-j)<=D):
                  tmp += 1
          # 答えを更新
          ans = max(ans, tmp)

# 出力
print(ans)
```

# C問題
## 方針
- 加湿器を一つずつがどの範囲加湿できるかを見てしまうと，加湿器の個数分 `O(HW)` x 加湿距離 `O(HW)` で `O(H^2W^2)` かかってしまう．
- 加湿器を同時に見て，どのくらい加湿範囲を広げられるかを見れば `O(HW)` で済みそう．
- 加湿度というイメージを使って実装する．
  - 加湿器が置かれてるの加湿度を `D+1` とする．
  - 上下左右を見て，`0 ~ 自分の加湿度-1` のところは， `自分の加湿度-1` を伝搬させて，(仮想の)加湿器を置いて繰り返し行う．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 加湿器を一つずつがどの範囲加湿できるかを見てしまうと，加湿器の個数分 `O(HW)` x 加湿距離 `O(HW)` で `O(H^2W^2)` かかってしまう．
- 加湿器を同時に見て，どのくらい加湿範囲を広げられるかを見れば `O(HW)` で済みそう．
- 加湿度というイメージを使って実装する．
  - 加湿器が置かれてるの加湿度を `D+1` とする．
  - 上下左右を見て，`0 ~ 自分の加湿度-1` のところは， `自分の加湿度-1` を伝搬させて，(仮想の)加湿器を置いて繰り返し行う．
"""
H, W, D = map(int, input().split()) # 入力
SS = [] # 盤面
HH = [] # (仮想の)加湿器の位置
for i in range(H):
  _S = input() # 入力
  S = []
  for j in range(W):
    s = _S[j]
    # 初期加湿度を設定
    match s:
      # 机
      case "#":
        # 加湿されないし移動できない．
        S.append(-1)
      # 床
      case ".":
        # 加湿されていない．
        S.append(0)
      # 加湿器
      case "H":
        # 加湿度をD+1とする
        S.append(D+1)
        # 加湿器の位置を保存する
        HH.append([i, j])
  SS.append(S)

# 加湿器を同時に見て加湿させていく
for d in reversed(range(1, D+1)):
  # 次に伝搬させる(仮想の)加湿器の位置
  nextHH = []
  # 加湿器を一つずつ見ていく．
  for (y, x) in HH:
    # 上下左右を見ていく
    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):
          # 0 ~ 自分の加湿度-1 のとき
          if(0 <= SS[Y][X] <= d):
            # 加湿度を設定
            SS[Y][X] = d
            # (仮想の)加湿器を設置
            nextHH.append([Y, X])
  # (仮想の)加湿器を再設定
  HH = nextHH

# 出力
ans = 0
for i in range(H):
  for j in range(W):
    if(SS[i][j] > 0):
      ans += 1
print(ans)
```

# D問題
- 大前提として，`N` がデカすぎるので，ルートやログで計算量を減らす必要がある．
- 約数が9つになる条件
  - 素数 `p, q` として， `p^2q^2` or `p^8` となるときだけ．
    - 詳細が気になる人「高校数学A」などで調べてください．
  - 全ての数値(`N`, `p`, `q`)にルートをとって考える．
    - `pq` or `p^4` が `sqrtN` 以下になる数字を見つける問題に帰着した．
- 解き方
  - エラトステネスの篩で `sqrtN` 以下の素数を列挙する．
  - `pq<=sqrtN` は二分探索で探す(`for` 二重だと実行時間に間に合わない)．
  - `p^4<=sqrtN` は線形探索で探す．
```D.py
"""
<方針>
- 大前提として，`N` がデカすぎるので，ルートやログで計算量を減らす必要がある．
- 約数が9つになる条件
  - 素数 `p, q` として， `p^2q^2` or `p^8` となるときだけ．
    - 詳細が気になる人「高校数学A」などで調べてください．
  - 全ての数値(`N`, `p`, `q`)にルートをとって考える．
    - `pq` or `p^4` が `sqrtN` 以下になる数字を見つける問題に帰着した．
- 解き方
  - エラトステネスの篩で `sqrtN` 以下の素数を列挙する．
  - `pq<=sqrtN` は二分探索で探す(`for` 二重だと実行時間に間に合わない)．
  - `p^4<=sqrtN` は線形探索で探す．
"""
# 入力
N = int(input())
sqrtN = int(N**0.5)

# エラトステネスの篩
maxPrime = sqrtN
isPrime = [True]*(maxPrime + 1)
isPrime[0] = False
isPrime[1] = False
for p in range(2, int(maxPrime**0.5) + 1):
  if isPrime[p]:
    for q in range(p*p, maxPrime + 1, p):
      isPrime[q] = False
lsPrime = [i for i in range(2, maxPrime + 1) if isPrime[i]]

# pq<=sqrtN
ans = 0
for i, p in enumerate(lsPrime):
  # 二分探索
  ok = -1
  ng = len(lsPrime)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if p*lsPrime[mid] <= sqrtN:
      ok = mid
    else:
      ng = mid
  # 重複の内容に，p<qを意識して計算する．
  ans += max((ok)-i, 0)

# p^4<=sqrtN
for i in lsPrime:
  if(i**4<=sqrtN):
    ans += 1
  else:
    break

# 出力
print(ans)
```

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