Codeforces #1015 : D. Arcology On Permafrost

なんかDで妙に苦労してる。
https://codeforces.com/contest/2084/problem/D

問題

整数N,M,Kが与えられる。M*K＜Nである。
N要素の非負整数列aに対し、f(a)を以下のように定義する。

• aのうち連続するK要素を取り除き、間を詰める、という作業をM回行う。最終的なaのうちMex(a)の最小値

f(a)が最大となるaを構築せよ。

解法

• (M+1)*K＞Nの場合
  • 0,1,2,.....,(K-1),0,1,2,.....,(K-1),0,1....と0～(K-1)を繰り返せばよい。どこをどうM回K要素を取り除かれても、最後0...(K-1)の並びが1個は残り、f(a)=Kとなる。
• (M+1)*K≦Nの場合
  • a=N/(M+1)とすると、0,1,2,....,a,0,1,...,a,...と繰り返す。

int T,N,M,K;
vector<int> E[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>K;
		if((M+1)*K<=N) {
			FOR(i,M+1) E[i].clear();
			FOR(i,N) E[i%(M+1)].push_back(i/(M+1));
			FOR(i,M+1) {
				FORR(e,E[i]) cout<<e<<" ";
			}
		}
		else {
			FOR(i,N) cout<<i%K<<" ";
		}
		cout<<endl;
	}
	
}

まとめ

最終的なコードは短いけど、結構手間取った。