AtCoder Beginner Contest 169 参戦記

ABC169A - Multiplication 1

1分半で突破. 書くだけ. コードテストがなかなか実行されなかったせいで無駄に時間がかかってしまった.

A, B = map(int, input().split())

print(A * B)

ABC169B - Multiplication 2

3分で突破. 64bit 整数でもオーバーフローする問題だけど、Python だと何も考えなくていいので楽ですねー. 0を先頭にするためにソートするのを忘れなければ OK!

N = int(input())
A = list(map(int, input().split()))

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)

ABC169C - Multiplication 3

3分で突破. A≤10¹⁵ を見た瞬間に double だとヤバいと理解したので、decimal に逃げた. (10¹⁵ は、10³≒2¹⁰ だから、ざっくりで ≒2⁵⁰ なので、double の仮数部 52bit に近く、それを溢れさせるのが作為だと分かる.)

from decimal import Decimal

A, B = map(Decimal, input().split())

print(int(A * B))

ABC169D - Div Game

22分半で突破、WA1. とりあえずエラトステネスの篩を貼り付けようと思ったが、N≤10¹² なので貼れず、sqrt(N) までの処理に直すところからスタート. その後に p^e を列挙して、ガンガン順に割っていって残った値を処理するところで失敗して WA を貰ったけど、もしかしてこのコードも嘘解法かもしれない. (ちゃんと残ったのが素数かどうかチェックしないと駄目なような?)

from math import sqrt

N = int(input())

rn = int(sqrt(N))
sieve = [0] * (rn + 1)
sieve[0] = -1
sieve[1] = -1
t = [0] * (rn + 1)
for i in range(2, rn + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    j = i
    while j < rn + 1:
        t[j] = 1
        j *= i
    for j in range(i * i, rn + 1, i):
        if sieve[j] == 0:
            sieve[j] = i

result = 0
last = -1
for i in range(2, rn + 1):
    if t[i] == 0:
        continue
    if N % i == 0:
        result += 1
        N //= i
        last = i
if N != 1 and N > rn:
    result += 1
print(result)

追記: 以前に書いた素因数分解の関数を使ったらもっとスパッと書けた. 失敗.

def prime_factorize(n):
    result = []
    if n % 2 == 0:
        t = 0
        while n % 2 == 0:
            n //= 2
            t += 1
        result.append((2, t))
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


N = int(input())

result = 0
for p, e in prime_factorize(N):
    i = 1
    while e >= i:
        result += 1
        e -= i
        i += 1
print(result)

ABC169E - Count Median

突破できず. 1時間以上考えてたわけだが、考えれば考えるほど難しい.

追記: コンテスト中も A_i と B_i の中央値の間に中央値として考えられる値があるよなあと思ったけど、全部そうだという確信は得られなかったよなあ. とはいえ、腐った読みでそれをスパッと出すくらいの気構えは要ったのかもしれない. yukicoder だとペナがないからホイホイ投げるんだけどなあ(笑). X_i を A_i から始めて、どれかを1増やすと中央値は増えないか、1増える(偶数の場合は0.5の可能性もある)と言われると確かにそうだなあと納得できる…….

N = int(input())
A = [None] * N
B = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

A.sort()
B.sort()

if N % 2 == 0:
    b = (B[N // 2] + B[(N - 1) // 2]) / 2
    a = (A[N // 2] + A[(N - 1) // 2]) / 2
    print(int((b - a) * 2 + 1))
else:
    print(B[N // 2] - A[N // 2] + 1)