Codeforces #194 Div1. C. Lucky Tickets

これはわからずEditorialを見て解答。
割と難しかったみたいね。
http://codeforces.com/contest/333/problem/C

問題

８ケタの数を考える。この数の各桁を連結したり、間に＋・－・×・括弧を入れて、10000以下の数Kを作りたい。
Kが与えられたとき、Kを作れる8桁の数をM通り以上答えよ。

解法

前後４ケタずつを考える。
４ケタの数字から生成できる数を全パターン列挙すると、約600000通り、すなわち0～9999の数が平均60個ずつぐらい作れる。

上４ケタを数Xを作れるパターンとし、下４桁を|K-X|を作れるパターンとしてそれらを連結すればよい。
各Xについて上記処理を行うと、やはり600000通りぐらいKを作れる。
4桁分処理を行うのも結構めんどいね。

int K,M;
set<int> S4[10000],S3[1000],S2[100],S1[10000],REV[10000];


void add(set<int> &t,set<int> &s1,set<int> &s2) {
	ITR(it1,s1) ITR(it2,s2) {
		t.insert(*it1+*it2);
		t.insert(*it1-*it2);
		t.insert(-*it1+*it2);
		t.insert(-*it1-*it2);
		t.insert(*it1**it2);
		t.insert(-*it1**it2);
	}
}

void dodo1(int c) {
	if(S1[c].empty()) {
		S1[c].insert(c);
		S1[c].insert(-c);
	}
}
void dodo2(int c) {
	if(!S2[c].empty()) return;
	
	S2[c].insert(c);
	S2[c].insert(-c);
	
	int s1,s2;
	s1=c/10,s2=c%10;
	dodo1(s1);dodo1(s2);
	add(S2[c],S1[s1],S1[s2]);
}

void dodo3(int c) {
	if(!S3[c].empty()) return;
	
	S3[c].insert(c);
	S3[c].insert(-c);
	
	int s1,s2;
	s1=c/100,s2=c%100;
	dodo1(s1);dodo2(s2);
	add(S3[c],S1[s1],S2[s2]);
	
	s1=c/10,s2=c%10;
	dodo2(s1);dodo1(s2);
	add(S3[c],S2[s1],S1[s2]);
}

void dodo4(int c) {
	int s1,s2;
	S4[c].insert(c);
	S4[c].insert(-c);
	
	s1=c/1000,s2=c%1000;
	dodo1(s1);dodo3(s2);
	add(S4[c],S1[s1],S3[s2]);
	
	s1=c/100,s2=c%100;
	dodo2(s1);dodo2(s2);
	add(S4[c],S2[s1],S2[s2]);
	
	s1=c/10,s2=c%10;
	dodo3(s1);dodo2(s1);
	add(S4[c],S3[s1],S1[s2]);
}


void solve() {
	int f,i,j,k,l, x,y;
	ll r=0;
	
	cin>>K>>M;
	FOR(i,10000) {
		dodo4(i);
		ITR(it,S4[i]) if(*it>=0) REV[*it].insert(i);
	}
	
	set<int> R;
	FOR(x,10000) {
		y = abs(x-K);
		if(y==10000) continue;
		ITR(it,REV[x]) {
			ITR(it2,REV[y]) R.insert(*it*10000+*it2);
			if(R.size()>=M) break;
		}
		if(R.size()>=M) break;
	}
	x=0;
	ITR(it,R) {
		if(x++>=M) break;
		_P("%08d\n",*it);
	}
	
}

まとめ

これは本番中に解くのは難しいな…。
他の人も全然解けてない。