Port 53

明日のための技術メモ

トップ > AtCoder > AtCoder ABC142

AtCoder ABC142

AtCoder Python Python-dictionary Algorithm-prime_factorial

今回もA-Cの3完でしたー
C問題で3回くらいTLE(実行時間オーバー)取られたけれど、
Pythonならdictionaryでなんとかなるじゃん...という反省。
dictionary慣れていればもう少し早く解けたなー
AtCoder ABC142

A. Odds of Oddness

N以下の正の整数から取り出したある数aが奇数である確率を求めろとのこと。
Nが偶数なら、N以下の偶数・奇数の数は同じ(n/2個)だし、
奇数なら奇数の方が1つ多い(1+n/2個)。
ささっと場合分けしておしまい。

#coding:utf-8
n = int(input())

if n % 2 == 0:
    print((n/2)/n)
else:
    print((1 + (n//2))/n)

B. Roller Coaster

身長Kcm以上だとジェットコースターに乗れるので、
各メンバーの身長が条件を満たすか判断し、数えるだけ。 一応、降順でソートしてから判定かけた。
そんな私は絶叫系大嫌い...

#coding:utf-8
n, k= map(int, input().split())
h = list(map(int, input().split()))

hs = sorted(h, reverse=True)
count = 0

for member in hs:
    if member >= k:
        count += 1

print(count)

C. Go to School

A[出席番号] = 出席番号の人が来た時にいた人数を把握してリストで書いてたが、
まさかここでTLEになると思ってなかった...
最初はindexとリストの要素が一致するか確認して、
一致したらリストにいれて出力するように考えていたけれど、
それだと計算量がO(N2)になってTLE。PyPyでもダメ。

なので辞書を使い、出席番号とその時の人数をまとめて管理し、
人数の昇順で並べ替えて、出席番号だけ出力すればOKだった。
辞書の使い方慣れてなくて時間かかってしまった...

ポイント

dic = {1: 2, 2: 3, 3: 1}
result = sorted(dic.items(), key=lambda x:x[1])
print(result)
#[(3, 1), (1, 2), (2, 3)] タプルのリストになる

#タプルのリストのindex側だけほしい時
ans = [i[0] for i in result]
print(*ans)
#3 1 2

ACしたコード

#coding:utf-8
n = int(input())
a = list(map(int, input().split()))
#出席番号のリスト
num = list(range(1, n+1))
dic = {key: val for key, val in zip(num, a)}


#結果出力のため、値(人数の昇順）で並べ替え
result = sorted(dic.items(), key=lambda x:x[1])
#生徒の出席番号だけ欲しいので、切り出し
ans = [i[0] for i in result]
print(*ans)

TLE判定になったコード

#coding:utf-8
n = int(input())
a = list(map(int, input().split()))
ans = []

#計算量がO(n^2)に...
for i in range(1, n+1):
    for j in range(0, n):
        if i == a[j]:
            ans.append(j+1)

print(*ans)

D. Disjoint Set of Common Divisors

最近蟻本を買ったので、それの110ページを読み、解説聞きつつ実装。
正の整数2つの公約数から互いに素になる数を最大いくつ選べるかという問題。
最大公約数をさらに素因数分解し、素数の数とそれに1の分を加えれば答え。
最大公約数を出すライブラリgcdは、AtCoder(2019.9時点)ではPython3.4.3のため、
fractionsをimportして使う。
私の環境は3.7なので、mathをimportすればOK。ここだけ気をつける。

#coding:utf-8
#import fractions
import math
import collections

#素因数分解
def prime_factorial(num):
    fact = []
    for i in range(2, int(num**0.5)+1):
        while num % i == 0:
            fact.append(i)
            num = num // i
    if num != 1:
        fact.append(num)
    return fact

if __name__ == "__main__":
    #最大公約数を素因数分解し、その個数＋1が答え
    a, b = map(int, input().split())
    g = math.gcd(a, b)
    #g = fractions.gcd(a, b)

    c = collections.Counter(prime_factorial(g))
    print(len(list(c.keys())) + 1)

D問題 参考