Codeforces #747 Div2 : F. Ideal Farm

2023年になったが、まだ2021/10の問題やってる…。
https://codeforces.com/contest/1594/problem/F

問題

正整数N,K,Sが与えられる。
N個の1列に並んだ箱に、S個の区別がつくボールを分けて入れたとする。
空の箱がないようなあらゆる入れ方において、箱の区間のうちボールの総数がKとなるものが必ず存在するか判定せよ。

解法

A[i] := i番目の箱に入れたボールの数
とし、P[i]をそのprefix sumとする。
P[i]-P[j]=Kとなるi,jが常に存在するなら条件を満たす。
Pを、初項が0、末尾がSとなる昇順列としたとき、鳩ノ巣原理の要領でそこからN個の入れ方を考えると、floor( (S+1)/(2K) )*K + min(S+1%(2K),K)がN以下の場合、条件を満たす。

int T;
ll S,N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S>>N>>K;
		
		if(S==K) {
			cout<<"YES"<<endl;
		}
		else {
			ll a=(S+1)/(2*K)*K;
			ll b=min((S+1)%(2*K),K);
			if(a+b>N) cout<<"NO"<<endl;
			else cout<<"YES"<<endl;
		}
	}
}

まとめ

コードは短い。