Zenn
🔥

【AtCoder】ABC400をPythonで解く

に公開
Python
競技プログラミング
AtCoder
tech

1. はじめに

目的

ABCを解くことにより、とにかくRatingを上げていく。

フィードバックして欲しい点

私は競技プログラミング初心者のため、いただいたアドバイスをすぐに理解できず、何度も質問してしまうかもしれません。それでも構わないという心優しい方がいらっしゃれば、ぜひアドバイスをいただけると嬉しいです。丁寧に教えていただけると、とても助かります！

  1. アルゴリズムの選択と最適化
    • 今の実装よりも効率的なアルゴリズムがあるか？
    • 計算量を減らせる部分や、ボトルネックになっている処理はないか？
  2. コードの可読性と整理
    • もっとシンプルに書ける部分はないか？
    • 変数名や関数名が分かりやすいか？
  3. エッジケース・例外処理の検討
    • 想定外の入力でバグが発生する可能性がないか？
    • 競プロのジャッジでWAになりそうなケースがあるか？

注意点

  • 言語はPython(PyPy 3.10-v7.3.12) を使用しています。

2. コンテスト情報

コンテスト名

AtCoder Beginner Contest 400

コンテストURL

https://atcoder.jp/contests/abc400

開催日

2025-04-05(土) 21:00 ~ 2025-04-05(土) 22:40 (100分)

配点

問題 点数
A 100
B 200
C 350
D 400
E 500
F 550
G 675

結果

順位：6712

総合 A B C D E F G
得点 300 100 200 (1)
時間 10:11 4:14 10:11

3. 解いた問題と解法

A: ABC400 Party

コード

a = int(input())

if 400 % a == 0:
  print(400 // a)
  
else:
  print(-1)

解法

400をAで割り切れるかで場合分けを行う。
割り切れた場合には400//aの値を、余りが出れば-1を出力する。

改善点

- 400 // a
+ 400 / a

400をaで割り切れるということがわかっているので、わざわざ//を使う必要もない。

B: Sum of Geometric Series

コード

n, m = map(int, input().split())
x = 0

for i in range(0, m+1):
  x += n**i

if x > 10**9:
  print("inf")
else:
  print(x)

解法

N^iをN**iで表し、iを0からMまでループを使ってN^iの値を足し合わせていく。
その後、条件分岐を用いて、xが10^9以上ならxの値を、xが10^9未満であればinfを出力する。

改善点

N, M = map(int, input().split())
X = sum([N ** i for i in range(M + 1)])
print(X if X <= 10 ** 9 else "inf")
  • リスト内包表記とフィルタリング
    [(変数を利用した処理) for (変数名) in (変数を動かす範囲) if 条件式]

リスト内包表記を利用することにより、N^iの合計をより簡潔に求めている。
また、フィルタリングを用いた条件分岐を行なって、より簡潔に出力している。

C: 2^a b^2

コード

n = int(input())
bases = []
results = []

b = 1
while 2 * b**2 <= n:
  bases.append(2 * b**2)
  b += 2
for i in bases:
  a = 0
  while i * 2**a <= n:
    results.append(i * 2**a)
    a += 1
print(len(results))

解法

まずは、bを奇数とした時、2*b^2が全てのXの基本となる数だと考える。
そして、この基本となる数をbasesにすべて格納する。
次に、basesの数を基に、2倍にしていき、Nを超えない範囲までの2^a*b^2の値をresultsにすべて格納する。これを全てのbasesのすべての数に繰り返す。
最後に、resultsに格納されている値の個数をlen(results)で出力する。

改善点

研究中

そもそも私のコードでは、計算量が多すぎて時間内に終わらせることができない。
そのため、計算量を減らす必要がある。
そして、すべてのXは以下の2つで表すことができる。

  1. 2*b^2
  2. 2^2*b^2

これは、2の指数mを以下の2つ場合に分けて証明できる。

  1. 偶数の場合
    2^(2m+2)*b^2 = 2^2*(2^m*b)^2

  2. 奇数の場合
    2^(2m+1)*b^2 = 2*(2^m*b)^2

そして、2^m*bを新しくb'とc'で置き直すと、偶数の場合と奇数の場合は互いに排反事象であるため、以下の式を満たすb'とc'の和が求める値である。

  1. 4*b'^2<=N
  2. 2*c'^2<=N

b'とc'をそれぞれ１つずつ代入していきながら、この等式を満たすのかを考えるのではなく、二分探索などを用いて最大となるb'とc'の値を求めると、より高速に計算ができる。

D~Gは研究中

現在の私には解くことができません。

4. まとめ

今回のC問題は解くこと自体はできたが、圧倒的に時間のかかるコードとなってしまった。改めてC問題以上を取るためにはアルゴリズムの知識が必要だと実感した。

Discussion