東京大学プログラミングコンテスト2014 F - チェックディジット

問題:F: チェックディジット - 東京大学プログラミングコンテスト2014 | AtCoder

解法:条件を満たすような関数を考えるために,f(s)=(文字列sについて,s[j] < s[i](j < i)となる(i,j)の組み合わせの数を2で割ったあまり)を考える。これは,同一の文字列に対して同じ出力を得る。また,隣接する2数が異なる時,それを入れ替えて得た整数を入力とすると,元と異なる出力になる(f(s)の値が1だけずれるので)。よって,上記のf(s)という関数を考えれば満点が得られる。
以下ソースコード

set<string> S, SS;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        string s;
        cin >> s;
        int n = s.size();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (s[i] < s[j]) cnt++;
            }
        }
        cout << cnt%2 << endl;
    }
    return 0;
}