SRM 452 div1 easy: NotTwo - mayoko’s diary

問題

解法

石を置く場所を o, 置かない場所を x とすると,

ooxxooxxoo
ooxxooxxoo
xxooxxooxx
xxooxxooxx

のように, 2 マスおきに見た時市松模様っぽくなるようにするのが最適です。理由を考えてみます。

単純な問題として, 「距離が 1 以下のマスの両方に石を置いてはならない」というルールを考えると, これの解は明らかに市松模様のように石を置いて行くのが良いです。
この問題のように, 2 マス離れたマス同士で, 両方に石を置いてはならないルールでは, (2n, 2m), (2n, 2m+1), (2n+1, 2m), (2n+1, 2m+1) という 4 つのタイプそれぞれについて, (n, m) が市松模様になるように石を置いて行くのが良い, ということになるので, 上のように石を置いて行くのが最適です。

010101010101
232323232323
010101010101
232323232323

↑「0」というグループについて市松模様, 「1」というグループについて市松模様, ...

int done[1111][1111];

class NotTwo {
public:
    int maxStones(int width, int height) {
        memset(done, -1, sizeof(done));
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (done[i][j] == -1) {
                    done[i][j] = 1;
                    for (int k = 0; k < 4; k++) {
                        int ni = i+2*dx[k], nj = j+2*dy[k];
                        if (ni < 0 || ni >= width || nj < 0 || nj >= height || done[ni][nj] != -1) continue;
                        done[ni][nj] = 0;
                    }
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < width; i++) for (int j = 0; j < height; j++) if (done[i][j] == 1) ret++;
        return ret;
    }
};