yukicoder No.115 遠足のおやつ

問題はこちら
No.115 遠足のおやつ - yukicoder

出力が-1になるケースは2パターン存在する
・高い方からK個買ってもD円に満たない場合
・安い方からK個買ってもD円を超える場合
(K>Nであるようなものは必ずどちらかに抵触する)
逆にこれらに触れなければ条件をみたすような買い方が必ず存在する
なのでそのようなパターンで辞書順最小のものは、金額が小さい方から順にそれを買ってよいかどうか（残りの金額と品物で、上の条件に抵触しないようにできるか）を調べて貪欲に買っていけば良い

まず1円のお菓子を買ったとする
すると「残りのD-1円で、2円～N円からちょうどK-1個買えるかどうか」を調べることになる
上に挙げた条件の前者に抵触することはありえないので後者だけ確認すれば良い
全ての商品の値段を-1して考えると
「残りの( (D-1)-(K-1) )円で、1円～(N-1)円からちょうどK-1個買えるかどうか」
と読み替えられるので、これは先ほどと全く同じ条件に帰着された。

この時購入可能ならば1を出力し
再び(D,K,N)の代わりに(D-K,K-1,N-1)で「1円のお菓子が」買えるかどうかを調べていくことになる
買えなかった場合も(D-K,K,N-1)の問題になる

以上を踏まえて実装

int main(){
	int N,K,D,i;
	scanf("%d%d%d",&N,&D,&K);
	if((K+1)*K/2>D||D+(K-1)*K/2>N*K){
		puts("-1");
		return 0;
	}
	for(i=1;K;i++){
		//i番目のお菓子を買うかどうか考える
		D-=K;
		//買うにしろ買わないにしろDはKだけ減らすことになる
		if(D+K*(K-1)/2<=N--*(K+1)){
			//買えるなら
			printf("%d ",i);
			//買う
			K--;
		}
	}
	return 0;
}

あとはこれを潰すだけ

if(D+K*(K-1)/2<=N--*(K+1)){
	printf("%d ",i);
	K--;
}

を

K-=D+K*(K-1)/2<=N--*(K+1)&&printf("%d ",i);

とした以外は至って普通に

N,K,D;main(i){scanf("%d%d%d",&N,&D,&K);for(-~K*K/2>D|D+~-K*K/2>N*K?exit(!puts("-1")):0;K;K-=N--*~-K>=D+K*~-K/2&&printf("%d ",i),i++)D-=K;}

REにはならないらしい
138B

17/01/23追記
-1のときのexitを使う必要なくね？

N,K,D;main(i){scanf("%d%d%d",&N,&D,&K);for(-~K*K/2>D|D+~-K*K/2>N*K?K=!puts("-1"):0;K;K-=N--*~-K>=D+K*~-K/2&&printf("%d ",i),i++)D-=K;}

134B