ABC142参戦記(A問題~C問題+D問題)

先日行われたABC142に参加したのでコンテスト中のあれこれをメモしておこうかと思います。使用言語はpython3、結果はABC3完で2596位(順位表情報)でした。コンテストへのリンクはこちら→https://atcoder.jp/contests/abc142

A - Odds of Oddness

偶奇で場合分けして偶数なら0.5,奇数なら(N // 2 + 1) / Nを表示すれば良さそうです。

ABC142_A.py

N = int(input())
if N % 2 == 0:
    print(0.5)
else:
    print((N // 2 + 1) / N)
)

B - Roller Coaster

K以上の人の数をカウントしていくだけですね。

ABC142_B.py

N, K = map(int, input().split())
h = list(map(int, input().split()))
cnt = 0
for i in range(N):
    if h[i] >= K:
        cnt += 1
print(cnt)

C - Go to School

人数が少ない時に来た子から順に登校していたということになるので、$A_i$の値でソートして$i$の値を順に表示すれば良いですね。

ABC142_C.py

N = int(input())
A = list(map(int, input().split()))
L = [[] for i in range(N)]
for i in range(N):
   L[i] = [A[i], i+1]
L.sort()
ans = [0 for i in range(N)]
for i in range(N):
   ans[i] = L[i][1]
print(*ans)

D - Disjoint Set of Common Divisors

コンテスト中にずっとバグらせていました。gcd求めてその素因数の数を調べるだけですね。素因数の調べ方に関してはコンテスト中こちらの記事を参考にさせていただきました。

ABC142_D.py

from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    i = 2
    while i <= n**0.5 + 1:
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
        i += 1
    if tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)

反省

今回はC問題まで通すことができました。時間配分は大体A-5分、B-3分半、C-5分、という感じでした。Dで数学的な部分に躓いたのが痛かったなと思います。