Atcoder Beginner Contest 142 振り返り 【Python】

はじめに

AtCoder Beginner Contest 142の振り返りをします。

atcoder.jp

A - Odds of Oddness

提出したプログラム

N = int(input())
count = 0
for i in range(N+1):
    if i % 2 == 1:
        count += 1
print(count/N)

まだ競プロになれてないせいか問題をなぞった回答が先に思い浮かぶ。

綺麗に書いてあった他の人の回答

N = int(input())
print(int(N / 2 + 0.5) /N)

B - Roller Coaster

提出したプログラム

N, K = map(int,input().split())
h_list = list(map(int,input().split()))
count = 0
for i in h_list:
    if i >= K:
        count += 1
print(count)

お前はいつまでpythonの内包表記を使わないつもりだ？？？ そろそろ慣れてください。

内包表記で書いたやつ

n,k=map(int,input().split())
h=list(map(int,input().split()))
print(sum([1 for i in h if i>=k]))

C - Go to School

提出したプログラム

N = int(input())
A_list = list(map(int,input().split()))
result_list = [0]*N
for i, val in enumerate(A_list):
    result_list[val-1] = i+1
print(*result_list)

リストをインデックスでソートするのはすぐわかったけど少し実装に手間取った。

因みに一回TLEしました....。

TLEしたやつ

N = int(input())
A_list = list(map(int,input().split()))
result_list = []
for i in range(1, N+1):
    list_idx = A_list.index(i)
    result_list.append(list_idx+1)
print(*result_list)

毎回リストからインデックスを参照してるから時間かかったと予想。

今後は計算量とか意識しながらプログラム書きたいです。

D - Disjoint Set of Common Divisors

提出したプログラム（TLE）

A,B=map(int,input().split())
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1] and n%i==0]
    return is_prime, table
_, A_cf = sieve(A)
_, B_cf = sieve(B)
cf = []
for i in A_cf:
    for j in B_cf:
        if i==j:
            cf.append(i)
print(len(cf)+1)

２つの数字をx,yとおく。

x以下の素数かつ約数のリストとy以下の素数かつ約数のリストを求めて、一致する個数を計算すればいいのかなーって思って書きました。

素数の求め方はぐぐったらエラトステネスの篩ってやつが早いらしいから使ってみました。

エラトステネスのふるいとその計算量 | 高校数学の美しい物語

コンテスト中は気が付かなかったけど、素数かつ約数って素因数だよね....。

算数からやり直します；；

終わりに

明日（2019/10/05）は FUNProCon があります。

大学の競プロ勢に轢き殺されてきます😱🚑