ARC088 E : Papple Sort(800)
作成日：2017.12.31
最終更新日：2017.12.31
問題概要
英小文字からなる文字列$S$に対し、操作「隣り合う2つの文字を入れ替える」を行う。
操作を繰り返すことで$S$を回文にできるかどうかを判定せよ。また、可能な場合は操作の最小回数を求めよ。
制約
$1 \leq |S| \leq 2 \times 10^5$
考え方
回文が作れない条件は奇数回登場する文字が2種類以上存在することである。
これは簡単に判定できるので、以下では回文を作れるとする。
回文となっている時、前から$i$番目の文字と後ろから$i$番目の文字は同じ種類である。
そこでまずは与えられた文字列$S$のうちどの2つの文字がペアになるかを考える。
異なる種類の文字は絶対にペアにならないので、同じ種類の文字だけを見れば良い。
同じ種類文字のうち2つを入れ替えても文字列自体は変わらない。
つまり同じ種類の文字を選んで操作を行うことは無駄であるから、初めに与えられた順序が保存されるとして良い。
よってペアは同じ種類の文字ごとに見た時の前から$i$番目の文字と後ろから$i$番目の文字で構成される。
但し文字列の長さが奇数の時はペアとなる文字は自分自身となる。
簡単のために2つのペアだけを見ることにする。
ペアの並びとしては$aabb$、$abab$、$abba$の3種類がある。
$S$が回文となっている時、ペアの並び方は$abba$となっていなければならない。
そのためには$aabb$に対しては操作を2回、$abab$に対しては操作を1回行う必要がある。
逆にこれをすべてのペアの組に対して考え、$abba$の並びにすれば$S$は回文になる。
必要な操作の回数の数え方を考える。
上記のペアの並びと操作回数の対応を見ると、最後に出てくる要素とペアとなっている要素より先に出てくる要素の数と一致している。
このことから、ペアのうち後に出てくる方の要素の位置でペアをソートして順に見ていき、先に出てくる方の要素より先に出ているすでに見たペアに含まれる要素の数を積算していけば良いことが分かる。
これはBITを用いれば$O(N \: log \: N)$で求められるから十分高速である。
ソースコード
マクロ等はこちら
BIT<T>
void add(int a , T b)
$a$番目の要素に$b$を加える
T get(int a)
先頭(0番目)から$a$番目の要素までの累積和を取得する
string S;
vector<int> c[26];
vector<P2> V;
BIT<int> bit;
int main(){
cin >> S;
int n = S.size();
repp(i,0,n){
c[S[i]-'a'].PB(i);
}
int z = 0;
repp(i,0,26){
repp(j,0,c[i].size()){
if(2*j >= c[i].size()) break;
if(2*j+1 == c[i].size()){
++z;
V.PB(MP(c[i][j],c[i][j]));
} else {
V.PB(MP(c[i][c[i].size()-1-j],c[i][j]));
}
}
}
if(z>1) return cout << -1 << endl , 0;
LL ans = 0;
sort(V.begin(),V.end());
for(auto u : V){
ans += bit.get(u.second-1) / (u.first == u.second ? 2 : 1);
bit.add(u.first,1);
if(u.first != u.second) bit.add(u.second,1);
}
cout << ans << endl;
return 0;
}解法まとめ
奇数回登場する文字が2種類以上存在する時、$S$を回文にすることは不可能である。(12,16,17,24行)
回文で対応する2つの文字をペアにし、ペアを後から出てくる要素の位置でソートする。
ペアを順に見ていき、先に出てくる要素より先頭に近いすでに見た要素の数を加えていったものが答えである。(13-32行)