日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）の解答等の速報的まとめ
for文ループで確かめる
A
n = int(input())
ans = 0
for _ in range(n):
a, b = map(int, input().split())
ans += a b
print(ans)
問題文の通りにシミュレートする
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)
順番に、今倒れているドミノが倒せるドミノの中で最大のドミノを右に置く
大きさが同じかそれ以下のドミノを追加するときは、それを省いても倒れるので最小個数ではなくなる
実装は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)
順番を全通り試す
頂点が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)
問題の入力例１を見ると、素数と$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)
Views: 0
