ARC080 D : Grid Coloring(400)

作成日:2017.08.07
最終更新日:2017.08.07

問題概要

問題本文

 縦$H$行、横$W$行のマス目を$N$色で塗り分ける。 $i$色目で塗られたマスが$a_i$個あり、それらが上下左右に隣り合っているような塗り方を求めよ。
制約
$1 \leq H,W \leq 100$
$1 \leq N \leq HW$
$a_i \geq 1$
$\sum_{1 \leq i \leq N}{a_i} = HW$

考え方

 $H=1$の時は$i$色目で$a_i$個連続でマスを塗るということを繰り返せば良い。
 そうでない時、まず$H=1$の時と同様に一列に並んだマスに色を塗ってから$H$行にすることを考える。 これはひもを平面に敷き詰めることと同じであるから、渦巻き状やジグザグに並べれば良い。 実装の容易さを考えてジグザグに並べることにする。

ソースコード

マクロ等はこちら

int H,W,N;
int ans[111][111];
int p;

int main(){
	scanf("%d%d%d" , &H , &W , &N);
	repp(i,1,N+1){
		int a;
		scanf("%d" , &a);
		while(a > 0){
			ans[p/W][(p/W)%2==1?W-1-(p%W):(p%W)] = i;
			++p;
			--a;
		}
	}
	repp(i,0,H){
		repp(j,0,W){
			printf("%d%c" , ans[i][j] , j+1==W ? '\n' : ' ');
		}
	}
	return 0;
}

解法まとめ

 各色$a_i$個連続にすでに塗り終わったマスに続いてジグザグに塗っていく。(7-15行)

ARC080の他の問題 C E F

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら