【AtCoder】ABC 395 B - Make Target | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 72

問題概要

のグリッドがあり、上から 行目、左から 列目のマスをマス と表す。はじめ、どのマスにも色は塗られていない。

これから、 の順に、以下の操作を行う。

1. とする。
   1. であるならば、 が奇数ならば黒、偶数ならば白で を左上、 を右下とする矩形領域に含まれるマスを塗りつぶす。このとき、既に色が塗られているマスについては色を上書きする。
   2. であるならば、何もしない。

最終的に各マスがどの色で塗られているかを求めよ。

制約

• 
• 入力はすべて整数。

考察

操作の手順通りの処理をforループや条件分岐を用いて実装していこう。

矩形領域の塗りつぶしには、二重forループで良いだろう。

全体の計算量は となるが、 の制約は と小さいので、十分高速である。

実装例

#include <bits/stdc++.h>
using namespace std;

#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;

    vector<vector<char>> grid(N, vector<char>(N));
    repe(i, 1, N)
    {
        int j = N + 1 - i;
        if (i <= j)
        {
            char c;
            if (i % 2 == 0)
                c = '.';
            else
                c = '#';

            repe(di, i, j) repe(dj, i, j)
            {
                grid[di - 1][dj - 1] = c;
            }
        }
    }

    rep(i, 0, N)
    {
        rep(j, 0, N)
        {
            cout << grid[i][j];
        }
        cout << endl;
    }

    return 0;
}

atcoder.jp

実装時間: 5分

コメント

「書かれている通りに実装する」これを徹底したい。