自分がコンテストでやった考察と実装を書いてみます.
目次
A問題 『Lacked Number』
問題ページ: A - Lacked Number
Difficulty: 22
考察
与えられた数字を全て set に持っておいて, set(range(10)) から引くと, set(range(10)) に含まれるが, もともとの数字に含まれない要素が取得できます.
任意の値の取得は s.pop() で取得できるので, それを出力すれば良いです.
実装
#!/usr/bin/env pypy3
s = set(map(int, list(input())))
s = set(range(10)) - s
print(s.pop())
B問題 『Slimes』
問題ページ: B - Slimes
Difficulty: 41
考察
一回ごとにスライムの数を B 倍するのをシミュレーションすればいいです.
A=1, B=10^9, C=2 の時に答えが最大になります. その時の答えは
\lceil \log_2 10^9\rceil = 30
なので, 間に合います.
実装
#!/usr/bin/env pypy3
a, b, k = map(int, input().split())
res = 0
while a < b:
a *= k
res += 1
print(res)
C問題 『Dice Sum』
問題ページ: C - Dice Sum
Difficulty: 787
考察
典型的なdp問題です.
dp[i][j] を長さ i-1で数列の和がjであるものの個数とします.
0 <= i <= n, 0 <= j <= mn <= 2500 です.
初期化は
dp = [[0] * (M + 1) for _ in range(n + 1)]
dp[0][0] = 1
であり, 更新は長さがi-1かつ最後の値が j-m 以上 j-1 以下である数列から条件を満たす数列が一意的に作ることができるので
dp[i][j] = \sum_{t=1}^{\min(j, m)} dp[i-1][j-t]
です.
更新に O(M) かかり, i, j の走査に O(NK) かかるので, 全体の計算量は O(MNK) となり, これでACすることができます.
なお, 更新と同時に$dp[i]$の累積和を計算するようにすれば 更新を$O(1)$で行うこともできます. この時の計算量は O(NK) となります.
実装
#!/usr/bin/env pypy3
n, m, k = map(int, input().split())
M = 2500
mod = 998244353
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(k + 1):
for t in range(1, min(j, m) + 1):
dp[i][j] += dp[i - 1][j - t]
dp[i][j] %= mod
print(sum(dp[n][:k + 1]) % mod)
D問題 『Range Count Query』
問題ページ: D - Range Count Query
Difficulty: 793
考察
inds[x] を 値がxであるインデックスを昇順に入れたリストとします.
すると, クエリでは値がXであり, インデックスが L 以上R 以下であるものの個数を返したいですが, これは二分探索によって O(log N) で求めることができます.
以上によって, 入力, 及びindsの構築にO(N), クエリの処理に O(Q log N) かかるので, 全体の計算量は O(max(N, Q log N)) であり, ACすることができます.
実装
#!/usr/bin/env pypy3
from bisect import bisect_left, bisect_right
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
inds = defaultdict(list)
for i, x in enumerate(A):
inds[x].append(i)
q = int(input())
for _ in range(q):
l, r, x = map(int, input().split())
l -= 1
r -= 1
res = bisect_right(inds[x], r) - bisect_left(inds[x], l)
print(res)
E問題 『K-colinear Line』
問題ページ: E - K-colinear Line
Difficulty: 1292
考察
まず, k==1 の時のみ答えが Infinity になる. 以下 k != 1 とする.
直線 L が異なる二点を通る直線として現れる回数を cnts[L] 書くこととします.
すると 直線 L 上に $k$ 個以上の点としてあらわれることの必要十分条件は, cnts[L] が $k$個の点から2つを選ぶ方法の個数 ${}_k \mathrm{C}_2 = k (k - 1) / 2$ 以上であることです.
最後に 二点を通る直線の表示について考えます.
二点 $(x_0, y_0), (x_1, y_1)$を通る直線は
(x_1-x_0) y + (y_0-y_1)x + x_0 y_1 - x_1 y_0 = 0
と表されます.
直線の表示を一意的にするため, $y$ の係数, $x$ の係数, 定数項 のそれぞれの部分を一意的に表しておきます.
\begin{align*}
a &= x_1 - x_0 \\
b &= y_0 - y_1 \\
c &= x_0 y_1 - x_1y_0
\end{align*}
とおきます. このとき
- $\gcd(a, b, c) = 1$.
- $a \neq 0$ の時: $a > 0$.
- $a = 0$の時, $b > 0$.
となるように正規化しておきます.
cntsの構築に O(N^2) かかるので, 計算量は全体で O(N^2) です.
実装
#!/usr/bin/env pypy3
from collections import Counter
from itertools import combinations
from math import gcd
n, k = map(int, input().split())
if k == 1:
print("Infinity")
exit()
poses = [None] * n
for i in range(n):
poses[i] = list(map(int, input().split()))
cnts = Counter()
for (x0, y0), (x1, y1) in combinations(poses, 2):
a = x1 - x0
b = y0 - y1
c = x0 * y1 - x1 * y0
g = gcd(gcd(a, b), c)
a, b, c = a // g, b // g, c // g
if a < 0:
a *= -1
b *= -1
c *= -1
elif a == 0 and b < 0:
b *= -1
c *= -1
cnts[(a, b, c)] += 1
res = 0
for c in cnts.values():
res += c >= k * (k - 1) // 2
print(res)