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

A問題

float で受け取る。

A.py

"""
<方針>
- `float` で受け取る。
"""
# 入力
X = float(input())

if(38.0<=X):
  print(1)
if(37.5<=X<38.0):
  print(2)
if(X<37.5):
  print(3)

B問題

連続しているところの間に文字を挿入して調整してあげれば良い。
最初と最後に番兵を入れることで、最初と最後の条件を気にしない方針にする。

B.py

"""
<方針>
- 連続しているところの間に文字を挿入して調整してあげれば良い。
- 最初と最後に番兵を入れることで、最初と最後の条件を気にしない方針にする。
"""
# 入力
S = list(input())

# 番兵
S = ["o"] + S + ["i", "o"]

# 答え
ans = 0

# 間に入れる文字
cnt = 0

# 今までiかどうか
isI = True

# 順番に見ていく
for s in S:
  # 今までiかどうかと現在iかどうか
  if(isI == (s == "i")):
    # 連続した回数を増やす
    cnt += 1
  else:
    # 間に文字を入れる数を増やす
    ans += cnt
    # 今までの文字を反転する
    isI = not isI
    # 間に入れる文字を初期化する
    cnt = 0

# 出力
print(ans)

C問題

方針

分割ごと O(N) に、それぞれの種類数を数えて O(N) いては、O(N^2) かかってしまう。
分割を変えるごとに、移動する数字は一つなので、うまく種類数を管理できれば、O(N) でいけそう。
- それぞれの分割がそれぞれの数値をいくつ持つかを保持し種類数も管理する。
- 0-1 の変動をしたときだけ、それぞれの種類数を変動させる。

前提

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

C.py

"""
<方針>
- 分割ごと `O(N)` に、それぞれの種類数を数えて `O(N)` いては、`O(N^2)` かかってしまう。
- 分割を変えるごとに、移動する数字は一つなので、うまく種類数を管理できれば、`O(N)` でいけそう。
  - それぞれの分割がそれぞれの数値をいくつ持つかを保持し種類数も管理する。
  - `0-1` の変動をしたときだけ、それぞれの種類数を変動させる。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 左の数値を管理
cntL = 0
L = [0]*(N+1)

# 右の数値を管理
cntR = 0
R = [0]*(N+1)


# 最初は全て右側に値を入れる
for a in A:
  R[a] += 1
  # aという数値がRに現れたとき
  if(R[a] == 1):
    cntR += 1

# 答え
ans = -1

# 左から順番に左側に寄せる
for a in A:
  R[a] -= 1
  # aという数値がRから消えたとき
  if(R[a] == 0):
    cntR -= 1
  
  # aという数値がLに現れたとき
  L[a] += 1
  if(L[a] == 1):
    cntL += 1
  
  # 更新
  ans = max(ans, cntR+cntL)

# 出力
print(ans)

D問題

公式解説と一緒です。

D.py

"""
<方針>
- 公式解説と一緒です。
"""
N = int(input())

# 二分探索を用いた二次方程式の解
def sol(a, b, c):
  l = 0
  r = N
  while abs(l-r)>1:
    mid = (l+r)//2
    if(a*mid**(2) + b*mid**(1) + c*mid**(0) <= 0):
      l = mid
    else:
      r = mid
  
  if(a*l**(2) + b*l**(1) + c*l**(0) == 0):
    return l
  else:
    return -1

for d in range(1, int(N**(1/3)) + 1):
  if(N%d != 0):
    continue
  
  m = N//d
  k = sol(3, 3*d, d**2 - m)
  if(k>0):
    
    print(k+d, k)
    exit()

print(-1)

補足

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

筆者について

その他

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

最後に一言

完璧なんてないよな。。。
あ。あと就活頑張ります。