AtCoder Beginner Contest 166参加記(Python)

コンテスト参加記 AtCoder Python ABC166

AtCoder Beginner Contest 166(ABC166)に参加しました
atcoder.jp

目次



A問題：A - A - A?C(100点)

問題文
atcoder.jp

場合分けをすれば大丈夫です

pythonでの実装例

s = input()

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



B問題：Trick or Treat(200点)

問題文
atcoder.jp

お菓子を持っている人を数えていき、全体の人数から持っている人数を引いてあげます
被りがあったときに保存しないようにする時にはpythonの場合setが使えます

pythonでの実装例

n,k = map(int,input().split())
children = set()

for i in range(k):
    d = int(stdin.readline().rstrip())
    a = list(map(int,stdin.readline().rstrip().split()))
    for j in a:
        children.add(j)
 
print(n-len(children))



C問題： Peaks(300点)

問題文
atcoder.jp

他のつながっている標高と比較した際に、自分の標高が一番高いかどうかを判定します

最高地点であった場合１の値を持つリストを作り、各道ごとにもし自身の方が低かった場合に値を０に直します
答えはリストの合計値です

pythonでの実装例

n,m = map(int,input().split())
h = list(map(int,input().split()))
li = [[]for _ in range(n)]

# 自分が最高点だった場合１違ったら０
higest = [1]*n

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    li[a].append(b)
    li[b].append(a)
    if h[a] <= h[b]:
        higest[a] = 0
    if h[b] <= h[a]:
        higest[b] = 0

print(sum(higest))



D問題：I hate Factorization(400点)

問題文
atcoder.jp

与えられている数字が5乗されているところに注目します
詳しい照明は公式のpdfに載っていますが、aとbの範囲はそれほど大きくはならないことが分かります
(本番中は適当に-500から+500までで回しました)

範囲内でｘに合致する組があった場合それを出力します

ちなみにａ⁵－ｂ⁵の素因数分解をすると
ａ⁵－ｂ⁵＝(ａ－ｂ)(ａ⁴＋ａ³ｂ＋ａ²ｂ²＋ａｂ³＋ｂ⁴)
です

pythonでの実装例

x = int(input())

for i in range(-200,200):
    for j in range(-200,200):
        if i**5-j**5 == x:
            print(i,j)
            exit()



E問題：This Message Will Self-Destruct in 5s(500点)(※本番中未解答問題)

問題文
atcoder.jp

任意の2人を選び2人の番号の絶対値と身長の和が等しかった場合が何個あるかをカウントします
問題文にも書いてありますが普通に全列挙していると計算量が10**10程度になってしまい間に合いません

そこで以下のような変形を行います(i < j)

A_{j} - A_{i} = j+i
　　　　↓
i+A_{i} = j-A_{j}

まずi+A_{i}の値をN人分保存しておき、その後N人分j-A_{j}の値を見たときに等しいものがいくつあるかをカウントします
このような場合には辞書型を使うと効率的に検索を行うことができます

pythonでの実装例

n = int(input())
a = list(map(int,input().split()))

# i + A_iの値を保存する辞書
dic = {}
point = 0

for i,j in enumerate(a):
    if i+j in dic:
        dic[i+j] += 1
    else:
        dic[i+j] = 1

# j - A_jの値を辞書で検索をかける
for i,j in enumerate(a):
    if i-j in dic:
        point += dic[i-j]

print(point)



所感

今回の結果
atcoder.jp

ABCD問題の４完１ぺナで3798th / 11684でした（パフォーマンス:881　レート:974 → 965 (-9)）

前日に行われたABC165の結果はよかったのですが今回は微減。。。
C問題をグループ分けした個数を求める問題だと勘違いして手間取って時間を落としてしまいました

E問題は変形するという解法を思いつかなかったので、もっと経験を積む必要がありそうです