Codeforces #749 : F. Defender of Childhood Dreams

こちらは実装は短め。
https://codeforces.com/contest/1586/problem/F

問題

正整数N,Kが与えられる。
N頂点のグラフを考える。
a＜bである頂点a→bに対し、有向辺が張られているものとする。

各辺に色を割り当てる。
その際、どの長さK以上のパスも、2色以上の辺を通るようにしたい。
最小何色で条件を満たせるか、また塗り方の一例を示せ。

解法

各頂点のラベル番号をK進数で表記する。
頂点aとbの間の辺は、値が異なる最大の桁位置に対応する色で彩色しよう。

同じ色の辺だけたどるのは最大でも(K-1)回なので、長さK以上のパスでは2色以上の辺を通らざるを得ない。

int N,K;
int A[1010][1010];
int B[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		x=i;
		FOR(j,100) {
			B[i][j]=x%K;
			x/=K;
		}
	}
	
	int ma=0;
	FOR(x,N) FOR(y,N) if(x!=y) {
		k=0;
		FOR(j,100) if(B[x][j]!=B[y][j]) k=j;
		A[x][y]=k+1;
		ma=max(ma,k+1);
	}
	
	cout<<ma<<endl;
	FOR(x,N) FOR(y,N) if(x<y) cout<<A[x][y]<<" ";
	
	
}

まとめ

わかってしまえばシンプルだな…。