Google Code Jam 2018 Round2 : A. Falling Balls

これまでで一番簡単なRound2だった気がする。
https://codejam.withgoogle.com/2018/challenges/0000000000007706/dashboard

問題

幅Cのグリッドがある。
ここグリッドの最上段から、各列１つずつボールを落とす。
ここで、一部のセルに斜めの板を配置することを考える。
そこに到達したボールは、板の向きに合わせて左右１マス隣に動く。
ボール同士は互いに干渉しないものとする。
なお、左右の端の列と最下段には板を配置できない。

最下段において各列に到達したボール数が与えられる。
そのような状況に至るような板の配置例を求めよ。

解法

左右にあるボールが板の存在により入れ替わることはない。
よって、どのボールがどこに至るかは一意に定まる。

x列目のボールが最後y列目に行くようにしたい場合、

• x＜yなら(0-indexで)i段目の(x+i)列目に右向きの板を置く
• x＞yなら(0-indexで)i段目の(x-i)列目に左向きの板を置く

ようにすればよい。

int T,testcase;
int N;
int C[1010];
int tar[1010];
string S[102];

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int sum=0;
	FOR(i,N) {
		cin>>C[i];
		sum+=C[i];
	}
	if(C[0]==0 || C[N-1]==0 || sum!=N) {
		_P("Case #%d: IMPOSSIBLE\n",TC);
		return;
	}
	x=0;
	FOR(i,N) {
		FOR(y,C[i]) tar[x++]=i;
	}
	
	int ma=0;
	FOR(i,101) S[i]=string(N,'.');
	FOR(i,N) {
		if(tar[i]<i) {
			FOR(x,i-tar[i]) S[x][i-x]='/';
		}
		if(tar[i]>i) {
			FOR(x,tar[i]-i) S[x][i+x]='\\';
		}
		ma=max(ma,abs(tar[i]-i)+1);
	}
	
	_P("Case #%d: %d\n",TC, ma);
	FOR(i,ma) _P("%s\n",S[i].c_str());
	
	
}

まとめ

Round1と間違えたかと思った。