読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.334 門松ゲーム

問題はこちら
No.334 門松ゲーム - yukicoder

DFSするだけ
メモ化して高速化しないとだめかと思ったけど、しなくても大丈夫らしい

int a[20],I,J,K,n;
int f(int x){
	//すでに使った竹の情報をbitで保存したものを引数とする
	int i,j,k;
	for(i=0;i<n;i++)for(j=i;++j<n;)for(k=j;++k<n;){
		//3本の竹を選ぶ
		if(~x&1<<i && ~x&1<<j && ~x&1<<k && (a[i]-a[j])*(a[k]-a[j])>0 && !f(x^1<<i^1<<j^1<<k)){
			//どの竹も未使用で、それらが門松列をなし、その後必勝なら
			I=i;J=j;K=k;
			return 1;
			//何を選んだか保存してreturn
		}
	}
	return 0;
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	f(0)?printf("%d %d %d",I,J,K):puts("-1");
}

よく考えると、3重ループの継続条件はa[i]!=0なので、nの情報は不要。ただしaにそのまま読み込むとindexがずれてめんどくさいことになるので、ちゃんと捨てる。
あとは自明な短縮をして

a[20],I,J,K,n;
f(x,i,j,k){
	for(i=0;a[i];i++)for(j=i;a[++j];)for(k=j;a[++k];)
		if(~x>>i&~x>>j&~x>>k&(a[i]-a[j])*(a[k]-a[j])>0&&!f(x^1<<i^1<<j^1<<k))
			return I=i,J=j,K=k;
			//kは必ず2以上
	K=0;
	//return 0;のかわり
}
main(i){
	for(;scanf("%d",a-i--););
	f(0)?printf("%d %d %d",I,J,K):puts("-1");
}

ここで、f(0)の返り値は、勝てないなら0になり、勝てるならi,j,kのどれか(に細工をしたもの)の非0な値にできる。
なのでこれを利用して出力部分を短縮

a[20],I,J,K;
f(x,i,j,k){
	for(i=0;a[i];i++)for(j=i;a[++j];)for(k=j;a[++k];)
		if(~x>>i&~x>>j&~x>>k&(a[i]-a[j])*(a[k]-a[j])>0&&!f(x^1<<i^1<<j^1<<k))
			return J=j,K=k,~i;
	J=K=0;
}
main(i){
	for(;~scanf("%d",a-i--););
	I=~f(0);
	I=!printf("%d %.d %.d",I,J,K);
	//%.dとすることで、値が0の時にはなにも出力しないようできる
	//printf("%d %.d %.d",~f(0),J,K);とすると、引数評価の順序の都合で、J,Kはf(0)実行前の値になってしまう

}

f(0)は読み込みの途中で実行してしまっても、影響はないので

for(;~scanf("%d",a-i--););I=~f(0);
for(;~scanf("%d",a-i--);)I=~f(0);

と書き換えて

a[20],I,J,K;
f(x,i,j,k){
	for(i=0;a[i];i++)for(j=i;a[++j];)for(k=j;a[++k];)if(~x>>i&~x>>j&~x>>k&(a[i]-a[j])*(a[k]-a[j])>0&&!f(x^1<<i^1<<j^1<<k))return J=j,K=k,~i;
	J=K=0;
}
main(i){
	for(;~scanf("%d",a-i--);)I=~f(0);
	I=!printf("%d %.d %.d",I,J,K);
}

238B

16/09/09追記
いや普通に考えて、fの返り値をKっぽいものにしたら出力部分で短縮できるでしょ…
ついでに、xで保存するものを逆にしたら2B縮められる

a[20],I,J;
f(x,i,j,k){for(i=0;a[i];i++)for(j=i;a[++j];)for(k=j;a[++k];)if(x>>i&x>>j&x>>k&(a[i]-a[j])*(a[k]-a[j])>0&&!f(x^1<<i^1<<j^1<<k))return I=~i,J=j,k;
	I=J=0;
}
main(i){
	for(;~scanf("%d",a-i--););
	I=!printf("%d %.d %.d",~I,J,f(-1));
}

Iのところは-1を入れるよりも~をつけたほうが1B短い
231B