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

A問題

• 計算をするだけ。

A.py

"""
<方針>
- 計算をするだけ。
"""
# 入力
N = int(input())

# 計算
ans = 2**N - 2*N

# 出力
print(ans)

B問題

• while 文でループ処理する。
• 1 になったら Yes を出力してプログラムを終了する。
• 生成された数字もメモしておき、すでに存在した数字で無限ループ入りそうになってもループを抜ける。

B.py

"""
<方針>
- `while` 文でループ処理する。
- `1` になったら `Yes` を出力してプログラムを終了する。
- 生成された数字もメモしておき、すでに存在した数字で無限ループ入りそうになってもループを抜ける。
"""
# 入力
N = int(input())

# 生成された数字集合
se = set()

# ループ処理
while (N not in se):
  # ハッピー！
  if(N == 1):
    print("Yes")
    exit()
  
  # 集合に登録
  se.add(N)
  
  # 次の数字を計算
  N = sum([int(n)**2 for n in str(N)])
print("No")

C問題

方針

• N 以下のやつらをまとめて計算することを考える。
• 無駄なく計算すればいけそう。つまり、x を O(√N) で回して、y を O(√N) を回せば良さそう。

前提

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

C.py

"""
<方針>
- `N` 以下のやつらをまとめて計算することを考える。
- 無駄なく計算すればいけそう。つまり、`x` を `O(√N)` で回して、`y` を `O(√N)` を回せば良さそう。
"""
# 入力
N = int(input())

# N以下それぞれが何回出てきたかカウント
A = [0]*(N+1)

# カウント
for x in range(1, int(N**.5)+1):
  for y in range(x+1, int((N-x**2)**.5)+1):
    index = x**2+y**2
    if(index <= N):
      A[index] += 1

# 出てきた回数一回だけを取得
ans = []
for i, a in enumerate(A):
  if(a == 1):
    ans.append(i)

# 出力
print(len(ans))
print(*ans)

補足

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

• 今回のコンテスト

筆者について

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

その他

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

最後に一言

• あけおめ。ことよろ。