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}$の計算の高速化を行っています。

この記事はここまでとします。