yukicoder No.10 ＋か×か

メモ化再帰
「i番目までで数sが作れた」という情報を保存することで2^(N-1)とおり全てを試す必要はなくなる

x[60][100100],a[60],m,n;
char p[60];
void f(int i,int s){
	//今i番目まで使ってsを作った、という状態
	if(i==n&&s==m)puts(p+1),exit(0);
	//すべての数を使い尽くして、かつ、目標値になったなら出力して終わり
	if(s>m||i==n||x[i][s]++)return;
	//目標値を超えたり、数を使い尽くしても目標値にならなかったり、ここに来たことがあればこの先を調べる必要はない
	p[i]='+',f(i+1,s+a[i]);
	p[i]='*',f(i+1,s*a[i]);
}

int main(){
	int i;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)scanf("%d",a+i);
	f(1,a[0]);
}

全部配列にまとめて読み込む。1つ目の情報はいらないので消えてもらう
あとは三項演算子でまとめつつ、「引数は後ろから評価される」「計算式は前から評価される」という処理系依存テクニックでまとめる
（p[i]への書き込みが2度あるので正確には未定義動作？）

x[60][1<<20],a[60];
char p[60];
f(i,s){
	a[i]?s>*a|x[i][s]++||f(i+1,s+a[i],p[i]=43)+f(i+1,s*a[i],p[i]--):s-*a?:exit(!puts(p+2));
}
main(i){
	for(;~scanf("%d",a-i--););
	f(2,a[1]);
}

2次元配列を1次元化し、その配列に全部読み込むことにする
さらによく考えたらf(2,a[1])ではなく、f(1,0)でよい（足し算が行われf(2,a[1])が呼ばれる）

x[1<<26];
char p[60];
f(i,s){
	x[i]?s>*x|x[i<<20|s]++||f(i+1,s+x[i],p[i]=43)+f(i+1,s*x[i],p[i]--):s-*x?:exit(!puts(p+2));
}
main(i){
	for(;~scanf("%d",x-i--););
	f(1,0);
}

160B

16/10/11追記
exitを使わずとも、*xを適当な値で潰してしまえば、それ以降出力されることはなくなるので、putsの返り値を使うことにして次のようにできる

x[1<<26];
char p[60];
f(i,s){
	x[i]?s>*x|x[i<<20|s]++||f(i+1,s+x[i],p[i]=43)+f(i+1,s*x[i],p[i]--):s==*x?*x=~puts(p+2):0;
}
main(i){
	for(;~scanf("%d",x-i--););
	f(1,0);
}

159B
~putsじゃなくてputsでもごまかせないかと思ったけど05.txtで落とされる