UTPC 2014 : F - チェックディジット

今回のUTPCの中で一番すんなり解けた。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_f

問題

10桁の数値が与えられるので、3種以下のチェックディジットを返せ。

このチェックディジットでは、元の10桁の数値のうち隣接する異なる2桁の数値が1箇所入れ替わったとき、結果が異なるようにせよ。

解法

各桁の並びの転倒数の偶奇を返せば、2種類のチェックディジットで済む。
1箇所隣接する数値を入れ替えると転倒数は1入れ替わるので、ちょうどチェックディジットは反転する。

int T;
int CD(string S) {
	int sum=0;
	int x,y;
	FOR(y,S.size()) FOR(x,y) if(S[x]<S[y]) sum++;
	return sum%2;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>s;
		cout<<CD(s)<<endl;
	}
	
}

まとめ

問題文を読むと3種以下だと満点扱いされると書いてあるため、最初3種にするよう迷ってしまった。
幸いすぐに「これ偶奇だけでいいじゃない」と気づけた。