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

hamayanhamayan's blog

マンションの改築 [第四回 アルゴリズム実技検定 L]

競技プログラミング

https://atcoder.jp/contests/past202010-open/tasks/past202010_l

解説

https://atcoder.jp/contests/past202010-open/submissions/21473177

難しい問題だが、特殊なアルゴリズムは要求しない。
アルゴリズムをただ適用するのではなく、テクニックを駆使してアルゴリズムを組み立てていく。

一般的な話というか、雑談

こういう問題で使えるテクとして以下のようなものがある。

  • 複数のものに同じだけ足し合わせる場合はoffsetを用意してoffsetに足せばいい
  • 隣接している数が同じ = 隣接している数の差分が0である
    • このような考え方を一般化した、階差数列を使ったテク

この辺を知っているとエッセンスを使うことで効率よくアルゴリズムを組み立てることができる。
この辺の経験も無しに、1から答えのアルゴリズムが作れたとしたらかなり才能があるように思う。

差分で考える

階差数列で考えることにしよう。
例えば、

10 20 30 20

であれば、h[i+1]-h[i]をする。

10 10 -10

これで例えばクエリ1で奇数マンションに5だけ増やしたとすると

5 15 -15

となる。さらに5増やすと

0 20 -20

となり、0となるものがあるので、等しいものが1つできる。
このように差分で考えたとき、各操作が終わった時点で高さが等しいものの個数は差分が0である個数と読み替えることができる。
これはとても嬉しい変換で、差分をmapなどで個数を持っておくことで差分[0]を答えれば答えになるようなイメージ。

offsetを使う。

先ほどの例に対して、クエリ2によって偶数マンションで3だけ増やしたとすると

13 -7 -7

のようになる。よって、これを考慮すると、階差数列的には

  • クエリ1: 奇数マンションにvだけ増やす → 奇数番目に-v, 偶数番目に+v
  • クエリ2: 偶数マンションにvだけ増やす → 奇数番目に+v, 偶数番目に-v

である。
奇数番目のoffsetをodddiff, 偶数番目のoffsetをevendiffとしておけばクエリ1とクエリ2については
このoffsetの計算だけで済む。
offsetが偶奇で分かれるため、階差数列の差分をmapで集計するときにも偶奇で配列を分けておく。
こうすることでoffset込みで答えはoddcnt[-odddiff] + evencnt[-evendiff]とすることができる。
すごいざっくり解説な気もするがここまでまずは理解することが大切。

クエリ3

クエリ3は1つだけを操作するということなので、差分を頑張って計算する。
具体的にはi番目を操作するとなると、h[i+1]-h[i]とh[i]-h[i-1]の2つの計算結果が変化することになるので、
それを計算する。
コードを見るとやっていることはそれほど難しくない。

  1. 現状態での差分の個数を減らす
  2. 差分の状態を変化させる（クエリによって）
  3. 変化後状態での差分の個数を増やす

というのを差分計算している。

終わりに

中々うまく説明できなかった体感がある。
公式解説とかを利用しながら理解できていることを祈る。

int N, Q, H[201010];
ll diff[201010];
ll odddiff = 0, evendiff = 0;
map<ll, int> oddcnt, evencnt;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> H[i];
    rep(i, 0, N - 1) diff[i] = H[i + 1] - H[i];
    rep(i, 0, N - 1) {
        if (i % 2 == 0) oddcnt[diff[i]]++;
        else evencnt[diff[i]]++;
    }

    rep(_, 0, Q) {
        int t; cin >> t;
        if (t == 1) {
            int v; cin >> v;
            odddiff -= v;
            evendiff += v;
        }
        else if (t == 2) {
            int v; cin >> v;
            odddiff += v;
            evendiff -= v;
        }
        else {
            int u, v; cin >> u >> v;
            u--;
            
            if (u % 2 == 0) {
                if (u) {
                    evencnt[diff[u - 1]]--;
                    diff[u - 1] += v;
                    evencnt[diff[u - 1]]++;
                }

                if (u < N - 1) {
                    oddcnt[diff[u]]--;
                    diff[u] -= v;
                    oddcnt[diff[u]]++;
                }
            }
            else {
                oddcnt[diff[u - 1]]--;
                diff[u - 1] += v;
                oddcnt[diff[u - 1]]++;

                if (u < N - 1) {
                    evencnt[diff[u]]--;
                    diff[u] -= v;
                    evencnt[diff[u]]++;
                }
            }
        }

        int ans = oddcnt[-odddiff] + evencnt[-evendiff];
        printf("%d\n", ans);
    }
}