yukicoder No.4 おもりと天秤

問題はこちら
No.4 おもりと天秤 - yukicoder

DP
「k番目までのおもりを使って重さiを作れるか」をkが小さい方から調べ
全てのおもりの重さの合計の半分が作れるか否かをチェックすれば良い
100以下の重さのおもりが100個以下なので、配列は0～10000まで用意すればOK

int main(){
	int w[10101]={1},i,j,t,s,n;
	scanf("%d",&n);
	s=0;
	for(i=0;i<n;i++){
		scanf("%d",&t);
		s+=t;
		for(j=10000;j--;w[j+t]+=w[j]);
		//jが小さい方からやってしまうと、同じおもりを2回以上使ってしまう
		//（例えば最初にt=2を読み込んだとき、w[4]=1になってしまう）
	}
	puts(s%2==1||!w[s/2]?"impossible":"possible");
	return 0;
}

まず自明な削減

w['~~']={1},j,s;
main(t){
	for(gets(&j);~scanf("%d",&t);){
		s+=t;
		for(j=1e4;j--;w[j+t]+=w[j]);
	}
	j=!puts("impossible"+(s%2<1&&w[s/2])*2);
}

w[0]に1を与えるのをやめ、ここにおもりの合計を保存することにする
jの値をうまく利用すると、Nの読み飛ばしも込めて次のように書き換えることができる

w['~~'],j;
main(t){
	for(;~scanf("%d",&t);){
		*w-=t*j;
		//jは初めて来た時0、2回目以降は-1になっている
		for(j=1e4;j--;w[j+t]+=w[j]);
	}
	j=!puts("impossible"+(*w%2<1&&w[*w/2])*2);
}

整形して終わり

w['~~'],j;
main(t){
	for(;~scanf("%d",&t);)for(*w-=t*j,j=1e4;j--;w[j+t]+=w[j]);
	j=!puts("impossible"+(~*w%2&&w[*w/2])*2);
}