1と四則演算だけで2011を作れ

virottoさんのとある情報工学科の大学生活 CTF：2011年問題の考察に触発されて…

問題概要

(省略)

解法

問題文より1の個数は最大16個．
四則演算では*と/が優先されるので，*と/のみで作れるものをリストアップする．
最後にそれと+と-を使って作れるものをリストアップする．

その他

最初はvirottoさんと同じような解法で解こうと思ったけどC++でパーサーを実装するのが面倒だったのでこの解法に．
IdeOneで実験した結果0.19sなので割と高速．
JavaScriptでevalという発想は無かった!

本番では解けなかった(ように見えた)けど，5日目に問い合わせてみたら，ジャッジのミスということが分かり実際は解けていたので一安心．

実装(C++)

本番の実装とは違います．

#include <iostream>
#include <tr1/unordered_map>
using namespace std;
using namespace tr1;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
int value[9]={1,11,111,1111,11111,111111,1111111,11111111,111111111};
string value_str[9]={"1","11","111","1111","11111","111111","1111111","11111111","111111111"};
const int CORRECT=2011;

unordered_map<int,string> v1[17];//*と/のみで生成可能な数値
unordered_map<int,string> v2[17];//+と-も用いて生成可能な数値

#define SOLVE1(p,k,q){\
	string next_str=p->second+ #k +value_str[q];\
	long long next=(long long)p->first k value[q];\
	if(next<=1e9&&(v1[i+j+1][next]==""||v1[i+j+1][next]>next_str))v1[i+j+1][next]=next_str;\
}
#define SOLVE2(p,k,q){\
	string next_str=p->second+ #k +q->second;\
	int next=p->first k q->first;\
	if(v2[i+j][next]==""||v2[i+j][next]>next_str)v2[i+j][next]=next_str;\
}
int main() {
	REP(i,9)if(i)v1[i+1][value[i]]=value_str[i];
	REP(i,16)REP(j,9){
		if(i+j+1>=17)continue;
		if(j)FOR(k,v1[i]){
			SOLVE1(k,*,j);
			SOLVE1(k,/,j);
		}
	}
	v1[1][value[0]]=value_str[0];
	v2[0][0]="";
	REP(i,16)REP(j,17)FOR(k,v1[j]){
		if(i+j>=17)continue;
		FOR(l,v2[i]){
			SOLVE2(l,+,k);
			SOLVE2(l,-,k);
		}
	}
	REP(i,17){
		if(v2[i][CORRECT]!=""){
			cout<<i<<":"<<v2[i][CORRECT].substr(1)<<endl;
			break;
		}
	}
	return 0;
}