読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ゆらふなセンパイお誕生日コンテスト B - 儀式

さてB問題。これが一番時間かかった。

問題

yurahuna2016.contest.atcoder.jp

元問題はこちら

code-thanks-festival-2014-a-open.contest.atcoder.jp

石像が南北方向にR行, 東西方向にC列並んでいる。最初はすべて南を向いている。左上を(1, 1)とする。

儀式はN回の手順からなり、1回の手順においては、指定された長方形領域内の石像をすべて左に90度回転させる。

今年の儀式では手順のうち、1つを飛ばしてしまった。儀式の最後に南を向いていた石像の個数Mが分かっているとき、飛ばした可能性がある手順の候補の番号をすべて出力しなさい。ただし少なくとも1つ忘れた手順の候補があることが保証される。

制約

 1 \leq R \leq 50

 1 \leq C \leq 50

 0 \leq M \leq 50

 1 \leq N \leq 5000

解法

まず、手順を1つも忘れずにすべて実行した場合の結果を求めておく。石像の方向を記録するには、南東北西を0, 1, 2, 3の数字で表すことにすると、長方形領域に入ったときに+1→mod4すればOK。最終場面の配置がわかったら、その時点で南を向いている数を記録しておきます(これをSとしましょう)

これが終わったら、各手順を忘れたときの、最後に南を向いている石像の数を求める。これを求めるには、手順を全部実行したときの最終場面において、忘れた手順の逆の操作(右に90度回転)をすればOK。そうすると、長方形内で1が0に、0が3になります。求めたいのは最終的に0となっているものの個数ですから、ある手順を忘れたとき最後に南を向いている石像の個数はS - (長方形内の1の個数) + (長方形内の0の個数)で求まります。

各手順についてこれを求めて、個数がMと一致したら候補とすれば解決です。計算量は O(NCR)なので間に合います。

所要時間は31:56

const int MAX_N = 5000;
const int MAX_R = 50;
const int MAX_C = 50;
 
int R, C, M;
int N;
int li[MAX_N][4];
int a[MAX_R][MAX_C];
 
void input() {
    scanf("%d%d%d", &R, &C, &M);
    scanf("%d", &N);
    REP(i, N) {
        int t[4];
        scanf("%d%d%d%d", &t[0], &t[1], &t[2], &t[3]);
        REP(k, 4) {
            li[i][k] = t[k] - 1;
        }
    }
}
 
void solve() {
    REP(i, N) {
        FOR(r, li[i][0], li[i][1] + 1) {
            FOR(c, li[i][2], li[i][3] + 1) {
                a[r][c] += 1;
                if (a[r][c] == 4) {
                    a[r][c] = 0;
                }
            }
        }
    }
 
    int south = 0;
    REP(i, R) {
        REP(j, C) {
            if (a[i][j] == 0) {
                south++;
            }
        }
    }
 
    REP(i, N) {
        int cnt = south;
        FOR(r, li[i][0], li[i][1] + 1) {
            FOR(c, li[i][2], li[i][3] + 1) {
                if (a[r][c] == 1) {
                    cnt++;
                } else if (a[r][c] == 0) {
                    cnt--;
                }
            }
        }
        if (cnt == M) {
            printf("%d\n", i + 1);
        }
    }
 
}
 
int main() {
    input();
    solve();
    return 0;
}

最初は「累積和?2次元いもす法??」とか考えたけど、意外とシンプルに解けました。