Codeforces #221 Div1. A. Divisible by Seven

CF221に参加。A,Bをそこそこの時間で解いたが、今回はC,Dの難易度が高くそこで打ち止め。
Hackも1ミス1成功で若干稼いだ。
A,Bを解ききったおかげでそこそこの順位についてレートも上昇。
http://codeforces.com/contest/375/problem/A

問題

最大100万桁の数字が与えられる。
この数字は、途中に1,6,8,9が1回以上含まれている。
この数字の桁を並べ替え、7で割り切れる数字を作れ。

解法

まず、元の数字から1,6,8,9を1つずつ抜き出す。
1,6,8,9で作れる24通りの4桁の数字は、7で割った余りを求めると0～6を網羅できる。
そのため、1,6,8,9を並べ替えたものと、元の数字から4桁抜き出したものを連結して7で割った余りが0になるものを探せばよい。
この問題ではleading zeroは許可されていないが、先頭に1,6,8,9を置くことでleading zeroも回避できる。

string S;

int mod7(string S) {
	int i,j=0;
	FOR(i,S.size()) {
		j=j*10+(S[i]-'0');
		if(j>10000) j%=7;
	}
	return j%7;
}

void solve() {
	int f,i,j,k,l,x,y,a[256];
	cin>>S;
	int L=S.size();
	x=0;
	ZERO(a);
	x=L-1;
	a['1']=a['6']=a['8']=a['9']=1;
	for(i=L-1;i>=0;i--) {
		if(a[S[i]]) a[S[i]]=0;
		else swap(S[x--],S[i]);
	}
	S=S.substr(4);
	string T="1689";
	do {
		if(mod7(T+S)==0) {
			cout << T+S << endl;
			return;
		}
	} while(next_permutation(T.begin(), T.end()));
}

まとめ

最初、1,6,8,9のみ並べ替え可能かと思ってちょっと考え込んだ。
いや、それでも24通り試せばよいのだろうけど。