2018 codeFlyer 予選 D ハンコ (500 点)

座標圧縮して二次元いもす法だけど、頭がごっちゃになった。

• 問題へのリンク

問題概要

白黒からなる N × M の二次元盤面が与えられる。これをより大きな盤面 H × W の左上隅に置く。N × M 盤面を H × W 盤面からはみ出さない範囲で動かしていく。このとき「黒」が通過する部分全体のマス目の個数が何個になるかを求めよ。

制約

• 1 <= N, M <= 2000
• 1 <= H, W <= 10⁹

解法

H >= N * 2, W >= M * 2 のとき、その間にある部分の大半は埋まることになる。

そんなときは H = N * 2, W = M * 2 と座標圧縮して、黒を数える。このとき 2 次元いもす法を用いた。

さらに座標圧縮した部分を数え上げる。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long H, W, N, M;
vector<string> base;
int sum[2200][2200];

int main() {
    cin >> H >> W >> N >> M;
    base.resize(N);
    for (int i = 0; i < N; ++i) cin >> base[i];

    /* N, M それぞれ 2 倍以上になっている部分はつぶして 2 次元いもす */
    long long tH = min(H, N*2), tW = min(W, M*2);
    for (long long i = 0; i < N; ++i) {
        for (long long j = 0; j < M; ++j) {
            if (base[i][j] != '#') continue;
            long long i2 = i + (tH - N) + 1;
            long long j2 = j + (tW - M) + 1;
            sum[i][j] += 1; sum[i2][j] -= 1; sum[i][j2] -= 1; sum[i2][j2] += 1;
        }
    }
    for (int i = 0; i < 2100; ++i)
        for (int j = 0; j < 2100; ++j)
            sum[i][j+1] += sum[i][j];
    for (int j = 0; j < 2100; ++j)
        for (int i = 0; i < 2100; ++i)
            sum[i+1][j] += sum[i][j];

    /* 計算 */
    long long res = 0;
    for (int i = 0; i < tH; ++i) {
        for (int j = 0; j < tW; ++j) {
            if (sum[i][j]) ++res;
        }
    }
    long long left = 2100, right = 2100, top = 2100, bottom = 2100;
    for (long long i = 0; i < N; ++i) for (long long j = 0; j < M; ++j) {
        if (base[i][j] == '.') continue;
        left = min(left, j);
        right = min(right, M-1-j);
        top = min(top, i);
        bottom = min(bottom, N-1-i);
    }
    if (left != 2100) {
        res += (H - tH) * (W - right - left);
        res += (W - tW) * (H - top - bottom);
        res -= (H - tH) * (W - tW);
    }
    cout << res << endl;
}