実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 469
問題概要
文字列 に対して次の操作をちょうど1回行った後の文字列としてあり得るものの個数を求めよ。
操作 : の任意の2文字を選び、その2文字の位置を入れ替える。
制約
- は英小文字からなる長さ 以上 以下の文字列
考察
選んだ2文字の種類が同じ場合と異なる場合とで、場合分けしてみる。S = aabbbcd
を例として考えよう。
同じ種類の場合
例えば、 の3文字目のb
と5文字目のb
を選んだとき。この場合、位置を入れ替えてできる文字列 はaabbbcd
となり、 に一致する。これは1文字目のa
と2文字目のa
を選んだときなども同様である。
つまり、同じ種類の文字を選んだ場合は、その文字の種類に関わらず そのもの1通りが作り出せるのである。
異なる種類の場合
例えば、 の1文字目のa
と3文字目のb
を選んだとき。この場合、 はbaabbcd
となる。また、 の2文字目のa
と5文字目のb
を選んだときは、 はabbbacd
となる。
つまり、異なる種類の文字を選んだ場合は、相異なる が作り出せる。
したがって主に数えたいのは、「 の中から異なる種類の2文字を選ぶ選び方は何通りあるか?」ということである。これは の長さを とすると全部で 通りあるので、単純に2重ループで数え上げるのでは間に合わない。このうまい数え方は kyopro_freinds さんのユーザ解説がとても参考になったので詳細はそちらで。
ここまでくればあとは実装するだけ。私は文字の種類をkey
、その文字が の中に含まれている個数をvalue
とするmap
を用いた。あるKey
のvalue
が1つでも1より大きければ (=同じ種類の文字が選べる場合)、異なる種類の2文字を選ぶ選び方に1を加える必要があることに注意。
コード
#include <bits/stdc++.h> using namespace std; #define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++) // ======================================== // int main() { string S; cin >> S; ll l = S.size(); map<char, ll> mp; rep(i, 0, S.size()) mp[S[i]]++; ll ans = l * l; bool flag = false; for (auto itr = mp.begin(); itr != mp.end(); itr++) { ans -= (itr->second) * (itr->second); if (itr->second > 1) flag = true; } if (flag) cout << ans / 2 + 1 << endl; else cout << ans / 2 << endl; }
実装時間: 40分