自分がコンテストでやった考察と実装を書いてみます.
目次
A問題 『Move Right』
問題ページ: A - Move Right
Difficulty: 14
考察
与えられる $S$ を $S_1, S_2, S_3, S_4$とすると, 答えは $0, S_1, S_2, S_3$ である.
pythonではリスト $S$ の最後の値を除いたものは S[:-1] と表すことができ, 文字列 $T$ と 文字列 $S$ を連結したものは $T + S$ と書くことができる.
よって, 解答は "0" + s[:-1] である.
リストの長さは $4$ しかないので, 計算量は考える必要がない.
実装
#!/usr/bin/env pypy3
s = input()
print("0" + s[:-1])
B問題 『Unique Nicknames』
問題ページ: B - Unique Nicknames
Difficulty: 202
考察
辞書 $cnt$ に対して $cnt[s]$ を文字列 $s$ が $s_j$ あるいは $t_j$ として現れた回数とする.
各 $1 \le j \le n$ に対して $a_j$ を選ぶことができるのは,以下のいずれかが成り立つ時である.
-
s_j != t_jかつs_jもしくはt_jはほかの文字列として現れない. -
s_j == t_jかつs_jが他に現れない.
cnt を使うと, これを判定する処理はそれぞれ $O(1)$ なので, 全体の計算量は $O(N)$ である.
実装
#!/usr/bin/env pypy3
from collections import Counter
n = int(input())
A = [None for _ in range(n)]
cnt = Counter()
for i in range(n):
A[i] = input().split()
cnt[A[i][0]] += 1
cnt[A[i][1]] += 1
res = True
for i in range(n):
res &= ((cnt[A[i][0]] == 1 or cnt[A[i][1]] == 1)
or cnt[A[i][0]] == 2 and A[i][0] == A[i][1])
if res:
print("Yes")
else:
print("No")
C問題 『1 2 1 3 1 2 1』
問題ページ: C - 1 2 1 3 1 2 1
Difficulty: 149
考察
列 $S_n$ の長さを $a_n$ と置く. $S_n$ の作り方より
\begin{align*}
& a_1 = 1, \\
& a_{n+1} = 1 + 2 a_n.
\end{align*}
これを解くと $a_n = 2^n - 1$ である. $a_{16} = 2^{16} - 1 = 65535$ である.
よってなにも考えずにリストの連結でしても $O(a_n) = O(2^n)$ なので, 、間に合う.
実装
#!/usr/bin/env pypy3
from collections import deque
n = int(input())
a = [1]
for i in range(2, n + 1):
a = a + [i] + a
print(*a)
D問題 『Cylinder』
問題ページ: C - Cylinder
Difficulty: 468
考察
典型的なdequeの問題.
要素の追加は append([x, c]) とすれば $O(1)$ で処理できる.
要素を取り出して合計を計算するのは, 前の方から取り出せるだけ取り出して, 合計を出力する.
この時, 取り出す回数は高々今まで追加した回数なので, 取り出す回数の合計は $O(Q)$ である.
よって, 計算量は全体で $O(Q)$ である.
実装
#!/usr/bin/env pypy3
from collections import deque
deq = deque()
q = int(input())
for _ in range(q):
t, *args = map(int, input().split())
if t == 1:
x, c = args
deq.append([x, c])
else:
assert t == 2
c = args[0]
res = 0
while c > 0:
if deq[0][1] <= c:
res += deq[0][0] * deq[0][1]
c -= deq[0][1]
deq.popleft()
else:
res += c * deq[0][0]
deq[0][1] -= c
c = 0
print(res)
E問題 『Max Min』
問題ページ: E - Max Min
Difficulty: 1256
考察
区間の最も右のインデックスを走査して, 全ての個数を足し合わせることを考える.
求める区間が成り立ってほしい条件は
- 区間の全ての値は $x$ 以上 $y$ 以下である.
- 区間に $x$ がある.
- 区間に $y$ がある
である.
それぞれの考えられる区間について, 走査する際に, 区間の最も左のインデックス left, $x$ が出てくる最も右のインデックス rightx, $y$ が出てくる最も右のインデックス righty を計算します. それと同時に答えを更新します.
答えの更新について考えます. 区間の最も左の値は left 以上かつ p = min(xright, yright) 以下の値を取るので, p - left + 1 を解答に追加すれば良いです.
それそれのインデックスの走査に対して, 計算量は $O(1)$ なので, 計算量は $O(N)$ です.
実装
#!/usr/bin/env pypy3
n, x, y = list(map(int, input().split()))
A = list(map(int, input().split()))
left = None
xright = None
yright = None
res = 0
for right, a in enumerate(A):
if y <= a <= x:
if left is None:
left = right
if A[right] == x:
xright = right
if A[right] == y:
yright = right
if xright is not None and yright is not None:
p = min(xright, yright)
res += p - left + 1
else:
left = None
xright = None
yright = None
print(res)