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です。
C問題
問題
画像の文字起こし
文字列が与えられます。
その文字列が以下のルールを満たしている部分の最長を求めてください。
・スラッシュのみ、または、スラッシュを挟んで左側に1、右側に2が並ぶ
・1と2の長さが同じ
入力例1
211/2212
11/22の部分が満たしています。
入力例 2
22/11
/の部分が満たしています。
入力例3
/1211/2///2111/2222/11
111/222の部分が満たしています。
アプローチ
画像の文字起こし
文字列中のスラッシュをチェックしていきます。
チェックを軸に左側に1が、右側に2がどこまで並んでいるかをチェックします。
D問題
問題
画像の文字起こし
文字列が与えられます。
その文字列が以下のルールを満たしている部分の最長を求めてください。
・同じ値が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文字目が最長です。