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

A問題

• 数値部分を a b として分けて受け取る．
• 掛け算して出力．

A.py

"""
<方針>
- 数値部分を `a` `b` として分けて受け取る．
- 掛け算して出力．
"""
# 入力
S = str(input())

a = int(S[0]) # 前半部分

b = int(S[2]) # 後半部分

ans = a*b # 答え

# 出力
print(ans)

B問題

• 順番に 2 から順番に割っていき，1 になるまで繰り返す．

B.py

"""
<方針>
- 順番に `2` から順番に割っていき，`1` になるまで繰り返す．
"""
# 入力
X = int(input())

N = 2
# 割りまくる
while True:
  # Nで割ったものにする．
  X //= N
  # 割った結果が1のとき，
  if(X == 1):
    # 抜け出す．
    break
  
  # 割る数を増やす．
  N += 1

# 出力
print(N)

C問題

方針

• クエリの数の時点で，O(N) かかる．
• なので，一回の処理は定数時間もかけられない．
• ここで，クエリタイプ毎に，list に対しての素朴な処理の計算量を見てみる
  • タイプ1
    • 新しい要素を追加→ O(1)
  • タイプ2
    • 先頭の要素を削除→ O(N)
  • タイプ3
    • 先頭からの累計の長さを取得→ O(N)
• 対策を考える．
  • タイプ2
    • deque を用いることで，先頭の要素を消す操作を O(1) にする．
  • タイプ3
    • 要素を追加した時に，累計の長さを保持させておくことで，要素への単純アクセスにし，O(1) にする．

前提

• C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
• AとB問題では，基本的に制約条件を見ずにやっても解ける．
• しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
• 詳しい話は私の352回の記事 のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- クエリの数の時点で，`O(N)` かかる．
- なので，一回の処理は定数時間もかけられない．
- ここで，クエリタイプ毎に，`list` に対しての素朴な処理の計算量を見てみる
  - タイプ1
    - 新しい要素を追加→ `O(1)`
  - タイプ2
    - 先頭の要素を削除→ `O(N)`
  - タイプ3
    - 先頭からの累計の長さを取得→ `O(N)`
- 対策を考える．
  - タイプ2
    - `deque` を用いることで，先頭の要素を消す操作を `O(1)` にする．
  - タイプ3
    - 要素を追加した時に，累計の長さを保持させておくことで，要素への単純アクセスにし，`O(1)` にする．
"""
from collections import deque

Q = int(input())

# 蛇を管理するdeque
## 要素の1つ目の要素→その蛇の頭の位置
## 要素の2つ目の要素→その蛇の尻尾の位置
snakes = deque()

# クエリ毎の処理
for _ in range(Q):
  query = list(map(int, input().split()))
  match query:
    # タイプ1
    case [1, l]:
      # 尻尾までの長さを取得する．
      if snakes:
        # 蛇が存在する時
        _, tail = snakes[-1]
      else:
        # 蛇が存在しない時
        tail = 0
      # 蛇を追加
      snakes.append([tail, tail+l])
    # タイプ2
    case [2]:
      # 先頭の蛇を出す．
      snakes.popleft()
    case [3, k]:
      # 先頭の蛇
      head0, _ = snakes[0]
      # k番目の蛇
      head, _ = snakes[k-1]
      # 位置の差分が，現在の先頭からの位置
      print(head - head0)

D問題

• 第一象限を考えて，4 倍し，中心の 1 を足せば良い．
• 第一象限の計算方法
  • 際が条件 (((i+0.5)**2 + (j+0.5)**2) <= R**2) を満たすかどうかをみる．
  • i を増加させて， j を減少させる方向で尺取りのように動かす．
  • 全体として，O(R) で計算できる．

D.py

"""
<方針>
- 第一象限を考えて，`4` 倍し，中心の `1` を足せば良い．
- 第一象限の計算方法
  - 際が条件 (`((i+0.5)**2 + (j+0.5)**2) <= R**2`) を満たすかどうかをみる．
  - `i` を増加させて， `j` を減少させる方向で尺取りのように動かす．
  - 全体として，`O(R)` で計算できる．
"""
R = int(input())

# 総数
ans = 0

# jは最初大きくする
j = R
# iを増加させる
for i in range(R):
  # jを動かす
  while True:
    # 条件を満たすか
    if ((i+0.5)**2 + (j+0.5)**2) <= R**2:
      # 満たせば，1~jを記録する．
      ans += j
      # 次のiへ
      break
    else:
      # jを減少させる
      j -= 1

# 4倍にして，1を足して出力
print(4*ans + 1)

補足

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

• 今回のコンテスト

筆者について

• Atcoderアカウント
• 今回も不参加のため，成績なし．
• 解説で示したA問題の提出
• 解説で示したB問題の提出
• 解説で示したC問題の提出
• 解説で示したD問題の提出

その他

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

最後に一言

• 特になし．