問題はこちら
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