AtCoderの一方向走査で状態更新を見分ける4問

一方向走査を選べるのは、入力を問題文の定める順序で一度ずつ見れば、現在の答えが「今の要素」と「それまでに保持した小さな状態」から決まるときです。最初に、何を状態として持つか、どの条件で更新するか、比較の境界を含むか、出力位置が1-originかを決めます。ABC291 AとABC277 Aは一致した位置を1-originで出力し、ABC297 Aは失敗したクリックも次の比較の直前要素にします。一方、ABC376 Aは飴を受け取れた時刻だけを次の基準にします。

この4問の並びは、公式が指定する学習順ではありません。状態の違いを比べるための編集上の順序です。

問題	持つ状態	判定と更新	出力と境界
ABC291 A	現在位置と最初の一致	大文字なら停止	大文字の1-origin位置。先頭は1
ABC297 A	直前のクリック	毎回、現在のクリックを次の直前要素へ進める。差が `D` 以下なら停止	最初の成立時刻。差が `D` と等しい場合も成立
ABC376 A	最後に飴を受け取った時刻	差が `C` 以上の成功時だけ個数と時刻を更新	受け取った個数。失敗押下は基準時刻にならない
ABC277 A	現在の1-origin位置	`P_i == X` なら停止	目的値の位置。先頭・末尾も1-origin

最初の一致と1-originを確認する：ABC291 A

ABC291 Aの公式問題文（入力条件と出力）では、英大文字と英小文字だけからなる長さ2以上100以下の文字列Sに、大文字がちょうど1個含まれます。Sの先頭を1文字目として、大文字の位置を出力する問題です。ABC291 Aの公式解説（文字を順番に調べる方法）も、Sの各文字を順に調べて大文字かを判定する方法を示しています。

公式サンプルの aBc を左から追います。位置1の a は大文字ではないので通過し、位置2の B で最初の一致になります。ここで 2 を出力して止めます。Zz なら先頭の1、xxxxxxXxxx なら7です。大文字がちょうど1個という制約があるため、最初の一致が答えになります。「最初の一致」と整理すること自体は、公式制約を横断して説明するための表現です。

s = input().strip()
for index, char in enumerate(s, start=1):
    if char.isupper():
        print(index)
        break

走査した位置まで大文字がなければ、まだ答えは見つかっていません。初めて isupper() が真になった位置は、唯一の大文字の位置なので正しい答えです。enumerate(s, start=1) により、Pythonの添字変換を別に書かず問題文の1-originを使えます。

文字列を左から一度調べるため、時間計算量は O(|S|)、追加メモリは O(1) です。大文字が先頭なら1、末尾なら |S| を出力します。公式制約で大文字は必ず1個あるため、見つからない場合の出力分岐はありません。

失敗しても直前要素を更新する：ABC297 A

ABC297 Aの公式問題文（クリック時刻の条件と出力）では、厳密に増加するクリック時刻列について、隣り合うクリックの差が D 以下なら後の時刻でダブルクリックが成立し、最初の成立時刻を出力します。成立しなければ -1 です。ABC297 Aの公式解説（隣接する時刻を調べる方法）も、T[i] - T[i-1] <= D を順に調べ、最初に成立した後の時刻を返す方法を示しています。

公式サンプル1の N=4、D=500、T=[300,900,1300,1700] を追います。最初の差は 900-300=600 なので失敗します。ただし、次に調べる組は 900 と 1300 です。失敗したクリック時刻900も、次の比較の直前要素として使います。1300-900=400 は D 以下なので、1300を出力します。差がすべて100で D=99 のサンプルは -1、差がちょうど500の [100,600,1100,1600] では600です。

n, d = map(int, input().split())
t = list(map(int, input().split()))
answer = -1
for i in range(1, n):
    if t[i] - t[i - 1] <= d:
        answer = t[i]
        break
print(answer)

時刻は増加順なので、隣り合う組を左から調べれば、最初に差が D 以下になった現在時刻が最初の成立時刻です。全ての組が失敗したときは、初期値 -1 が残ります。コードの t[i - 1] は毎回ひとつ前のクリックを表し、失敗したかどうかに関係なく次の組へ進みます。

入力配列を保持するコードなので、時間計算量は O(N)、追加メモリは O(N) です。判定に必要な直前時刻だけを読みながら進める実装なら状態自体は O(1) ですが、この掲載コードは時刻列をリストにしています。N=1 なら隣接する組がないため -1 です。差がちょうど D のときは <= に含まれるので成立します。

最後に飴を受け取った時刻だけを更新する：ABC376 A

ABC376 Aの公式問題文（押下時刻と受け取り条件）では、ボタンを押すと飴を1個受け取りますが、前回飴を受け取ってからの経過時間が C 秒未満なら受け取れません。ABC376 Aの公式解説（最後に受け取った時刻を使う方法）は、受け取った個数と最後に飴を受け取った時刻を持ち、差が C 以上のときだけ両方を更新します。

指定された区別ケース N=4、C=5、T=[0,3,6,9] を追います。最初の時刻0では1個受け取り、last_received=0 です。時刻3は 3-0=3<5 なので失敗しますが、last_received は0のままです。時刻6では 6-0=6>=5 となって2個目を受け取り、基準時刻を6へ更新します。時刻9は 9-6=3<5 なので失敗し、最終的な個数は2です。

n, c = map(int, input().split())
t = list(map(int, input().split()))
candies = 1
last_received = t[0]
for current in t[1:]:
    if current - last_received >= c:
        candies += 1
        last_received = current
print(candies)

最初の押下は必ず成功します。その後の押下では、直前の押下時刻ではなく、最後に飴を受け取った時刻との差だけが条件を決めます。条件を満たしたときだけ candies と last_received を更新し、満たさないときは状態を保持するので、最後の candies が受取数になります。

このコードは入力配列を保持するため、時間計算量は O(N)、追加メモリは O(N) です。走査中の状態である candies と last_received は O(1) です。N=1 なら最初の1個だけで1、T_1=0 も入力条件に含まれます。差がちょうど C のときは >= に含まれるので受け取れます。

同じ時刻列 `[1,7,10,15]` を閾値5で追う	ABC297 A（`D=5`）	ABC376 A（`C=5`）
開始	直前クリックは1	1回目を受け取り、最後の成功時刻は1
時刻7	`7-1=6>5` で失敗。ただし次の直前クリックを7へ更新	`7-1=6>=5` で成功し、個数を2、最後の成功時刻を7へ更新
時刻10	`10-7=3<=5` で成立し、10を出力して停止	`10-7=3<5` で失敗。最後の成功時刻は7のまま
時刻15	ABC297 Aは10で停止済み	`15-7=8>=5` で成功し、個数は3

この同じ列では、ABC297 Aの失敗は次の比較の基準を進めます。ABC376 Aでは、失敗押下そのものが起きる時刻10を基準にせず、最後に成功した7を使い続けます。比較演算子も、ABC297 Aは <=D、ABC376 Aは >=C です。

目的値の位置を1-originで出力する：ABC277 A

ABC277 Aの公式問題文（置換と目的値の位置）では、(1,2,...,N) の置換 P と X が与えられ、P_k=X を満たす k を出力します。ABC277 Aの公式解説（位置を順に調べる方法）は、各位置で P_i=X かを確認し、Pythonの0-basedループから出力するときは1を足す点を説明しています。

公式サンプル1の N=4、X=3、P=[2,3,1,4] では、位置1の値2は不一致で、位置2の値3が一致します。したがって出力は2です。公式サンプル2の目的値は末尾の位置5、サンプル3の目的値も末尾の位置6なので、先頭と末尾のどちらでも1-originで数えることを確認できます。

n, x = map(int, input().split())
p = list(map(int, input().split()))
for index, value in enumerate(p, start=1):
    if value == x:
        print(index)
        break

配列を左から調べ、P_i=X となった位置を出力します。P は置換なので一致する位置は1個だけで、最初の一致が唯一の答えです。enumerate(p, start=1) により、コード内の位置と問題文の1-originが一致します。

時間計算量は O(N)、入力配列を保持する追加メモリは O(N) です。N=1 なら P=[1]、X=1 なので答えは1です。目的値が先頭でも末尾でも、0-basedの値をそのまま出力せず1-originの位置を出力します。置換制約により、見つからない場合の分岐は想定しません。