Atcoder-ABC205をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC204を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
- 割り算するので、誤差が気になる気もしたが大丈夫だった
実装
A, B = map(int, input().split()) print(A*B/100)
結果
B問題
考察
- 並び替えによって作れれば良いので、要素があるかを確認すれば良い
- 与えられたAをsortし、Nまでの要素が全て揃っているかを確認すれば良い
実装
N = int(input()) A = list(map(int, input().split())) flag = True A.sort() for i in range(N): if i+1 == A[i]: continue flag = False break if flag: print("Yes") else: print("No")
結果
C問題
考察
- 指数の性質を利用し、場合分けをする
- Cが偶数の場合はA, Bの絶対値の比較になる(偶数乗すると正になるため)
- Cが奇数の場合は、単純にA, Bの大丈比較で良い
実装
A, B, C = map(int, input().split()) if C % 2 == 0: if abs(A) == abs(B): print("=") elif abs(A) > abs(B): print(">") else: print("<") else: if A == B: print("=") elif A > B: print(">") else: print("<")
結果
D問題
初めてのD問題解けた!!
考察
- max(K)=1018 のため、rangeで巨大な数列を作り、Aを除外するとTLEになるため別の方法を考える
- N=105 のため、この範囲であればloopが回せそう
- それぞれのKに対して、Aの要素を加味しながら何番目かを出すのが良さそう
- kがAのうちでどこに入るのかを、2分探索で求める
- Aも大きな数列なので、線形探索でO(n)だと間に合わない可能性があるため、二分探索で求める
- もし、Aのうちでkが一番小さいようなら、そのまま出力する
- もし、kがAの要素よりも大きいなら、Aの要素を除いて順番を出す必要があるので、再帰を用いて順次求めるようにする
- kがAのうちでどこに入るのかを、2分探索で求める
実装
import sys from bisect import bisect_right sys.setrecursionlimit(pow(10, 9)) N, Q = map(int, input().split()) A = list(map(int, input().split())) def solve(k, idx1): idx2 = bisect_right(A, k) if idx1 < idx2: solve(k+(idx2-idx1), idx2) else: print(k) for _ in range(Q): k = int(input()) solve(k, 0)
結果
まとめ
- D問題が初めて解けて、自己最高のratingを叩き出せた!嬉しい