東京大学プログラミングコンテスト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; }