EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC205をpythonで問題を解いてみた

目的

  • Atcoderで上を目指すべく頑張っている中でABC204を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い
  • 割り算するので、誤差が気になる気もしたが大丈夫だった

実装

A, B = map(int, input().split())

print(A*B/100)

結果

B問題

atcoder.jp

考察

  • 並び替えによって作れれば良いので、要素があるかを確認すれば良い
    • 与えられた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問題

atcoder.jp

考察

  • 指数の性質を利用し、場合分けをする
  • 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問題解けた!!

atcoder.jp

考察

  • max(K)=1018 のため、rangeで巨大な数列を作り、Aを除外するとTLEになるため別の方法を考える
  • N=105 のため、この範囲であればloopが回せそう
  • それぞれのKに対して、Aの要素を加味しながら何番目かを出すのが良さそう
    • kがAのうちでどこに入るのかを、2分探索で求める
      • Aも大きな数列なので、線形探索でO(n)だと間に合わない可能性があるため、二分探索で求める
    • もし、Aのうちでkが一番小さいようなら、そのまま出力する
    • もし、kがAの要素よりも大きいなら、Aの要素を除いて順番を出す必要があるので、再帰を用いて順次求めるようにする

実装

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を叩き出せた!嬉しい