LoginSignup
2
1

More than 1 year has passed since last update.

【AtCoder】PythonでABC247のA, B, C, D, Eを解く

Last updated at Posted at 2022-04-10

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

目次

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)
2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1