yukicoder : No.459 C-VS for yukicoder

ARCとyukicoderの間にCODEVSを見ていた。
http://yukicoder.me/problems/no/459

問題

グリッド上で展開される落ちものゲーを考える。
H*Wのフィールドに、N個のパックを落とす。

各パックは3*3のサイズを持ち、9マス分の各マスはブロックで埋まっているか空である。
ただし最低１つはブロックが含まれている。
各パックを落とす際は、左右方向の位置を決めると無限の高さから落ちる。
パック内の各ブロックは、底面か他のブロックにぶつかるまで落下する。

N個のパックを落とした左右方向の位置と、N個パックを落とした後のフィールドの状態が与えられる。
各パックの構成としてあり得るブロックの配置を答えよ。

解法

フィールドの端から順に処理していく。
最終的なフィールドにおけるフィールドのc列の高さがH[c]とする。
c列目にブロックを落とす可能性のあるパックに、いくつかずつブロックを分配して割り当てていくことを考えよう。

まだ１個もブロックが割り当てられていないパックがあれば、まずそこに割り当てる。
その後は各パック・各列３個以内の範囲でブロックを割り当てていけばよい。

int H,W,N;
string S;
int HH[10101];
int A[40100][3], C[40101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(y,H) {
		cin>>S;
		FOR(x,W) HH[x] += S[x]=='#';
	}
	vector<int> add[10101];
	FOR(i,N) {
		cin>>C[i];
		add[C[i]].push_back(i);
	}
	
	queue<int> Q[5];
	FOR(x,W) {
		for(i=2;i<=4;i++) {
			while(Q[i].size()) Q[1].push(Q[i].front()), Q[i].pop();
		}
		FORR(r,add[x]) Q[0].push(r);
		
		for(i=0;i<=3;i++) {
			while(HH[x] && Q[i].size()) {
				y=Q[i].front();
				Q[i].pop();
				if(x>=C[y]+3) continue;
				HH[x]--;
				A[y][x-C[y]]++;
				Q[i+1+(i==0)].push(y);
			}
		}
	}
	FOR(i,N) {
		string B[3]={"...","...","..."};
		FOR(y,3) {
			string B="...";
			FOR(x,3) if(A[i][x]>y) B[x]='#';
			cout<<B<<endl;
		}
	}
	
}

まとめ

最初フローを書こうとしてしまった。