Equalizing Two Strings - #598 div2 f
#文字列 #転倒数
解法
すべての文字に関して, 個数がs, tで同じでないといけない
反転する長さを2とする
1文字でも2つ以上出てたら必ずs, tを同じにできる
s, tをsortするが, 隣の文字のswap回数を同じにしないといけない
同じ文字があれば, そこでswapしてswap回数合わせられる
すべての文字が1つ以下なら,
swap回数の偶奇を合わせられるかが問題
swap回数は転倒数で求める
隣のswapでsortするのに必要な最小回数
= 前から見て, 自分より前で自分より大きいものの個数の総和
abdcなら, cにとってdの1個
eabfdcg
まず, 自分より前の自分より大きいものとswapし
続けるのが最適
1回のswapで, 隣の2数の大小関係しか変わらない
すなわち, (1)は1しか減らせない
隣の2数で, 前が後ろより大きい箇所がなければそれはsortし終わった
数列なので, (2)は常に可能
実は, 転倒数を使わなくていい
なぜなら, 同じ文字は現れないので, 最大26文字だから
コード
転倒数
https://codeforces.com/contest/1256/submission/67411007
2重ループ
https://codeforces.com/contest/1256/submission/67411813
