【C++】ABC264 D問題 "redocta".swap(i, i+1)

ABC264のD問題 “redocta”.swap(i, i+1)を解説します。

問題のポイント
転倒数という考え方。
転倒数とは、順番通りになっていない組の数のことです。

今回の問題では、a, t, c, o, d, e, rの7文字の順序を扱います。
aを0番目、tを1番目、cを2番目、cを3番目、….、rを6番目とみなします。
atcoderという文字列は、0, 1, 2, 3, 4, 5, 6となっています。

例えば、a, t, c, o, d, e, rで構成された適当な文字列catredoを考えます。
catredoという文字列は、2, 0, 1, 6, 5, 4, 3となっています。

今回はatcoderという文字列に昇順に番号を与えたので、昇順になっていない文字列の組を数えます。
全て列挙してみます。

上記の8個になります。この問題では転倒数を聞かれているわけです。
転倒数は2重ループを利用してカウントしています。

入力例

catredo

回答例

#include
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
    string s;
    cin >> s;   // 入力受け取り

    string t = "atcoder";
    int n = t.size();

    map< char, int > mp;  // aが0番目、tが1番目、cが2番目、...という情報を持つmapを作りたい
    rep(i, n) {
        mp[t[i]] = i;
    }

    vector< int > vec(n); // catredoという入力であった場合、{2, 0, 1, 6, 5, 4, 3}となるようなvector
    rep(i, n) {
        vec[i] = mp[s[i]];
    }

    int cnt = 0;    // 答えを準備
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (vec[i] > vec[j]) {  // i番目より後ろの文字列に小さい数字がある度に1プラス
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

【C++】ABC264 D問題 “redocta”.swap(i, i+1)

コメント