[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回の記事の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)

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

一週間体調崩してた．