自分がコンテストでやった考察と実装を書いてみます.

目次

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)