AIで解説 AtCoder攻略　文字列一致

文字列一致ページの位置づけ

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

文字単位の走査からKMP法・Z algorithmまで、文字列の一致位置や連続条件を同じ添字処理として練習します。

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

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

最初の一問として、ABC236 A chukodai（公式解説）を解きます。指定された2箇所の文字を入れ替えます。文字列をlistに変換してから添字で交換し、最後にjoinで戻します。

S = list(input().strip())
A, B = map(int, input().split())
S[A - 1], S[B - 1] = S[B - 1], S[A - 1]
print(''.join(S))

交換と出力を含めてO(N)時間・O(N)メモリです。

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

問題	公式解説	出題意図	difficulty
ABC336 A Long Loong	公式解説	Official editorial intent is classified as fixed length string insertion.	-1289
ABC436 A o-padding	公式解説	Pad the numeric string on the left with zeroes to the required width.	-1226
ABC279 A wwwvvvvvv	公式解説	Give weight 1 to w and 2 to v and sum the string weight.	-1224
ABC236 A chukodai	公式解説	文字列の指定された2位置の文字を入れ替えて出力する。	-1207
ABC388 A ?UPC	公式解説	入力の先頭大文字にUPCを連結して出力する。	-1184

問題	公式解説	出題意図	difficulty
ABC264 A "atcoder".substr()	公式解説	固定文字列の指定区間を切り出す。	-1180
ABC189 A Slot	公式解説	Check whether all three slot symbols are identical.	-1145
ABC232 A QQ solver	公式解説	`a×b`形式の2桁を文字から整数へ変換して掛け算する。	-1137
ABC399 A Hamming Distance	公式解説	Count positions at which the two strings have different characters.	-1129
ABC329 A Spread	公式解説	Reverse the input string.	-1120

問題	公式解説	出題意図	difficulty
ABC251 A Six Characters	公式解説	文字列を繰り返して6文字にし、先頭6文字を出力する。	-1113
ABC402 A CBC	公式解説	公式Editorialの方針を cbc string transform として整理する。	-1084
ABC382 A Daily Cookie	公式解説	指定位置以降のクッキー文字数を単純に数える。	-1062
ABC358 A Welcome to AtCoder Land	公式解説	Official editorial intent is classified as string equality.	-1054
ABC374 A Takahashi san 2	公式解説	文字列が指定されたsanで終わるかを判定する。	-1054