ARC093 D : Grid Components(500)
作成日：2018.08.18
最終更新日：2018.08.18
問題概要
白(.)か黒(#)に塗った縦横それぞれ$100$マス以下のグリッドで、白黒それぞれ$A,B$個の連結成分をもつようなものを1つ構成せよ。
但し連結成分とは、上下左右に隣接する同じ色で塗られたグリッドの集合を指す。
制約
$1 \leq A,B \leq 500$
考え方
グリッドは縦横$100$マスあり、$B = 1$であるとする。
1つの連結成分に含まれるグリッドは$1$マスだけで良いから、互いに上下左右に隣接しない$A$個のグリッドを選んで白く塗り他の部分を黒く塗ると、白についての条件は達成できる。
黒についての条件も達成するには、白で塗られたグリッドが黒で塗られたグリッドを分断していなければ良い。
コードを書くのが楽になるようにすることを考えると、縦横それぞれ$1$マスずつ開けて白で塗るグリッドを選ぶことにするのが良さそうである。
$A = 1$の時も白黒逆にすれば同様にグリッドを塗れる。
また$A \neq 1$,$B \neq 1$の時は、グリッドを上下半分に分けてそれぞれ$A = 1$,$B = 1$の場合を構成すれば良い。
但し、分けた先では$A,B$は与えられた値より$1$小さいものを用いる。
この塗り方だと縦横$100$マスのグリッドに連結成分は各色最大で$1251$個作れるので十分である。
ソースコード
マクロ等はこちら
const int N = 100;
int A,B;
char ans[N][N];
int main(){
cin >> A >> B;
repp(i,0,N/2) repp(j,0,N) ans[i][j] = '#';
repp(i,N/2,N) repp(j,0,N) ans[i][j] = '.';
[]{
for(int i = 0 ; i < N/2 ; i += 2) for(int j = 0 ; j < N ; j += 2){
if(A == 1) return;
ans[i][j] = '.';
--A;
}
}();
[]{
for(int i = N-1 ; i > N/2 ; i -= 2) for(int j = 0 ; j < N ; j += 2){
if(B == 1) return;
ans[i][j] = '#';
--B;
}
}();
cout << N << ' ' << N << endl;
repp(i,0,N){
repp(j,0,N) cout << ans[i][j];
cout << endl;
}
return 0;
}解法まとめ
縦横$100$マスのグリッドの上半分を黒で塗り、そのうち$A-1$マスを白で塗りなおす。
塗りなおすグリッドは縦横$1$マスずつ開けて選んでいく。(7,10-14行)
下半分も白黒入れ替えて同様にグリッドを塗る。(8,17-21行)