AtCoder Beginner Contest 092 解説備忘録

前書き

AtCoder Beginner Contest 092 を解いてみた．解けなかった問題の備忘録．

D問題

[問題はこちら]

・100×100マスのグリッドを用意．

・上半分(50×100)を白，下半分(50×100)を黒に塗る．これで白の連結成分は1，黒の連結成分は1となる．

・【白の連結成分を作る】
Aの数だけ，下半分の黒部分から白にくり抜いていく．ここで，ちょうどビルの窓のように，隙間をあけてくり抜くことで，黒の連結成分を減らすことなく白の連結成分を増やせる．(初期で上半分に白の連結成分が1あるので，A-1個を下半分でくり抜くことに注意)

・【黒の連結成分を作る】
同様に，Bの数だけ，上半分の白部分から黒にくり抜いていく．ここで，ちょうどビルの窓のように，隙間をあけてくり抜くことで，白の連結成分を減らすことなく黒の連結成分を増やせる．(初期で下半分に黒の連結成分が1あるので，B-1個を下半分でくり抜くことに注意)

以下ACのコード：

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

int main() {

    int a,b;
    cin >> a >> b;

    cout << 100 << " " << 100 << endl;

    vector<vector<char>> x(50, vector<char>(100,'.')); //上半分は最初白
    vector<vector<char>> y(50, vector<char>(100,'#')); //下半分は最初黒

    //白の個数を調整
    int p,q;
    p = (a-1)/49 + 1; //p段に及ぶ
    q = (a-1)%49; //最終段の個数

    FOR(i, 0, p){
        if(i!=p-1){
            FOR(j, 0, 49){
                y[2*i+1][2*j+1] = '.';
            }
        }else{
            FOR(j, 0, q){
                 y[2*i+1][2*j+1] = '.';
            }
        }
    }

     //黒の個数を調整
    p = (b-1)/49 + 1; //p段に及ぶ
    q = (b-1)%49; //最終段の個数

    FOR(i, 0, p){
        if(i!=p-1){
            FOR(j, 0, 49){
                x[2*i+1][2*j+1] = '#';
            }
        }else{
            FOR(j, 0, q){
                x[2*i+1][2*j+1] = '#';
            }
        }
    }


    FOR(i, 0, 50){
        FOR(j, 0, 100){
            cout << x[i][j];
            if(j==99){
                cout << endl;
            }
        }
    }
    FOR(i, 0, 50){
        FOR(j, 0, 100){
            cout << y[i][j];
            if(j==99){
                cout << endl;
            }
        }
    }


    return 0;
}

あとがき

思いつかん．
精進します．