競プロ初心者の挑戦日記①

概要

競技プログラミングの初心者が、コンテストに参加した記録です。
問題を回答するにあたって、使用する言語はPythonです。
自力で実装できないものは潔く諦めます。

対象コンテスト

AB問題のみ解けました。

A問題

所要時間：４分
特定の文字列が現れる最初のインデックスを出力する問題です。
単純にfindして結果を出力しました。

n = int(input())
s = input()

index = s.find('ABC')
if index == -1:
    print(index)
    exit()

print(index+1)

B問題

所要時間：７分
与えられた文字２つから、接頭語と接尾語が一致しているかどうかを判別する問題です。
こちらも単純に、関数で接頭語と接尾語をチェックして出力。

n, m = map(int, input().split())
s = input()
t = input()

st = t.startswith(s)
en = t.endswith(s)

if st and en:
    output = '0'
elif st:
    output = '1'
elif en:
    output = '2'
else:
    output = '3'
    
print(output)

C問題

所要時間：２１分（LTEで回答失敗）
全ての日数の最大値と特定の日数リストが与えられ、全ての日ごとに、特定の日数までの間隔を出力する問題です。
問題を理解するのに苦戦しました。

サンプルは次のコードで通りましたが、数値が大きくなるとダメですね。

n, m = map(int, input().split())
a = list(map(int, input().split()))

for i in range(1, n+1):
    if i in a:
        print(0)
        continue
    
    next = 0
    for day in a:
        if i < day:
            next = day
            break
        
    print(next - i)

C問題提出コードの問題点

リスト内の存在チェック

次のコードが遅すぎた。

if i in a:
    print(0)
    continue

特定の日数リストの全件ループ

力技の解決策に頼った結果。
ループでの検索は極力避けるべきですね。

next = 0
for day in a:
    if i < day:
        next = day
        break

C問題の改善後コード

二分探索を使用して、コード内の検索を高速化しました。

n, m = map(int, input().split())
a = list(map(int, input().split()))

def binary_search(a, x):
    left = 0
    right = len(a) 
    
    while left <= right:
        mid = (left + right) // 2
        if x > a[mid]:
            left = mid + 1
        else:
            right = mid - 1
    return right + 1

for i in range(1, n+1):
    index = binary_search(a, i)
    print(a[index] - i)

反省

C問題を提出してLTEを食らった時、二分探索が必要なのかなと思って諦めてしまいましたが、他の人のコードを見ていると、カウンタ（？）を更新して特定日を取得している人が多かったです。
これであれば既存の知識でも回答が可能だったかなと。
もう少し粘るべきでした。１つの考えに囚われるのは良くないですね。