Kth Excluded [AtCoder Beginner Contest 205 D]

https://atcoder.jp/contests/abc205/tasks/abc205_d

解説

https://atcoder.jp/contests/abc205/submissions/23456683

自分はクエリ先読みと尺取り法っぽく解いた。
考え方が思いついても実装も大変な問題。
クエリ先読みについてはモチベは簡単なので、軽く説明するが、尺取り法については知らない場合はもっと入門的な問題で学んでくることをお勧めする。
（二分探索とか使えば、クエリ先読みも二分探索もいらない気がする）

クエリ先読み

クエリ問題への取り組み方の1つとしてクエリ先読みというやり方がある。
バルク実行という言い方もできるし、こちらの方が馴染みがある人も多いかもしれない。
クエリを貰った順から1つ1つ処理するのではなく、一気にまとめてやってしまうと計算量改善が図れるという雰囲気である。

クエリをすべて読み込んでおいて、Kの値が小さいものから順番に処理していくことを考える。
最終的にはクエリを読み込んだ順で出力する必要があるので、順番も保持した状態にしておく工夫が必要となる。
やり方は色々あるが、自分はidxを配列ordに入れておいて、Kの最小で特殊ソートして使うことにした。
すると、順番はindex順に処理していき、実際のKの値はK[ord[index]]で取ってくればいい。

これ以降は順番とかクエリ先読みとかいう部分は無視して解説する。
実装時に巻き取ればいいので、これ以降はAと同様にKは普通に昇順であったときに、どうやってクエリをさばくかというのを考える。

尺取り法

数のありうる空間は[1,10¹⁸]なので、あまりに大きすぎる。
よって、ある程度まとめて計算する必要があるのだが、それをAの値を境界線としてグループ分けすることにする。
グループ分けをするとA1の前で1つ、Aの間でN-1個、ANの後で1つのN+1のどこかのグループにすべての答えが属すことになる。
ちょうどこれは、Kが昇順に並んでいると仮定すると、Kが大きくなるにつれて、グループの番目も同様に大きくなることが分かる。
このように一方が増加するときに、もう片方も単調的な動きをする場合に尺取り法が効率的に使える。

自分の実装では、グループの方を小さい方から順番になめていって、Kを小さい方から順番にグループにマッピングしていくようにしている。
答えをいかに出すかであるが、K[i]番目がA[j]とA[j+1]の間にあることが分かっていれば、A[j]より前のAでない数の個数は簡単に求めることができるので、
K[i]からその個数を引けばA[j]+1から何番目の数が答えになるかが分かる。
それをA[j]から足して答えとすればいい。

とあるグループについて考えるときにそれ以前のAでない数の個数を変数cntとして保持していくことでグループを小さい方から見ながらそれまでの個数も保持でき、
Kがそのグループに属すと分かっていれば答えが求められるようになっている。
尺取り法の説明は、基本概念をまずしっかり理解していないと、何とも難しい…

二分探索を使う場合

グループのA以外の個数を累積和で持っておいて二分探索でどのグループに属すかを判定していけば、クエリ先読みも尺取り法もいらないなと解説書いてて思いました。

int N, Q; ll A[101010];
ll K[101010];
ll ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, Q) cin >> K[i];

    vector<int> ord;
    rep(i, 0, Q) ord.push_back(i);
    sort(all(ord), [&](int a, int b) { return K[a] < K[b]; });

    int ord_i = 0;
    ll cnt = 0;
    while (ord_i < Q && cnt + 1 <= K[ord[ord_i]] && K[ord[ord_i]] <= cnt + A[0] - 1) {
        ans[ord[ord_i]] = 0 + K[ord[ord_i]] - cnt;
        ord_i++;
    }
    cnt += A[0] - 1;
    rep(i, 1, N) {
        while (ord_i < Q && cnt + 1 <= K[ord[ord_i]] && K[ord[ord_i]] <= cnt + A[i] - A[i - 1] - 1) {
            ans[ord[ord_i]] = A[i - 1] + K[ord[ord_i]] - cnt;
            ord_i++;
        }
        cnt += A[i] - A[i - 1] - 1;
    }
    while (ord_i < Q) {
        ans[ord[ord_i]] = A[N - 1] + K[ord[ord_i]] - cnt;
        ord_i++;
    }

    rep(i, 0, Q) printf("%lld\n", ans[i]);
}