ABC319をPythonで（A~E）

AtCoder Beginner Contest 319の解答と簡易的な解説を書きました。

A問題

問題文に書いてあるのをコピペする。

A問題

s = {"tourist":3858,
"ksun48":3679,
"Benq":3658,
"Um_nik":3648,
"apiad":3638,
"Stonefeang":3630,
"ecnerwala":3613,
"mnbvmar":3555,
"newbiedmy":3516,
"semiexp":3481}
print(s[input()])

B問題

各iについて全探索する。

B問題

n = int(input())
ans = ["-"] * (n + 1)
for i in range(n + 1):
    for j in range(1, 10):
        if n % j == 0 and i % (n // j) == 0:
            ans[i] = str(j)
            break

print("".join(ans))

C問題

本番は根性で全探索した。

C問題

from itertools import permutations

c = [list(map(int, input().split())) for _ in range(3)]

total, ans = 0, 0
for p in permutations(range(9)):
    total += 1
    check = [[False] * 3 for _ in range(3)]
    flag = True
    for p_i in p:
        x, y = p_i // 3, p_i % 3
        check[x][y] = True
        a, cnt_a = set(), 0
        b, cnt_b = set(), 0
        for i in range(3):
            if check[x][i]:
                a.add(c[x][i])
                cnt_a += 1
            if check[i][y]:
                b.add(c[i][y])
                cnt_b += 1
        if (len(a) == 1 and cnt_a == 2) or (len(b) == 1 and cnt_b == 2):
            flag = False
        if x == y:
            a = {c[i][i] for i in range(3) if check[i][i]}
            if len(a) == 1 and sum(check[i][i] for i in range(3)) == 2:
                flag = False
        if x + y == 2:
            a = {c[i][2 - i] for i in range(3) if check[i][2 - i]}
            if len(a) == 1 and sum(check[i][2 - i] for i in range(3)) == 2:
                flag = False
    if flag:
        ans += 1

print(ans / total)

D問題

2分探索

ミスが起きないように、事前に空白分+1しておき解答時に-1する。

D問題

n, m = map(int, input().split())
L = list(map(lambda x:int(x) + 1, input().split()))

def calc(x):
    res = 1
    now = L[0]
    if now > x:return float("inf")
    for l_i in L[1:]:
        if x < l_i:
            return float("inf")
        if now + l_i <= x:
            now += l_i
        else:
            res += 1
            now = l_i

    return res


ok, ng = 10 ** 16, 0
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if calc(mid) <= m:
        ok = mid
    else:
        ng = mid

print(ok - 1)

E問題

移動時間は、開始時間mod pで周期的に変わる
このpは、バスの出発時間p_iの最小公倍数

E問題

from math import lcm

n, x, y = map(int, input().split())
buss = [list(map(int, input().split())) for _ in range(n - 1)]
p = 1
for p_i, _ in buss:p = lcm(p, p_i)

def solve(i):
    now = i + x
    for p_i, t_i in buss:
        now = (now + p_i - 1) // p_i * p_i + t_i
    return now + y - i

data = [solve(i) for i in range(p)]

for _ in range(int(input())):
    q = int(input())
    print(data[q % p] + q)