LoginSignup
0

More than 1 year has passed since last update.

posted at

updated at

Atcoder ABC166 A-EをPythonで

また4完でした。Eは解説AC。コンテストのコードそのまま載せてるのでお見苦しい部分があるかもしれませんがご容赦ください。

A. A?C

入力がABCだったらARCを、そうでなければABCを返す

ABC166a.py
s=input()

if s=="ABC":
    print("ARC")
else:
    print("ABC")

B. Trick or Treat

全てのお菓子に関して、持っている子どものindexを+1する。最後にお菓子を1つも持っていない子を数え上げて出力。

ABC166b.py
n,k=map(int,input().split())
d=[]
a=[]
for i in range(k):
    d.append(int(input()))
    a.append(list(map(int,input().split())))

aa=[0]*n

for j in a:
    for k in j:
        aa[k-1]+=1 #お菓子を持っている子のindexを+1

ans=0

for x in aa:
    if x==0:
        ans+=1 #お菓子を1つも持っていない子は0なので、その子の数を数える

print(ans)

C. Peaks

頂点数と同じ長さの配列を用意し、2つの頂点の高さを比べて低いほうの頂点を+1する。高さが同じであれば両方とも+1する。最後に値が0である頂点の数を出力する。
ちなみに1本の道とは、一筆書きで行ける道ではなく頂点に繋がっている道のみという意味でした。勘違いして時間ロスした。

ABC166c.py
import copy

n,m=map(int,input().split())
h=list(map(int,input().split()))
l=[]
for i in range(m):
    a,b=map(int,input().split())
    l.append([a,b])

ll=[0]*n

for j in l:
    if h[j[0]-1]>h[j[1]-1]:
        ll[j[1]-1]+=1
    elif h[j[0]-1]==h[j[1]-1]:
        ll[j[1]-1]+=1
        ll[j[0]-1]+=1
    else:
        ll[j[0]-1]+=1

ans=0
#print(ll)
for k in ll:
    if k==0:
        ans+=1
print(ans)

D. I hate factorization

$A$も$B$も制約が無いので総当たりでTLEにならない程度:1000個くらい用意して計算したら通った。公式による解説見ると負の数含めて250個くらいで十分だそうです。負の数のべき乗根はまともに出力してくれないので一度absを取る必要あり。

ABC166d.py
x=int(input())
l=[]

for i in range(300): #300**5=2430000000000以下のx^5で表せる数(-x含む)を追加
    a=i**5
    l.append(a)
    l.append(-a)

for j in l:
    for k in l:
        aa=j-k
        if j!=k and aa==x:
            ans=[]
            for z in [j,k]:
                aaa=abs(z)**(1/5) #5乗根
                if z>=0:
                    ans.append(int(aaa))
                else:
                    ans.append(int(-aaa))
            print(*ans)                
            exit()

E. This Message Will Self-Destruct in 5s

アプローチに関しては 公式による解説を参照。インデックス値と身長の和と、インデックス値と身長の差をそれぞれ用意する。その後2つの値が一致するようなパターンの数を数える。具体的には2つの配列lとrを用意し、lの各要素に関して同じ値を持つrの数を数える。
count使ったらTLEになったので、Counter使って連想配列として格納し、get使って取り出すと通った。どのくらい早くなっているかは検証していませんが・・・

ABC166e_TLE.py
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[]
r=[]
for i,j in enumerate(a):
    l.append(i+j)
    r.append(i-j)

for i in l:
    ans+=r.count(i)

print(ans)
ABC166e.py
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[]
r=[]
for i,j in enumerate(a):
    l.append(i+j)
    r.append(i-j)

b=Counter(r)
for i in l:
    ans+=b.get(i,0)

print(ans)

Dまでを30-40分くらいで解けないと水色への道は開かれませんね。がんばらねば

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0