【AtCoder】ARC173 C - Not Median

問題

解法

以下 0-indexed とする。

の場合、区間を一方向に伸ばしながら Segment Tree 上の二分探索を行うなどして求める。

それ以外のとき、各 に対し、自身より大きい値か小さい値かしか興味がないので便宜上 + と - とおく。

(1) +0+ や -0- のとき

この区間の中央値は ではないため答えとなり、かつ 3 が最小なのでこれで良い。

(2) -0+ や +0- のとき

+0- を例に取ると -+-+...-+0-+...-+ となる区間は 0 を含みつつ奇数長の区間を選ぶ場合、どこからどこまでを選んでも中央値が 0 になってしまうのでダメ。

逆に初めて -- や ++ が連続するところから 0 まで（場合によっては奇数長になるように反対側の区間を 1 だけ余計に）取ると、その区間は中央値が 0 にならない。 反対側の区間を必要以上に長く取る必要はないので、これを左右それぞれについて計算し、区間長がより小さいものが答えになる。

よって左右それぞれについて愚直に ++ か -- が出てくる部分まで伸ばしていくことで答えを求めることができる。

これは一見計算量が のように見えるが、この愚直がどこからどこまで行われるかについて考えると実は である。

各 に対し をプロットした図を考えると (2) となるのは *↘*↘* か *↗*↗* であり、これらの位置を とおくと 愚直に伸ばしていく操作は隣接する で必ず終了するということがわかる。

隣接する が *↘*↘* の場合を例に取ると 0*** か *0** か **0* か ***0 であるが、どこでも必ず *↘*↘* が登場していることがわかる。（図がないため説明が難しいが）

よって以上を実装すれば AC できる。(P[i - 1] - P[i]) * (P[i + 1] - P[i]) > 0 などのオーバーフローに気をつける。（一敗）

#include "my_template.hpp"
#include "data_structure/segment_tree.hpp"
#include "algebra/monoid_sum.hpp"
using namespace std;

signed main() {
    INT(N);
    VEC(i64, P, N);
    REP(i, N) P[i]--;
    vector<int> ans(N, -1);
    // calc ans[0], ans[N - 1]
    REP(t, 2) {
        SegmentTree<MonoidSum<int>> seg(N);
        int len = 0;
        REP(i, N) {
            seg.set(P[i], 1);
            len++;
            auto f = [&](int s) -> bool { return s <= len / 2; };
            if (len >= 3 and len % 2 == 1) {
                if (seg.max_right(0, f) != P[0]) {
                    ans[0] = len;
                    break;
                }
            }
        }
        // reverse
        REV(P);
        REV(ans);
    }
    // calc ans[1], ans[2], ... , ans[N - 2]
    REP(i, 1, N - 1) {
        if ((P[i - 1] - P[i]) * (P[i + 1] - P[i]) > 0) {
            // +0+ or -0-
            ans[i] = 3;
        } else {
            // +0- or -0+
            int l = i - 2, r = i + 2;
            while (l >= 0 and (P[l] - P[i]) * (P[l + 1] - P[i]) < 0) l--;
            while (r < N and (P[r] - P[i]) * (P[r - 1] - P[i]) < 0) r++;
            int len = INF<int>;
            if (l >= 0) chmin(len, i - l + 1);
            if (r < N) chmin(len, r - i + 1);
            if (len == INF<int>) continue;
            ans[i] = len / 2 * 2 + 1;
        }
    }
    print(ans);
    return 0;
}

感想

愚直操作が で目から鱗だった。こういう計算量の見積もり方をしたことがなく面白かった。（解けなかったけど）

ARC173 B（点集合が与えられるので非退化な三角形を可能な限りたくさん作るやつ）もたまたますんなりと解けたが証明はできなかったので、ARC は証明能力が重要だなと思った。

ARC の黄 diff 解けね〜な〜