AIで解説 AtCoder攻略　線形走査

線形走査ページの位置づけ

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

隣接要素の比較、ソート後の境界、漸化式など、状態を前へ渡す一方向の走査をまとめます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

最初の一問として、ABC291 A camel Case（公式解説）を解きます。文字列を左から見て、最初に大文字が現れる位置を返します。条件を満たす位置を見つけたら、それ以上調べる必要はありません。

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

最悪でも文字列を1回読むO(N)時間、O(1)追加メモリです。

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

問題	公式解説	出題意図	difficulty
ABC291 A camel Case	公式解説	英大文字の位置を探して1始まりで出力する。	-1162
ABC359 A Count Takahashi	公式解説	Official editorial intent is classified as count name.	-1075
ABC346 A Adjacent Product	公式解説	Official editorial intent is classified as adjacent product.	-1074
ABC277 A ^{-1}	公式解説	Find the one-indexed position of X in the array.	-1045
ABC351 A The bottom of the ninth	公式解説	Official editorial intent is classified as score difference.	-1028

問題	公式解説	出題意図	difficulty
ABC312 A Chord	公式解説	Accept exactly the six chord spellings in the fixed set.	-990
ABC457 A Array	公式解説	Scan the array and count values satisfying the condition.	-972
ABC396 A Triple Four	公式解説	Detect whether any three consecutive values are equal.	-958
ABC352 A AtCoder Line	公式解説	Official editorial intent is classified as station range check.	-946
ABC275 A Find Takahashi	公式解説	Output the one-indexed position of the maximum height.	-929

問題	公式解説	出題意図	difficulty
ABC337 A Scoreboard	公式解説	Official editorial intent is classified as score sum comparison.	-923
ABC297 A Double Click	公式解説	隣接クリック時刻の差がD以内の組を探す。	-900
ABC211 B Cycle Hit	公式解説	4試合の結果を走査し、文字列HITが一度でも現れるかを判定する。	-864
ABC357 A Sanitize Hands	公式解説	Official editorial intent is classified as hand count.	-824
ABC376 A Candy Button	公式解説	ボタン間隔がC以上のときだけ押下を数える。	-823