AtCoder Beginner Contest 381 のB問題〜D問題をPythonで解説します。

提出コード

B問題

画像の文字起こし

文字列が与えられます。
その文字列が以下のルールを満たしているかを求めなさい。
・同じ値が2個並んでいる
・同じ値は2つのみ現れる

入力例 1
aabbcc
a,b,cどれも満たしています。

入力例 2
aab
aは満たしていますが、bが満たしていません。

入力例3
ZZZZZZ
zが6つも現れているので、満たしていません。

画像の文字起こし

ルールをそれぞれ判定していきます。
同じ値が2個並んでいる
1文字ずつチェックしていき、右に同じ文字がなければNGです。
最後までNGがなければOKです
ステップを2にすることで、効率よく判定できます。

同じ値は2つのみ現れる
各文字ごとの出現回数を取得して、全ての文字が2回ずつ現れていたらOKです。

画像の文字起こし

文字列が与えられます。
その文字列が以下のルールを満たしている部分の最長を求めてください。
・スラッシュのみ、または、スラッシュを挟んで左側に1、右側に2が並ぶ
・1と2の長さが同じ

入力例1
211/2212
11/22の部分が満たしています。

入力例 2
22/11
/の部分が満たしています。

入力例3
/1211/2///2111/2222/11
111/222の部分が満たしています。

画像の文字起こし

文字列中のスラッシュをチェックしていきます。
チェックを軸に左側に1が、右側に2がどこまで並んでいるかをチェックします。

画像の文字起こし

文字列が与えられます。
その文字列が以下のルールを満たしている部分の最長を求めてください。
・同じ値が2個並んでいる
・同じ値は2つのみ現れる

入力例 1
23112211
1122の部分が満たしています。

入力例2
122
22の部分が満たしています。

入力例3
1
満たしている部分はありません。

画像の文字起こし

尺取り法で実装できます。
まず左端を決めます。
その後、1文字おきに文字をチェックしていき、どこまで条件に合うかをチェックします。
1文字おきのチェックでは、取りこぼしが出てくるので、偶奇それぞれのインデックスでチェックをします。
7、8文字目のチェックの次は2、3文字目のチェックをします。

NGな条件は以下の通りです。
この条件に当てはまった際は、左端を右に移動し、そこからチェックを再開します。
・右隣が異なる時
・同じ値がチェック中に再登場した時

右隣が異なる時
1文字目は2文字目と値が異なるのでNGです。
この場合、左端を右に2つ移動します。

同じ値がチェック中に再登場した時
1文字目の後、5文字目に再度1が出てくるので、NGです。
この場合、左端をチェックの直前に登場した同じ値から右に2つ移動します。

11223322という文字列で考えます。
3文字目の後、7文字目に再度2が出てきます。
この場合、左端は5文字目に移動します。
3文字目には移動しない理由は、3文字目の2からチェックをしても、後にまた2が再登場してくることが分かっている為です。

画像の文字起こし

23112211という文字列のシミュレーションを考えます。

最初の左端は1文字目からスタートします。
1文字目は2文字目と値が異なるのでNGです。左端を右に2つ移動します。

左端は3文字目です。
3文字目と4文字が同じで、値の再登場もないので、OKです。左端はそのままです。

左端は3文字目のままです。
5文字目と6文字が同じで、値の再登場もないので、OKです。左端はそのままです。

左端は3文字目のままです。
7文字目と8文字が同じですが、1が再登場しているので、NGです。
左端を直前の1から右に2つ移動します。

左端は5文字目です。
5文字目と6文字が同じで、値の再登場もないので、OKです。左端はそのままです。

左端は5文字目のままです。
7文字目と8文字が同じで、値の再登場もないので、OKです。
しかし、未尾まで来たので、左端を右に2つ移動します。

左端は7文字目です。
7文字目と8文字が同じで、値の再登場もないので、OKです。
しかし、未尾まで来たので、今度は左端を奇それぞれのインデックスをする為、2文字目に移動します。

左端は2文字目です。
以降は、類似の処理が続く為省略しますが、結果は3~6文字目および5~8文字目が最長です。