https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_e

解説

https://atcoder.jp/contests/joi2017yo/submissions/8141535

まず、順当に考えると、座標を全探索して、シミュレーションをして、その座標が尾根であるかを判定する。
どのようにシミュレーションするかであるが、雨水が通過するというのは、その座標から到達可能であるとも言える。
到達可能性解析といえば、幅優先探索。
幅優先探索をして、雨水が溜まる部分に複数箇所到達可能なら尾根である。
これをやるとO(H^2W²)なので厳しい。

ありがちな方針ではあるが、始点は尾根であるかは事前に分からないが、終点が溜まる場所であることは事前にわかる。
つまり、溜まる場所を始点として考えてみると考えやすいのではないか。
幅優先探索を逆に行ってみる。
標高が低い所から高い所へ逆流させよう。
このときに、どの溜まる場所から逆流してきたかを保存しておこう。
もし、3つ以上の場所から逆流してきた場合は、尾根判別をしたいだけなので、2つだけ保持しておけばいい。
これで、全ての場所について、溜まる場所について特定ができるので、2つ以上溜まる場所があるなら尾根として計上する。

幅優先するときは、逆順にやるのが面倒なので、全て異なる数であることを利用して、小さい数から順番に操作を行えばいい。

int H, W, A[1010][1010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
set<int> ponds[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    rep(y, 0, H) rep(x, 0, W) {
        bool ok = true;
        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                if (A[y][x] > A[yy][xx]) ok = false;
            }
        }
        if (ok) ponds[y][x].insert(y * W + x);
    }

    vector<pair<int, int>> ord;
    rep(y, 0, H) rep(x, 0, W) ord.push_back({ A[y][x], y * W + x });
    sort(all(ord));

    fore(p, ord) {
        int x = p.second % W;
        int y = p.second / W;

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                if (A[y][x] < A[yy][xx]) {
                    fore(pond, ponds[y][x]) ponds[yy][xx].insert(pond);
                    while (2 < ponds[yy][xx].size()) {
                        ponds[yy][xx].erase(ponds[yy][xx].begin());
                    }
                }
            }
        }
    }

    int ans = 0;
    rep(y, 0, H) rep(x, 0, W) if (2 <= ponds[y][x].size()) ans++;
    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

尾根 (Ridge) [第１６回日本情報オリンピック予選（オンライン） E]

解説