Codeforces #261 Div2 C. Pashmak and Buses

CF#261に参加。
今回は割と簡単だったようで完答者多数。
自分もちょっとWA出したけど最終的には全部解けた。
http://codeforces.com/contest/459/problem/C

問題

N人の生徒がK台のバスいずれかを使って登校する、ということをD日繰り返す。
２人の生徒がD日間同じバスを利用する、ということがないよう、各人が乗るバスを割り振れ。

解法

K台でD日なので最大でK^D人までの生徒なら条件を満たすように割り振れる。
後は１日ごとに生徒をK個のグループに分け、各グループに1～K番のバスを割り当てる、ということを再帰的に繰り返せばよい。

ll N,K,D;
int mat[1001][1001];

void dfs(int d,int l,int r) {
	if(d>=D) return;
	int i;
	if(r-l<=K) {
		FOR(i,r-l) mat[d][i+l]=i;
	}
	else {
		int st=(r-l+(K-1))/K;
		for(i=0;i*st+l<r;i++) {
			int j;
			FOR(j,st) if(l+i*st+j<r) mat[d][l+i*st+j]=i;
			dfs(d+1,l+i*st,min(l+(i+1)*st,r));
		}
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>K>>D;
	
	ll t=1;
	FOR(i,D) {
		t*=K;
		if(t>=N) break;
	}
	if(i==D) return _P("-1\n");
	dfs(0,0,N);
	
	FOR(i,D) {
		FOR(j,N) _P("%d ",mat[i][j]+1);
		_P("\n");
	}
}

まとめ

Kが大きいので、K^Dの計算でオーバーフローしてる人いないかなと思ったけど、pretestで大きな値が入ってるケースがあったようでHack出来ず。