競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - Registration
文字列Tは文字列Sの末尾に一個文字をつけたものになっているか答える問題です。
TをT[:-1]とスライスすることで比較しました。
S = input()
T = input()
if S == T[:-1]:
print('Yes')
else:
print('No')
B - Easy Linear Programming
1と書かれたカードが$A$枚、0と書かれたカードが$B$枚、-1と書かれたカードが$C$枚あります。この中から$K$枚を選ぶ時の最大値はいくつか答える問題です。
1, 0, -1の順番に優先して数えればいいです。ただし$A, B, C\leq2\times10^9$である点から、配列に入れたりforで回そうとすると痛い目にあいます。(一敗)
A, B, C, K = map(int, input().split())
out = min(A, K) - max(0, K-A-B)
print(out)
C - Skill Up
それぞれの番号ごとに合計した全ての要素が$X$を超えるような組み合わせの中で最小の価格を求める問題です。
$N, M \leq 12$という制限から十分に全網羅が可能です。全探索にはitertools.product(), ついでにnumpyを使用することで並列計算を行いました。
import itertools
import numpy as np
N, M, X = map(int, input().split())
items = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int32)
out = 10**18
for c in itertools.product([False, True], repeat=N):
tmp = np.sum(items[np.where(c)], axis=0)
if M == np.count_nonzero(tmp[1:] >= X):
out = min(out, tmp[0])
if out == 10**18:
print(-1)
else:
print(out)
D - Teleporter
それぞれの町は一個ずつワープ先が設定されています。最初の町からK回テレポートして到着する町を答える問題です。
$K\leq10^{18}$という制限からまともに探索すればTLEです。諦めました。他の人の解答を見ます。
Kの範囲は$K\leq10^{18}$でも、Nの範囲は$N\leq 2 \times 10^{5}$であるところに注目するべきでした。つまりこの探索は必ずループする。
まずは普通に探索。各町に最初に到達した時間t_zeroを配列として保存しておいて、同じ町に二回目の到達をしたら1周のための時間を計算。Kから一周の時間の剰余項を取る。残りの時間kで再び探索...するまでもなく、前にやった計算を再利用。以下のコードで通りました。
N, K = map(int, input().split())
A = list(map(int, input().split()))
t_zero = [-1] * N
t = 0
a = 1
while t_zero[a-1] == -1:
if t == K:
break
t_zero[a-1] = t
t += 1
a = A[a-1]
else:
k = (K - t_zero[a-1]) % (t - t_zero[a-1])
a = t_zero.index(t_zero[a-1] + k) + 1
print(a)
E - Colorful Blocks
横一列に並んだブロックを色分けする問題です。ただし、同じ色が隣り合うことが許容されるのはK個までで、何個組み合わせがあるでしょうか。
M色の色が隣り合わないようにN個並べる組み合わせは、$M\times(M-1)^{N-1}$個存在します。
K組のブロックが隣り合っていい時というのは$N-K$個のブロックを色が並ばないように並べる作業とも言えます。また、隣り合うブロックの組み合わせの選び方は$_{N-1} C _ {K}$個。
つまり以下の数式を計算すればいいことになります。
$$ \sum M\times (M-1)^{N-k-1} \times _{N-1} C _ k $$
実装したのが以下になります。ただし本番中はうまく計算速度を上げることができずに、時間内に解くことができませんでした。
N, M, K = map(int, input().split())
out = 0
mod = 998244353
c = 1
for k in range(K+1):
out += M * pow(M-1, N-k-1, mod) * c
out %= mod
c *= (N-k-1) * pow(k+1, mod-2, mod)
c %= mod
print(out)
ここでは
$$ Y^{p-2} \mod p \equiv {1\over Y} $$
という式(フェルマーの小定理の変形)を用いて、$Y^{-1}$の計算の高速化を行っています。
この記事はここまでとします。