はまやんはまやんはまやん

hamayanhamayan's blog

チップ・ストーリー ~漆黒編~ [DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 B]

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_b

解説

https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650234

ok[y][x] := 座標(x,y)が真っ黒か
というのを用意して、真っ黒でない領域を消していくことを考えよう。
左上の真っ黒でない領域は、(0,0), (0, (N+1)/2-1 ), ( (N+1)/2-1 , 0)で囲まれた三角形の部分である。
(N+1)/2はN/2の切り上げを表現している。
この部分のok[y][x]を0にしよう。
 
この作業を残りの3隅でも行うが、画面を回転させることで同じコードで処理させる。
自分はrotateClockwise関数を持ってるので、これで、左上の領域を処理→90度回転をして、4隅を処理した。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
 
    vector<vector<int>> ok(N, vector<int>(N, 1));
    rep(r, 0, 4) {
        rep(x, 0, (N + 1) / 2) {
            int sy = (N + 1) / 2 - 1 - x;
            rep(y, 0, sy + 1) ok[x][y] = 0;
        }
        ok = rotateClockwise(ok);
    }
 
    int ans = 0;
    rep(y, 0, N) rep(x, 0, N) if (ok[y][x]) ans++;
    cout << ans << endl;
}