茶AtCoder：ABC322の回答と感想

ABC322 回答と感想

パフォ：759
レート：438 → 479 (+41)

今回は久しぶりにA~Cまですんなり解くことができ、レーティングもHighestを更新できました。D問題は、問題文が頭に入ってこなかったためパスしましたが、もう少し粘ったほうが良かったかもしれないと思います。

A問題：AC 2分45秒

与えられた文字列に対して、文字列ABCが含まれているか、含まれているならどの位置に出現するかを判定する問題です。Strオブジェクトのfind()メソッドを使って出現位置を取得しています。このコードではABCを@に変換していますが、S.find("ABC")と実装しても出来ましたね。

提出コード(一部略)

import sys

input = lambda: sys.stdin.readline().rstrip()
intinput = lambda: int(input())

N = intinput()
S = input()

if "ABC" in S:
    newS = S.replace("ABC", "@")
    print(newS.find("@") + 1)
else:
    print(-1)

B問題：AC 3分34秒

与えられた文字列について、接頭辞・接尾辞であるかどうかを判定する問題です。Strオブジェクトのstartwithを使って先頭に含まれるかどうかを、endwithを使って後ろに含まれるかどうかを判定しました。出力は問題文の指示通りに実装しました。A問題もそうでしたが、問題の読解にかかる時間を短縮できるようにしたいと思います。

提出コード(一部略)

mapint = lambda: map(int, input().split())

N, M = mapint()
S = input()
T = input()

pre = T.startswith(S)
post = T.endswith(S)

if pre and post:
    print(0)
elif pre and not post:
    print(1)
elif not pre and post:
    print(2)
elif not pre and not post:
    print(3)

C問題：AC 12分7秒

「次に花火が打ち上げられるのは何日後か」をそれぞれ求める問題です。花火が打ち上げられる日程をソートした上で、二分探索bisect_leftを使って「次に花火が打ち上げられる日」を取得し、何日後かを計算しています。(制約をちゃんと見ればソートする必要は無かったけど)計算量はO(NlogN)らしいです。

配列Aを降順にソートしてから計算することでO(N)で解くことも出来るということですが、自分なりに簡潔に実装できたと思います。

提出コード(一部略)

from bisect import bisect_left

mapint = lambda: map(int, input().split())
listmapint = lambda: list(mapint())

N, M = mapint()
A = listmapint()
setA = set(A)
A.sort()

for i in range(1, N + 1):
    if i in setA:
        print(0)
        continue
    next = bisect_left(A, i)
    print(A[next] - i)

いったん、ここまで。