SRM 254 DIV1 Hard SelfCatalogue

問題 Editorial

問題

「この文の中にxつのy(数字)が出てくる、またzつのw(数字)が出てくる」というような文であって、
文の中に現れるすべての数字に対して言及していて、
真であるような文を"self-catalogue"と言う。
数字はx,zの部分とy,wの部分が数えられる。x,zの部分は2桁の数ならそれぞれ数えられる。
"self-catalogue"は長さ10の数値列で表せる。インデックスiの数値は数字iが出現する回数である。ただし0の場合はその数字に言及していないことを表す。
サイズ10の数値列countsが与えられる。そのいくつかの(0つ以上の)要素は-1である。

• 1である場所にはどんな数値でも入れられ、その他の場所はcounts[i]である、辞書順最小の"self-catalogue"を表す数値列を求めよ
• -1 <= counts[i] <= 100

解答

Editorialを参考にした。
基本的は全探索。ただし各場所に入れる数値の上界で枝刈りできる。
まず明らかに22より大きい数値は入らない。
何故ならば、それぞれの場所が全部その数字を含んでいても、2桁までなので2*10。それと自分自身の数字を足しても22までにしかならないからである(22が入ることがあるとは限らない)
各場所に数値を入れていくたびに、そこに入れた数値の分だけ上界は減っていく。
なぜならば、そこに入れる分に数字が"取られる"からである。
最後には単純に判定すればいい。
他にも様々な枝刈りができるが、これで間に合う

コメント

枝刈り苦手。これは簡単なので解きたかった。
まず枝刈りしようという姿勢が無い感じ。どうやるか？というのを考えてない。それっぽかったら、考えろ

コード

#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
typedef vector<int> vi;  
struct SelfCatalogue {
	vi v;
	bool dfs(int i, int x) {
		if(x < 0) return false;
		if(i == 10) {
			static int a[10];
			rep(j, 10) a[j] = 0;
			rep(j, 10) if(v[j] != 0) {
				a[j] ++;
				a[v[j]%10] ++;
				if(v[j] >= 10) a[v[j]/10] ++;
			}
			rep(j, 10) if(v[j] != a[j]) return false;
			return true;
		}
		if(v[i] == -1) {
			rer(j, 0, x) {
				v[i] = j;
				if(dfs(i+1, x - j)) return true;
			}
			v[i] = -1;
			return false;
		}else {
			return dfs(i+1, x - v[i]);
		}
	}
	vector <int> construct(vector <int> counts) {
		v = counts;
		if(dfs(0, 22)) return v;
		else return vi();
	}
};