きゃねろぐ

とある「おひさま」の徒然日記

Python初心者のためのABC205

AtCoder

A問題

atcoder.jp

算数の問題ですね．

100:A=B:ans\quad\Longleftrightarrow\quad ans=\displaystyle\frac{AB}{100} 


A,B = map(int,input().split())
print(A*B/100)

B問題

atcoder.jp

実際に A を昇順に並び替えて (1,2,\dots,N) と一致するか判定しましょう．

N = int(input())
A = list(map(int,input().split()))
A.sort()

if A==list(range(1,N+1)):
  print('Yes')
else:
  print('No')

リストを使って各値の出現回数を管理し， 1 から N までの値がそれぞれ1回ずつ現れるかどうかを判定しても良いです．

N = int(input())
A = list(map(int,input().split()))
cnt = [0]*(N+1)

for a in A:
  cnt[a] += 1

ok = True
for i in range(1,N+1):
  if cnt[i] != 1:
    ok = False
    
if ok:
  print('Yes')
else:
  print('No')

集合を用いても同様の判定ができます．

N = int(input())
A = list(map(int,input().split()))
S = set(A)
    
if len(S)==N:
  print('Yes')
else:
  print('No')

C問題

atcoder.jp

まず， A,B は負の値を取ることもあり， C は正の値に限られる点に注意しましょう． A^C と B^C を比較する問題ですが C は共通しているので， C を固定した時の関数 f(X)=X^C の挙動を考えてみましょう．

  • C が奇数のとき， f(X) は狭義単調増加なので A\lt B\ \Longleftrightarrow\ A^C\lt B^C が成り立ちます．
  • C が偶数のとき， f(X) は X\ge 0 の時は狭義単調増加で， X\lt 0 の時は f(X)=f(-X) が成り立つので，まとめると |A|\lt |B|\ \Longleftrightarrow\ A^C\lt B^C が成り立ちます．

以上より， C の偶奇に関して場合分けをすると良いことが分かります．

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

def compare(X,Y):
  if X>Y:
    print('>')
  elif X<Y:
    print('<')
  else:
    print('=')
    
if C%2:
  compare(A,B)
else:
  compare(abs(A),abs(B))

D問題

atcoder.jp

各クエリに対して O(X) の計算量がかかるとすると，全体の計算量は O(QX) となります． Q\le 10^5 とそこそこ大きいので， X=N などではTLEしてしまいます*1．何とか定数時間または \log 時間に抑えられないでしょうか．

小さいケースで実験してみましょう． A=(3,7,10) のとき小さい方から数えて K 番目の数を X とすると，

K X X-K
1 1 0
2 2 0
3 4 1
4 5 1
5 6 1
6 8 2
7 9 2
8 11 3
9 12 3
︙ ︙ ︙

のようになります．同様に実験することで，

  • 1\le K\lt A_1 のとき X=K
  • A_1\le K\lt A_2-1 のとき X=K+1
  • A_2-1\le K\lt A_3-2 のとき X=K+2
    　　　　　　　　︙
  • A_{N-1}-(N-2)\le K\lt A_{N}-(N-1) のとき X=K+N-1
  • A_{N}-(N-1)\le K のとき X=K+N

が成り立つことが分かります．よって，以下のようなコードでACできます．

from bisect import bisect_right

N,Q = map(int,input().split())
A = list(map(int,input().split()))

# 二分探索用のリスト
L = [A[i]-i for i in range(N)]

for _ in range(Q):
  K = int(input())
  X = K + bisect_right(L,K)
  print(X)

この解法における各クエリに対する計算量は O(\log N) です．

別解として，以下のような二分探索が可能です．

from bisect import bisect_right

N,Q = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(Q):
  K = int(input())
  l = 1
  r = 10**18+10**5
  while r-l:
    mid = (l+r)//2
    cnt = mid - bisect_right(A,mid)  #mid以下の自然数のうちAに含まれないものの個数
    if cnt>=K:
      r = mid
    else:
      l = mid+1
  print(l)

この解法における各クエリに対する計算量は O(\log(\max(K_i)+N)\log N) です．

*1:C++だと間に合うらしいです…．