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

Posted at 2024-12-13

[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問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

一週間体調崩してた．

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up