atcoder ABC 087 D - Grid Components

AtCoder

問題

D - Grid Components

解法

  • $ h, w $ は 100以下という条件なので、$ h = 100, w = 100 $ で固定して考える
  • $ 1 \leq A \leq 500, 1 \leq B \leq 500 $ の制約であれば、100x100 の 半分 50x50 の領域に500個の連結成分を作ることは可能

上記を前提として考えると、100x100の半分ずつの領域で白、黒それぞれ連結成分を必要数作ればよいことがわかる。

1-50行目を黒、51-100行目を白で初期化しておき、1-50行目で白の連結成分、51-100行目で黒の連結成分を作ることを考える。

連結成分は上下左右に隣合わなければ良いので、今回の制約であれば1行飛ばしでも収まるので以下のように並べて解ける。

.#.#.#.#.#
##########
.#.#.#.#.#
##########
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int a,b;
const int h=100,w=100;
char g[h][w];

int main() {
  cin >> a >> b;
  a--; b--;

  REP(i,h) REP(j,w) g[i][j] = i<h/2 ? '#' : '.';

  for (int i=0; i<h; i+=2) {
    if (h/2+(h/2)%2+2 == i) swap(a,b);
    for (int j=0; j<w; j+=2) {
      if (a==0) break;
      g[i][j] = g[i][j] == '.' ? '#' : '.';
      a--;
    }
  }

  cout << h << " " << w << endl;
  REP(i,h) REP(j,w) {
    cout << g[i][j];
    j == w-1 && cout << endl;
  }
}