2020年 11月 3.9
日
まえがき
(茶diff)やんないんじゃない，出来ないんです．(ｽﾔｧ)
本文
下のモンダイ，まじで分からなすぎて発狂しかけたので，とりあえず書くだけ書いといた（自己満足)，でもめっちゃ長いし俺数学的素養とかないから，この記事の解説探してるひとは，AGC048で検索かけて他のひとの記事を見ることをオススメしときます．
基本的になぐり書きで，足りない部分とか一切考えてないから，これで完璧に証明もできてる！なんて思っちゃだめだよ
AGC048 A- atcoder < S
- [文字列,ちょっとだけ見ればいい]
このモンダイ難しくないですか...??解説見ても最初わからんかった．解説記事漁ってやっと理解出来たわ．
文字列S = "aaaaaaaa...a" (aだけの文字列)の時
どう頑張っても "atcoder" < S にすることは出来ない
なんでかっていうと，全部同じ'a'っていう文字だから，i文字目とi+1文字目をswapしたところで文字列に変化が一切起きない．
結果として"atcoder" < Sまで持っていけない．(伝われ)文字列Sが，'a'以外の文字('b' ~ 'z')を含んでいる時．
S= "aaaaaak" のとき，kを最初に持ってきて S = "kaaaaaa" となるまで操作します．
こうすることで "atcoder" < "kaaaaaa" となるので，"atcoder" < Sという条件を満たすことが出来ます．
こういう感じで，'a'以外の文字を含んでいれば，その文字を一番最初に持ってくることで，必ず"atcoder" < Sとなりますね．(atcoderはアルファベット順で一番若い'a'から始まっているので,'a'以外スタートの文字列は必ず"atcoder"よりも辞書順で後)
しかもこの時，'a'以外の文字が't'よりも後のアルファベット('u','v','w','x','y','z')の時，更に一手分だけお得似できます
見てイキましょう
(最近エッチだから行くがカタカナに鳴っちゃう…)
S = "aaaaaaaaz"
この時，'z'を最初にもって来る操作をして S = "zaaaaaaa"('a'の数テキトウだから合ってないかも.ユルシテ)
これで"atcoder" < "zaaaaaaaa" (=S)とすることが出来ました．
しかし，早まるな．待って．
これさ，'z'を二番目(1-indexed)に持ってきても条件を達成できるんですよね．
見て．
"atcoder" < "azaaaaaaa" (=S)
分かる？ 縦に並べるとわかりやすいかな？
"a t c o d e r"
"a z a a a a a a a a"
ほら，"at"の部分と"az"の部分を比較して，1文字目が一致．二文字目が't' < 'z'だから"atcoder" < "azaaaaaaa"なんだよ！！
だから，'z'を一番前に持ってくるよりも1手swapが少なく"atcoder" < Sとなるように出来るんだ！！
一応注意点として，'t'よりも後のアルファベットの時は2番目に持ってくることで条件が達成出来るけど，'b'~'t'の時はダメだよ
例えばS="aaaaaat"のとき，tを2番めに持ってきたって
"ataaaaa"
"atcoder"
この2つで比較して，"atcoder" > "ataaaa"だもん．
だから，この時は't'を一番最初に持ってきて
"atcoder" < "taaaaa" としなきゃ条件を達成出来ない．
ここで出てくる疑問として，「えｗｗじゃあ，'c'より後のアルファベットを3文字目に持ってきた方が操作回数少なくて済むんじゃないの〜〜WWW」って，多くの水色コーダーの方は思うと思います（私もそうでした)
じゃあ，例えばS="aaaad"のとき,dを3番目に持ってきてみましょう
S="aadaa"ですね．
"a t c o d e r"
"a a d a a"
さて，これは2文字目の段階で't' > 'a' なので，"atcoder" > "aadaa"となり条件を満たせてイません．
水色コーダー「えええｗｗｗなんで〜WWWWWWW
't'より後のアルファベットを2文字目に持ってきた時は条件満たしてたのに，'c'より後のアルファベットを3文字目に持ってきても条件満たせないのなんで〜WWWなんでなんでWWWW」
聡明な皆さんならもうおわかりでしょう，なんと，'t'より後のアルファベットを2文字目に持ってきたときに条件が達成出来たのは，1文字目のアルファベットが"atcoder"と"azaaaa"の2つで'a'というアルファベットで一致していたからなのです！！（ここ日本語難しい)
だから，水色コーダー君は，"ataaaad"のときなら，'d'を3文字目に持ってくることで"atcoder" < "atdaaaa"を達成出来るんだな．というふうに理解をしましょうね．
さてさて，ここで水色コーダー君は考えます．
水色コーダー「1文字目まで"atcoder"と一致してるなら，'t'より後を探して〜，2文字目まで一致してるなら'c'より後を探して〜,3文字目まで一致してるなら'o'より後を探して〜WWW」
あはは，笑い者ですね（自虐)
先程の例，"ataaaaad" = S をもう一度考えます．この文字列，"atdaaaaa" = S とすることでも "atcoder" < Sと出来ます
しかし，2文字目まで一致してるなら，'c'より後を探す必要なんてなくて，2文字目まで一致してるなら，二文字目を一文字目に持ってきてしまえば条件達成出来るのです！！
S="ataaaaad"の't'を一文字目に持ってきて…
S="taaaaaad" これなら1手で条件を達成出来る!!!
長くなりました．要は，Sにどのように操作を施すかって言うと，
- 何かの文字を1文字目に持ってくる
- 何かの文字を2文字目に持ってくる
この二通りしか考えなくていいのです！！ S="at...."なら，tを一文字目に持ってくる．
S="aa...z"とかなら，'z'を2文字目に持ってくる
S="adz..."とかなら，'d'を1文字目に持ってきても，'z'を2文字目に持ってきてもどっちでもいい．
S="adaz"とかなら，'d'を一文字目に持ってくる方が，'z'を二文字目に持ってくるよりも手数が少ない．
とても長くなりましたね，じゃあやることをそろそろまとめます．
- S > "atcoder" なら0を出力．
- Sが'a'のみの文字列だったら，-1を出力
- その他の場合
- Sを全部見て，'a' < S[i] となる i で最小のものを取得する．
- Sを全部見て，'t' < S[j] となる j で最小のものを取得する.
iとj-1のうち，小さいほうが答え
あ，ここでのiとjは0-indexdにしてください．そうしたら，iはS[i]を0番目に持ってくるまでの手数， j-1はS[j]を1番目に持ってくるまでの手数となります．(かくにんしてみてね)
const int inf = 1e9; int main() { int n; cin >> n; string at = "atcoder"; int sz = at.size(); while(n--){ string s; cin >> s; if(at < s){ cout << 0 << endl; } else { int a = inf, b = inf; rep(i,s.size()){ if(s[i] > 'a'){ a = i; break; } } rep(j,s.size()){ if(s[j] > 't'){ b = j-1; break; } } int ans = min(a,b); cout << (ans == inf? -1 : ans) << endl; } } }
