ABC400をPythonで（A～E）

AtCoder Beginner Contest 400の解答等の速報的まとめ

A問題

400で割り切れたらその商を、そうでなければ-1を出力する

A

a=int(input())
print(-1 if 400%a else 400//a)

B問題

答えが$10^9$を超えるまで足す

B

n, m = map(int, input().split())

ans = 0
for i in range(m + 1):
    ans += n ** i
    if ans > 10 ** 9:
        exit(print("inf"))

print(ans)

C問題

$b$に偶数が入らないものとして計算する。

C

from math import isqrt

n = int(input())

ans = 0
for a in range(1, 60):
    b = isqrt(n // (2 ** a))
    ans += (b + 1) // 2

print(ans)

D問題

ふつうのbfsのように探索し、壁があったらそのマスと隣のマスをコスト+1で探索していく

D

from collections import deque

h, w = map(int, input().split())
s = [input() for _ in range(h)]
A, B, C, D = map(lambda x:int(x) - 1, input().split())

INF = float("inf")
cnt = [[INF] * w for _ in range(h)]
q = deque()
q.append([0, A, B])
cnt[A][B] = 0
while q:
    c, x, y = q.popleft()
    if cnt[x][y] < c or cnt[C][D] <= c:
        continue
    for arr_i, arr_j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        i, j = x + arr_i, y + arr_j
        if 0 <= i < h and 0 <= j < w:
            if s[i][j] == "#":
                if c + 1 < cnt[i][j]:
                    cnt[i][j] = c + 1
                    q.append([c + 1, i, j])
                if 0 <= i + arr_i < h and 0 <= j + arr_j < w and c + 1 < cnt[i + arr_i][j + arr_j]:
                    cnt[i + arr_i][j + arr_j] = c + 1
                    q.append([c + 1, i + arr_i, j + arr_j])
            else:
                if c < cnt[i][j]:
                    cnt[i][j] = c
                    q.appendleft([c, i, j])

print(cnt[C][D])

E問題

1. 素数の偶数乗で$10^{12}$以下のものをすべて求め、ソートする
2. 同じ素数を用いていない組み合わせかつ積が$10^{12}$以下のものを書き出してソートする
3. 各クエリの$A$以下で最大の数をbisectで出力する

E

from bisect import bisect

def get_prime(limit):
    primes = [False] + [True] * limit
    primes[1] = False
    i = 2
    while i * i <= limit:
        if primes[i]:
            for j in range(i * i, limit + 1, i):
                primes[j] = False

        i += 1

    return [i for i in range(limit + 1) if primes[i]]


prime = get_prime(10 ** 6)
maxi = 10 ** 12
lst_i = list()
for p in prime:
    p_i = p ** 2
    while p_i <= maxi:
        lst_i.append([p_i, p])
        p_i *= p ** 2

lst_i.sort()
lst = set()
for i in range(len(lst_i)):
    for j in range(i):
        if lst_i[i][0] * lst_i[j][0] <= maxi:
            if lst_i[i][1] != lst_i[j][1]:
                lst.add(lst_i[i][0] * lst_i[j][0])
        else:
            break

lst = sorted(lst)

for _ in range(int(input())):
    print(lst[bisect(lst, int(input())) - 1])