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; }