codeforces.com 概要 長さが100万以下の文字列Sが1つあたえられる。構成されてる文字は、アルファベットの最初の20文字、すなわち'a' ~ 't'である。これの連続部分文字列を1つ選んで、1回だけ反転してよい。(しなくてもよい) 操作を終えた時、文字列Sの連続…

codeforces.com 概要 2つの長さNの文字列S, Tが与えられる。次の操作を任意回行えるとして、SとTを一致させることはできるか？ x 同時に反転させる。 例えば、S="sen", T="shojin"でx=3の連続部分列を次のように選べる。 S'="sen", T'="hoj" これを同時に入…

atcoder.jp 概要 ある文字列sが存在し、次の操作を考える。 sの空でない連続部分文字列を1つ選び、これをpとする。pのそれぞれの番目を'?'に置き換えるorそのままにする。 この操作で得られた3つの文字列、a, b, cが存在するとき、元のsの最短の長さを答えよ…

このサイトが詳しい。drken1215.hatenablog.com次のような問題を考える。 文字列S(|S| a, b, rが与えられて、S[a, a + r], S[b, b + r]が同じ連続部分文字列かどうかを判定せよ。 いい感じに前処理をして、クエリ1回ごとにかかる計算量O(1)とかO(log N)でな…

新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのよう…

codeforces.com 概要 '('と')'のみが含まれる文字列S, Tが与えられる。次の条件を満たす文字列Xを構成してください。 SとTはどちらもXの部分文字列である。 Xはかっこ列としてすべての'(' と ')' は対応されていて、かつその2文字からのみ成る。 Xの長さはあ…

codeforces.com 概要 t個の文字列が与えられる。それぞれの文字列は'a', 'b', 'c', '?'で構成されてる。各文字列に対して、'?'は'a' or 'b' or 'c'にすることができる。それぞれの文字列の’?’をうまく差し替えた時、同じ文字が隣り合わないような文字列の差…

atcoder.jp 概要 偶数長'(', ')'からのみなる列(size 今カーソルは一番左を指している。コスト１を使って、次の操作のうちのいずれかを行える。 カーソルを左右に動かす(動かせるなら)。 カーソルの指してる文字を変更する。'(' -> ')' とか ')' -> '(' であ…

atcoder.jp 概要 最大10万長の文字列Sが与えられる。"yahoo"を0以上の任意の整数回繰り返した文字列とSの編集距離の最短を答えよ。

atcoder.jp 概要 文字列S, T(長さが最大 10^5)は'A', 'B'のみで構成されてる。 あなたは、 1. A -> BB , B -> AAに置換 2. AAA ->(nothing), BBB -> (nothing) と、3つ連続の同じものを消す ことを好きな回数だけ行える。この時、Q回(1 Sの[a, b]をTの[c, d]…

atcoder.jp 概要 100文字までの文字列SをK(1