mayoko’s diary

プロコンとかいろいろ。

Educational Codeforces Round 8 E. Zbazi in Zeydabad

D は問題文が理解できないので桁 DP だよねということだけ言っといて退散します。
というかこの問題, 趣旨的に tourist を助けて欲しいという問題になっていますが絶対 tourist のほうが早く解けるんだよなぁ。

解法

まず, toR[i][j] = (i, j 番目から z がどこまで右に続いているか), toL[i][j] = (i, j 番目から z がどこまで左に続いているか), toD[i][j] = (i, j 番目から z がどこまで左下に続いているか)
というのをメモしておきます。これは O(nm) で出来ますね。

で, そしたら invR[i][j] = (x + toR[y][x] - 1 = j となる x の集合) というのを作ります。

ここからが解法の本番です。

"Z" という形になっているかを調べるために, "Z" の右上部分の角に注目します(この座標を (r, c) とする)。とりあえず, Z の大きさとしてあり得るものは, mini = min(toL[r][c], toD[r][c]) に絞られます。で, 後は "Z" の下の直線部分があっているかを見たいわけですが, これを高速で行うために Binary Indexed Tree を使いましょう。

c を右側から見ていった時, invR[r][c] に値が入っていたら, BIT[x+y] の y 番目の要素に 1 足す, ということを行うと, (r, c) について下の直線部分がちゃんとあるかどうかというのは, BIT[r+c] の, [r, r+mini) の要素の和を求めれば良いことになるので, 答えが高速で求められます。

対角線上の頂点が同じグループで扱えることに着目した面白い問題でした。あと, BIT では計算の都度 BIT を更新していくパターンの問題が多いですが, 今回もそのパターンでした。

// 0-based Binary Indexed Tree
// 数え上げ用
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s += bit[i]);
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] += x);
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)-sum(a);
    }
    // sum(0, i) >= wとなる最小のiを求める 存在しなければmaxを返す
    int lb(T w) {
        if (w <= 0) return 0;
        int k = 1;
        while (k <= max) k <<= 1;
        int i = 0;
        for (; k > 0; k >>= 1) if (i+k <= max && bit[i+k] < w) {
            w -= bit[i+k];
            i += k;
        }
        return i+1;
    }
};

const int MAXN = 3030;
int toR[MAXN][MAXN], toL[MAXN][MAXN], toD[MAXN][MAXN];
vi invR[MAXN][MAXN];
string field[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> field[i];
    // toR
    for (int i = 0; i < n; i++) {
        int l = 0;
        while (l < m) {
            if (field[i][l] == '.') {
                toR[i][l++] = 0;
            } else {
                int r = l;
                while (r < m && field[i][r] == 'z') r++;
                for (int j = l; j < r; j++) toR[i][j] = r-j;
                l = r;
            }
        }
    }
    // invR
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        if (toR[i][j] != 0) invR[i][j+toR[i][j]-1].push_back(j);
    }
    // toL
    for (int i = 0; i < n; i++) {
        int r = m-1;
        while (r >= 0) {
            if (field[i][r] == '.') {
                toL[i][r--] = 0;
            } else {
                int l = r;
                while (l >= 0 && field[i][l] == 'z') l--;
                for (int j = r; j > l; j--) toL[i][j] = j-l;
                r = l;
            }
        }
    }
    // toD
    for (int i = 0; i < n+m-1; i++) {
        int sy = (i < m) ? 0 : i-(m-1);
        int sx = (i < m) ? i : m-1;
        while (sy < n && sx >= 0) {
            if (field[sy][sx] == '.') {
                toD[sy++][sx--] = 0;
            } else {
                int y = sy, x = sx;
                while (y < n && x >= 0 && field[y][x] == 'z') y++, x--;
                for (int j = sy, k = sx; j < y; j++, k--) toD[j][k] = y-j;
                sy = y, sx = x;
            }
        }
    }
    vector<BIT<ll> > bits(n+m-1, BIT<ll>(n));
    ll ans = 0;
    for (int c = m-1; c >= 0; c--) {
        for (int r = 0; r < n; r++) {
            for (int x : invR[r][c]) {
                bits[r+x].add(r, 1);
            }
        }
        for (int r = 0; r < n; r++) {
            int mini = min(toL[r][c], toD[r][c]);
            if (mini == 0) continue;
            ans += bits[r+c].sum(r, r+mini);
        }
    }
    cout << ans << endl;
    return 0;
}