kmjp's blog

競技プログラミング参加記です

Codeforces #601 Div1 A. Feeding Chicken

レートが1しか変動しなかった回。
http://codeforces.com/contest/1254/problem/A

問題

グリッドが与えられる。一部のマスには米がある。
このグリッドを、K個の領域に分割せよ。
ただし、各領域は連結しており、かつ1個以上米のあるマスを含まなければならない。

解法

一瞬↓これに近く見えるけど、分割方法が矩形に限定されない分異なる。
C - Strawberry Cakes

隣接マスをたどり全マスを1回ずつ通るルートを考えよう。
例えば左上から左右にジグザグ移動しながら下に降りてくるとか。
あとはそのルートにそって、米に遭遇した時点でパスを分割するようにすればよい。

int T;
int H,W,K;
string S[101];
string A="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
string ret[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>K;
		int C[62]={};
		int NR=0;
		i=0;
		FOR(y,H) {
			cin>>S[y];
			FOR(x,W) if(S[y][x]=='R') NR++;
		}
		FOR(i,NR) C[i%K]++;
		i=0;
		FOR(y,H) {
			FOR(j,W) {
				if(y%2==0) x=j;
				else x=W-1-j;
				if(i>=K) i=K-1;
				if(S[y][x]=='R') {
					S[y][x]=A[i];
					C[i]--;
					if(C[i]==0) i++;
				}
				else {
					S[y][x]=A[i];
				}
			}
			cout<<S[y]<<endl;
		}
	}
}

まとめ

まぁこれはあまり迷わないね。