問題はこちら
No.688 E869120 and Constructing Array 2 - yukicoder
明らかに並び順には依存せず、0と1の個数のみで決まることがわかる。
1がi個、0がj個あるとき、和が2になる部分集合はi*(i-1)/2*pow(2,j)個あるので、i,jを全探索する
main(){
int k;
scanf("%d",&k);
for(int i=1;i<=30;i++)for(int j=0;i+j<=30;j++){
if(i*(i-1)/2<<j==k){
printf("%d\n",i+j);
for(int t=0;t<i+j;t++)printf("%d ",t<i);
exit(0);
}
}
}
これを縮める。
//printfをまとめる（スペシャルジャッジなので改行と空白を区別しなくて良い） for(scanf("%d",&k);j>29?j=0,++i<31:1;j++)if(i*~-i/2<<j==k){for(;t<=i+j;t++)printf("%d ",t?t>j:i+j);exit(0);} //ifを消す for(scanf("%d",&k);j>29?j=0,++i<31:1;t?exit(0):j++)for(;i*~-i/2<<j==k&&t<=i+j;t++)printf("%d ",t?t>j:i+j); //for文をまとめる for(scanf("%d",&k);i*~-i/2<<j==k&&t<=i+j?printf("%d ",t?t>j:i+j)+t++:(t?exit(0):j++,j>29?j=0,++i<31:1);); //真偽入れ替え for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0):j++,j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;); //次のように書き換えると、exit(0)がvoidなのでCE for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0):++j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;); //これなら通るが長さは同じ for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0),1:++j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;);
ということで完成品は以下
t,j,k;main(i){for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0),1:++j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;);}
116B
2018/07/12追記
自明に縮むし頭悪すぎか？？
t,j,k;main(i){for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?++j>29?j=0,!t&++i<31:1:printf("%d ",t?t>j:i+j)+t++;);}
107B
