ABC 089

Table of Contents

https://atcoder.jp/contests/abc089

A. Grouping 2

https://atcoder.jp/contests/abc089/tasks/abc089_a

B. Hina Arare

https://atcoder.jp/contests/abc089/tasks/abc089_b

C. March

https://atcoder.jp/contests/abc089/tasks/abc089_c

D. Practical Skill Test

https://atcoder.jp/contests/abc089/tasks/abc089_d

自力 AC

考えたこと

解法

「考えたこと」に従った実装したもの。$R_{\max}$ から下っていくことはできるけれど、最小の $L$ の出発点を考えると面倒そうに思えてこの実装になった。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, D;
    cin >> H >> W >> D;

    vector A(H, vll(W));
    rep(i, H) rep(j, W) {
        cin >> A[i][j];
        A[i][j]--;
    }

    vector<pair<int, int>> num_pos(H * W);
    rep(i, H) rep(j, W) num_pos[A[i][j]] = {i, j};

    int Q;
    cin >> Q;
    vector<pair<int, int>> queries;
    rep(i, Q) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        queries.emplace_back(l, r);
    }

    vint rmax(D, 0);
    vector<bool> rexists(D, 0);
    for (auto [l, r] : queries) {
        chmax(rmax[r % D], r);
        rexists[r % D] = true;
    }

    map<pair<int, int>, ll> memo;
    auto f = [&](auto f, int l, int r) -> ll {
        if (l == r)
            return 0;
        auto [ni, nj] = num_pos[l + D];
        auto [i, j] = num_pos[l];
        return memo[{l, r}] = abs(ni - i) + abs(nj - j) + f(f, l + D, r);
    };

    rep(i, D) {
        if (!rexists[i])
            continue;
        f(f, i, rmax[i]);
    }

    for (auto [l, r] : queries) {
        int rmx = rmax[r % D];
        cout << memo[{l, rmx}] - memo[{r, rmx}] << '\n';
    }
}

解説見て直した実装。最小の $L$ は単純に $0 \sim D-1$ 出発で考えればいいだけだった。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, D;
    cin >> H >> W >> D;

    vector A(H, vll(W));
    rep(i, H) rep(j, W) {
        cin >> A[i][j];
        A[i][j]--;
    }

    vector<pair<int, int>> num_pos(H * W);
    rep(i, H) rep(j, W) num_pos[A[i][j]] = {i, j};

    vll cumsum(H * W);
    rep2(d, D, H * W) {
        auto [ni, nj] = num_pos[d];
        auto [i, j] = num_pos[d - D];
        cumsum[d] = cumsum[d - D] + abs(ni - i) + abs(nj - j);
    }

    int Q;
    cin >> Q;
    rep(_, Q) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        cout << cumsum[r] - cumsum[l] << endl;
    }
}