0.はじめに
土曜日がARCと珍しい感じ。1問も正解できず
レート落ちする恐れもありましたが、まぁ
今更気にしてもしょうがないので参戦。
なんとか1問正解でき、レートも微増となりました。
1.A - ABA and BAB
愚直に解いていくとTLEまっしぐらな問題であることは
わかるものの、最初はどうしていいかわかりませんでした。
まぁ2時間使うつもりでとりあえずTLE覚悟の愚直な
方法で実装
【考え方】
1.1回置換の操作を行うと、文字列の長さが2個減る
2.N=10の時、文字列の長さ毎のパターンは以下の5種
1)N=10、2)N=8、3)N=6、4)N=4、5)N=2
3.まず、N=10の文字列をリストL(set)に格納
～以下Lがなくなるまで繰り返し
4.Lから、一つずつ文字列を取り出し取り出すたびにansに1加算
5.取り出した文字列を先頭から見ていき
ABAかBABが出てきたら、置換した文字列を
リストNL(set)に格納していく
6.Lがなくなったら、LをNLで置き換え
7.ansを出力して終了
上記考え方で、例題3までは解けましたが、4は案の定TLE
例題3を上記考え方に通していい感じで解けないかを検討し
1)AとBが連続している部分は置換の対象にはならない
2)ABABA・・・とかBABA・・・とAとBが交互に連続している部分は
最終的に同じ型に帰結する＆最終型までのパターン数は一定
ということに気づきました。
さらに2)について最終型までのパターン数は
AとBが交互に出てきた数を2で割って1を足すことで計算可能と判明
例）
ABA →Aに対してB・Aと2回、交互出てきたとカウントして2//2+1の2パターン
（ABA、A）が発生
ABABA →Aに対して4回、交互出てきたとカウントして4//2+1の3パターン
（ABABA、ABA、A）が発生
上記をもとに考え、AとBが交互に出てくるパート毎のパターン数を
掛け合わせれば、答えが出ると気づきました。
例題3をもとにすると)
xの部分は返還の対象とならない部分として
1～3のパートに分かれる
x11111122222xx333
BBABABAABABAAAABA
1・2の部分は3パターンずつ、3の部分は2パターンが
発生するので、掛け合わせて、答えは18パターン
上記までの考察をもとに以下の実装
【実装】
1.NとSを入力
2.以下の変数を初期化
MOD(回答のMOD算出に使用) 初期値：10の9乗足す7
cnt(ABが連続する数をカウント) 初期値：0
pre(S参照時の前の文字) 初期値：""(空)
L(ABが連続する部分のパターン数)初期値：
3.文字列Sを添え字iで先頭から参照していく
-1.preが空の時、preにS[i]をセット
-2.preが"A"かつ、S[i]が"B"の時
・cntに1を加算し、preにS[i]をセット
-3.preが"B"かつ、S[i]が"A"の時
・cntに1を加算し、preにS[i]をセット
-4.-1～-3以外の時(preとS[i]が同じとき)
・cntが2以上の時、Lにcnt//2+1を追加
・cntに0をセットして、preにS[i]をセット
4.cntが2以上の時、Lにcnt//2+1を追加(ABの繰り返しのままSが終わったときの措置)
5.ansに1をセット
6.Lを先頭から読み込み、ansに乗算していく
7.ans％MODを出力
例題4が正解だったのでまぁ行けるかなと提出してAC頂けました。
https://atcoder.jp/contests/arc180/submissions/55020785
以上