AtCoder Beginners Contest 過去問チャレンジ6
ABC090D - Remainder Reminder
a を b で割った余りが K 以上ということは、b は K + 1 以上なのが確定. b で割った余りは 0..b-1 で、この1周期に出現する K 以上の個数は b - K となる. a は N 以下なので、周期数は N / b となる. 後は周期の余りについて考える必要があるが、ところで N は1から始まるので、周期は 1, 2, ..., b - 1, 0 の順となる. つまり N % b が n の場合、1, 2, ..., n となり、K = 0 と K = 1 の個数が同じとなることに注意.
N, K = map(int, input().split())
result = 0
for b in range(K + 1, N + 1):
result += (N // b) * (b - K) + max(N % b - max(K - 1, 0), 0)
print(result)
ABC115D - Christmas
レベル L バーガーの層数とそれに含まれるパティの枚数は N≤50 なので簡単に計算できる(し、ループを回して計算しなくても簡単に求める数式は導出できる). あとは X が尽きるまで再帰的に進めば良い. レベル L バーガーに遭遇して、残ってる X がレベル L バーガーより大きければ、X をその層数だけ減らして、カウンタにそのパティ数を追加し、小さければレベル L - 1 バーガの中に入っていけば良い.
N, X = map(int, input().split())
def f(N, X):
result = 0
if X >= 1:
X -= 1
else:
return result
if X >= 2 ** ((N - 1) + 2) - 3:
X -= 2 ** ((N - 1) + 2) - 3
result += 2 ** ((N - 1) + 1) - 1
else:
return result + f(N - 1, X)
if X >= 1:
X -= 1
result += 1
else:
return result
if X >= 2 ** ((N - 1) + 2) - 3:
X -= 2 ** ((N - 1) + 2) - 3
result += 2 ** ((N - 1) + 1) - 1
else:
return result + f(N - 1, X)
if X >= 1:
X -= 1
else:
return result
return result
print(f(N, X))
ABC053D - Card Eater
ダブっているカードが3枚以上あれば、どう3枚選んでもカードの種類数を減らさずダブリを2枚減らせる. ダブっているカードが2枚の場合、片方のダブっているカード2枚ともう片方のダブっているカード1枚でカードの種類数を減らさずダブリを0にできる. ダブっているカードが1枚の場合はダブっているカード2枚とその他のカード1枚で、カードの種類数は1減るがダブリを0にできる. 結局のところ答えはカードの種類数から、ダブり数が奇数の場合は1、偶数の場合は0を引いたものとなる.
N = int(input())
A = list(map(int, input().split()))
t = len(set(A))
if (len(A) - t) % 2 == 0:
print(t)
else:
print(t - 1)
ABC072D - Derangement
pi = i の場合には、pi と pi+1 でスワップし、その回数を数えればいいだけ. pN = N のときだけ、一つ前の pN-1とスワップ. pi は 1..N の順列なので、スワップすれば必ず pi != i になるし、当然 pi+1 != i なので pi+1 も必ず大丈夫になる. 1回で処理できる連続する pi = i をバラバラに2回で処理しないためにも、順番にやるのが最善なのは明らか.
N = int(input())
p = list(map(int, input().split()))
result = 0
for i in range(N - 1):
if p[i] != i + 1:
continue
result += 1
p[i], p[i + 1] = p[i + 1], p[i]
if p[N - 1] == N:
result += 1
print(result)
ABC040D - 道路の老朽化対策について
どう考えてもサイズ付き UnionFind を使うことは明白で、後は年でソートして、順次道路を追加しながら、国民が行き来できる都市の個数を確認していくだけ.
from sys import setrecursionlimit
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
setrecursionlimit(10 ** 5)
N, M = map(int, input().split())
roads = []
for _ in range(M):
a, b, y = map(int, input().split())
roads.append((y, a - 1, b - 1))
Q = int(input())
citizen = []
for i in range(Q):
v, w = map(int, input().split())
citizen.append((w, v - 1, i))
parent = [-1] * N
roads.sort(reverse=True)
results = [None] * Q
t = 0
for c in sorted(citizen, reverse=True):
while t < M and roads[t][0] > c[0]:
unite(parent, find(parent, roads[t][1]), find(parent, roads[t][2]))
t += 1
results[c[2]] = -parent[find(parent, c[1])]
print(*results, sep='\n')
ABC129E - Sum Equals Xor
L = XXXX の時、条件を満たす組の数を n とする. L = 1XXXX の時に条件を満たす組の数は 0～1111 で条件を満たす組の数と 10000～1XXXX で条件を満たす組の数の合計となる. ところで YYYY + ZZZZ = YYYY xor ZZZZ だとすると、1YYYY + ZZZZ = 1YYYY xor ZZZZ は成立するし、YYYY + 1ZZZZ = YYYY xor 1ZZZZ も成立する. つまり 10000～1XXXX で条件を満たす組の数は 2 * n となる.
L = 1 のとき条件を満たす組の数は (0,0),(0,1),(1,0) で3つである. L = 11 のとき条件を満たす組の数は上述の通り 0～1 = 3 と 10～11 = 2 * 3 の合計となり 3 * 3 = 9 となる. 同様に L = 111 は 9 * 3 = 27 となり、L = 1111 は 34 = 81 となる. 結果として L = 1XXXX のとき条件を満たす組の数は 2 * n + 34 となる.
ここまでくれば、下の桁から一桁づつ計算して、答えを求めることができる.
L = input()
result = 1
t = 1
for c in L[::-1]:
if c == '1':
result = result * 2 + t
result %= 1000000007
t *= 3
t %= 1000000007
print(result)