ABC412をPythonで（A～E）

日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）の解答等の速報的まとめ

A問題

for文ループで確かめる

A

n = int(input())
ans = 0
for _ in range(n):
    a, b = map(int, input().split())
    ans += a < b

print(ans)

B問題

問題文の通りにシミュレートする

B

s = input()
t = set(list(input()))

ans = "Yes"
for i in range(1, len(s)):
    if s[i].isupper() and s[i - 1] not in t:
        ans = "No"

print(ans)

C問題

順番に、今倒れているドミノが倒せるドミノの中で最大のドミノを右に置く
大きさが同じかそれ以下のドミノを追加するときは、それを省いても倒れるので最小個数ではなくなる

実装はSortedListを使っているが、普通にソートしてbisectで調べればいい

C

from sortedcontainers import SortedList

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    sList = SortedList(a[1:-1])
    now, end = a[0], a[-1]
    count = 2
    while sList and now * 2 < end:
        ind =  sList.bisect_right(now * 2) - 1
        if ind < 0 or sList[ind] <= now:
            count = -1
            break
        count += 1
        now = sList[ind]

    print(count if now * 2 >= end else -1)

D問題

順番を全通り試す
頂点が3個あれば条件を満たすので、Nが６以上の時は２つに分割するパターンを計算する
計算方法は、すでにある辺をすべて消してから辺を新たにつなぐ
ただし、もとからあった辺を消してからつなぐのは無駄なので消さなかったことにする

D

from functools import lru_cache
from itertools import permutations

@lru_cache(maxsize=None)
def count_circle(pattern):
    res = 0
    for i in range(len(pattern)):
        before, now = pattern[i - 1], pattern[i]
        target = (before, now) if before < now else (now, before)

        if target in edges:
            res -= 1
        else:
            res += 1
    return res


n, m = map(int, input().split())
edges = set()
for _ in range(m):
    e_i = sorted(map(lambda x:int(x) - 1, input().split()))
    edges.add(tuple(e_i))

INF = float("inf")
ans = INF
for p in permutations(range(n)):
    ans_1 = count_circle(p)
    ans_2 = INF if n < 6 else count_circle(p[:3]) + count_circle(p[3:])
    ans_3 = INF if n < 7 else count_circle(p[:4]) + count_circle(p[4:])
    ans_4 = INF if n < 8 else count_circle(p[:5]) + count_circle(p[5:])
    ans = min(ans, min(ans_1, ans_2, ans_3, ans_4) + m)

print(ans)

E問題

問題の入力例１を見ると、素数と$8(2^3)$の時に最小公倍数が増加している
よって$L+1$~$R$の中にある素数および素数のべき乗の個数を数える（$L$は1つ目なので条件関係なく種類数を１つ増やす）

素数判定はエラトステネスの篩をすればいいが$10^{14}$は間に合わない
$10^7$までなら素数を求められるので先に求めた後、配列の０番目を$L+1$としたエラトステネスの篩で素数の判定をする
それと別に$L+1$~$R$に入る素数のべき乗の個数を数えて合計すれば答えとなる

E

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]]


l, r =  map(int, input().split())

prime = get_prime(min(10 ** 7, r))
lst = [True] * (r - l)
start = l + 1
beki_count = 0
for p_i in prime:
    p_j = p_i * p_i
    while p_j <= r:
        if l + 1 <= p_j <= r:
            beki_count += 1
        p_j *= p_i

    s = ((l + 1) // p_i) * p_i
    if s < l + 1: s += p_i
    if s == p_i:s += p_i
    for p_k in range(s, r + 1, p_i):
        lst[p_k - start] = False

print(1 + sum(lst) + beki_count)