お誕生日コンテスト : C - ロ　シ　ア

なぜロシアなんだろう…。
謎な理由でWAを重ねた問題。
http://birthday0410.contest.atcoder.jp/tasks/birthday0410_c

問題

0～(N-1)番の人が長方形のベッドに寝たい。

各人のサイズはKであり、各人は寝るためにK個の連結したマスを必要とする。
ただし、体の各パーツを1～K番とすると、隣接する以外のパーツと隣接マスに配置されてはならない。

また、各人は前後の番号の人と隣接していなければならず、他の人と隣接してはならない。
そのような寝方を答えよ。

解法

場合分けの面倒な問題。

N==2の時

以下のように縦に２人並べるだけ。

AAAAAAAAAAA
BBBBBBBBBBB

K==1の時

Nが8以上の偶数なら、以下のように３行からなる輪を作ればよい。
また、N==4だけは２行の和を作れる。
N==6または奇数の時は答えは無し。

ABCDE
L...F
KJIHG

AB
DC

N==3の時

K==1の時は答えは無し。K>=2なら以下のようにすればよい。

AAAAAAAABBBBBBBB
....CCCCCCCC....

K==2の時

K==1のように輪っかを作ればよい。ここに来る時点でN>=4なので、常時輪が作れる。

AABBCC
G....D
GFFEED

残りの場合(N>=4、K>=3)

こんな感じで、上１列に横向きに寝かせて、残りは縦に寝かせればよい。
最初の左上の角や右上の角で折り曲げて縦を占めるマスを総当たりで検索する。
なお、全パターン列挙したがこの条件の場合は常に答えは存在する。

AAAAAAABBBB     AAAABBBB   AABBBCC  AAABBBCCC
L.........B     J......C   A.....C  L.......D
LKJIHGFEDCB     JIHGFEDC   JIHGFED  LKJIHGFED
LKJIHGFEDCB     JIHGFEDC   JIHGFED  LKJIHGFED
LKJIHGFEDC.     JIHGFEDC   JIHGFED  .KJIHGFE.
LKJIHGFEDC.     .IHGFED.
LKJIHGFEDC.
LKJIHGFEDC.
.KJIHGFEDC.

int N,K;
string S[100];
string L;
char SS[1000][1000];

void solve() {
	int f,i,j,k,l,x,y;
	
	FOR(i,26) L+='A'+i;
	FOR(i,26) L+='a'+i;
	
	cin>>N>>K;
	
	if(N==2) {
		FOR(i,K) S[0]+='A',S[1]+='B';
		return _P("%d %d\n%s\n%s\n",K,2,S[0].c_str(),S[1].c_str());
	}
	if(K==1) {
		if(N==4) return _P("2 2\nAB\nDC\n");
		if(N<8 || N%2) return _P("-1\n");
		x=(N-2)/2;
		
		FOR(i,x) SS[0][i]=SS[1][i]=SS[2][i]='.';
		y=0;
		FOR(i,x) SS[0][i]=L[y++];
		SS[1][x-1]=L[y++];
		FOR(i,x) SS[2][x-1-i]=L[y++];
		SS[1][0]=L[y++];
		_P("%d %d\n%s\n%s\n%s\n",x,3,SS[0],SS[1],SS[2]);
		return;
	}
	if(N==3) {
		FOR(i,K) S[0]+='A';
		FOR(i,K) S[0]+='B';
		FOR(i,2*K) S[1]+='.';
		FOR(i,K) S[1][i+K/2]='C';
		return _P("%d 2\n%s\n%s\n",S[0].size(),S[0].c_str(),S[1].c_str());
	}
	if(K==2) {
		ZERO(SS);
		int w=N-1;
		FOR(x,w) SS[1][x]='.';
		i=0;
		FOR(x,w) SS[0][x]=L[(i++)/2];
		SS[1][w-1]=L[(i++)/2];
		FOR(x,w) SS[2][w-1-x]=L[(i++)/2];
		SS[1][0]=L[(i++)/2];
		return _P("%d 3\n%s\n%s\n%s\n",w,SS[0],SS[1],SS[2]);
	}
	
	for(int w=3;w<=max(N,K);w++) {
		for(int h=1;h<=K-1;h++) {
			int num=(w+(h-1)+(K-1))/K;
			int rem=1+(num*K-(w+h-1))%K;
			
			int lnum=w;
			if(h>2) lnum--;
			if(rem>2) lnum--;
			if(lnum!=N-num) continue;
			ZERO(SS);
			FOR(y,K+2) FOR(x,w) SS[y][x]='.';
			FOR(i,num*K) {
				int tx,ty;
				if(i<h) tx=0,ty=h-1-i;
				else if(i<h+w-1) tx=i-(h-1),ty=0;
				else tx=w-1,ty=i-(h+w)+2;
				SS[ty][tx]=L[i/K];
			}
			for(i=num;i<N;i++) {
				int xdif=w-2;
				int ydif=2;
				if(rem<=2) xdif++;
				if(i==num && rem<=1) ydif--;
				if(i==N-1 && h<=1) ydif--;
				FOR(y,K) SS[y+ydif][xdif-(i-num)]=L[i];
			}
			FOR(i,N) {
				num=0;
				FOR(y,K+2) FOR(x,w) if(SS[y][x]=='A'+i) num++;
			}
			
			_P("%d %d\n",w,K+2);
			FOR(y,K+2) _P("%s\n",SS[y]);
			return;
		}
	}
	return _P("-1\n");
}

まとめ

えらい苦労したけど何とか解けてよかった。

kmjp's blog

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