Codeforces Round #432 Div.2 D / Div.1 B - Arpa and a list of numbers

http://codeforces.com/contest/850/problem/B

問題概要

N要素の数列Aが与えられる。以下の操作を好きなだけ繰り返して、数列の全要素のGCDが1でなくなるようにしたい。目的を達成する最小のコストを求めよ。

• 操作1. コストxで数列から任意の1要素を取り除く
• 操作2. コストyで数列の任意の1要素に1を足す

1 <= n <= 5×10⁵

1 <= x, y <= 10⁹

1 <= a <= 10⁶

解法

最終的なGCDを固定して考える（この数をgとする）。gの倍数ごとに区間を分けて、その区間ごとに数えるとうまいこといく。

具体的には(kg, (k+1)g]のような区間に含まれる数がgを約数に持つためには、(k+1)gのところまでインクリメントされるしかない。何回目のインクリメントまでがxより得かはxをyで割れば出る。つまり上の区間のうち決まった境界より左の数はxで処理し、右の数はy×距離で処理することになる。境界を仮にmとすると、前者はkg～mの区間に現れる数を累積和すれば求まる。後者は距離に応じてxの係数がインクリメントするので単純な累積和だとだめで、区間内にその数がn回現れるならn回カウントされるような累積和を使いたい。これはxで使った累積和に対してさらに累積和を取ると得られるのでそれを使う（伝われ）、あとそれだけだと区間左外の分もカウントしてしまってるのでそれは良い感じに引く。

頑張ったんですが説明無理だったので要点だけ言うと①GCDを固定します②固定したGCDの倍数ごとに区間を区切ります③区間ごとに累積和を良い感じにやってO(1)で計算します　という感じです。①はO(max(A)), ②はならしでO(log(max(A)))のあわせてO(max(A)log(max(A))).

感想

そもそも解法がむずい上に境界まわりの処理が鬼すぎる、あと解法を書くのもむずすぎる

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
 
void main() {
    auto s = readln.split.map!(to!long);
    auto N = s[0].to!int;
    auto X = s[1];
    auto Y = s[2];
    auto A = readln.split.map!(to!int).array;
    A.sort();
    
    const int MAX = 10^^6 + 1;
    const int border = ((X - 1) / Y).to!int;


    auto cnt = new long[](MAX * 2); 
    auto cntsum = new long[](MAX * 2);
    
    foreach (i; 0..N)
        cnt[A[i]] += 1;
    foreach (i; 0..MAX*2-1)
        cnt[i + 1] += cnt[i];
    foreach (i; 0..MAX*2-1)
        cntsum[i + 1] += cntsum[i] + cnt[i + 1];


    long ans = 1L << 59;
    
    foreach (g; 2..MAX) {
        long tmp = 0;
        for (int l = 1; l < MAX; l += g) {
            int r = l + g - 1;
            int m = max(l, r - border);
            long y = Y * (cntsum[r - 1] - cntsum[m - 1] - cnt[m - 1] * (r - m));
            long x = X * (cnt[m - 1] - cnt[l - 1]);
            tmp += x + y;
        }
        ans = min(ans, tmp);
    }

    debug {
        cnt[0..20].writeln;
        cntsum[0..20].writeln;
    }
    
    ans.writeln;
}

Codeforces Round #432 Div.2 C / Div.1 A - Five Dimensional Points

http://codeforces.com/contest/850/problem/A

問題概要

5次元空間上のN個点が与えられる。この中のある点aについて、異なる点b, cを取ってきたときにab, acのなす角が90度未満となるb, cが存在するとき、aを悪い点と呼び、そうでない場合良い点と呼ぶ。良い点をすべて答えよ。

1 <= N <= 10³

解法

Nが33より大きいとき、答えは0である。そうでない場合はN³で全探索すればよい。理由：5次元空間には5個の軸があって2⁵個の象限が存在する。ある点を原点にとったとき同じ象限に存在する点が2点以上あれば、これら3つでつくられる角度は90度未満になる。鳩の巣原理から原点＋32象限よりも多くの点が存在すれば必ず同じ象限に2点が存在することになるので、良い点は存在しないことになる。

問題

天才すぎる

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
     
real angular(int[] x, int[] y, int z[]) {
    int[] v1 = vec(x, y);
    int[] v2 = vec(x, z);
    return acos(product(v1, v2) / sqrt(product(v1, v1) * product(v2, v2)));
}

real product(int[] v1, int[] v2) {
    return v1.length.iota.map!(i => v1[i] * v2[i]).sum.to!real;
}

int[] vec(int[] x, int[] y) {
    return x.length.iota.map!(i => y[i] - x[i]).array;
}


void main() {
    auto N = readln.chomp.to!int;
    auto P = N.iota.map!(_ => readln.split.map!(to!int).array).array;

    if (N >= 50) {
        0.writeln;
        return;
    }

    
    const real EPS = 0.0001;
    auto ans = new bool[N];
    fill(ans, true);
    
    foreach (i; 0..N)
        foreach (j; 0..N)
            foreach (k; 0..N)
                if (i != j && j != k && k != i && angular(P[i], P[j], P[k]) < PI / 2 - EPS)
                    ans[i] = false;

    ans.sum.writeln;
    N.iota.filter!(i => ans[i]).map!(i => (i + 1).to!string).join(" ").writeln;
}

AtCoder Grand Contest 019 D - Shift and Flip

http://agc019.contest.atcoder.jp/tasks/agc019_d

問題概要

0と1のみからなる同じ長さの文字列A, Bが与えられる。以下の操作を何度か行ってAを変化させていったとき、AをBに一致させることができるか判定せよ。また可能な場合は最小の操作回数を求めよ。

• 操作1. Aを左に1文字回転させる
• 操作2. Aを右に1文字回転させる
• 操作3. B[i] = 1であるようなiをひとつ選び、A[i]を反転する

|A| <= 2000

解法

結論：先頭に来るインデックス×左に回す回数、先頭に来るインデックス×右に回す回数の組合せを全探索する。O(|A|^2 log|A|).

まずAの中で最終的に先頭にくるインデックスiを固定する。こうするとすべてのインデックスについて反転操作が必要かどうかが決定できる（＝操作3にかかる回数も一意に決定できる）。あとは要反転のインデックスがすべてB=1のインデックスに当たるように回転操作を繰り返し、最後にiが先頭に来るように回転操作をすればよい。

ありうる回転操作は「左に回す→右に回す→iが先頭になるように回す」もしくは「右に回す→左に回す→iが先頭になるように回す」しかない。愚直にやると左に回す回数×右に回す回数で全探索をかけることになるが、それだとO(N³)になってしまう。しかしうまくやると左に回す回数を決めた時点で右に回す回数は決定できる（逆も）。前計算としてすべてのインデックスについて「左右それぞれについて最低何回回すとB[i]=1のインデックスにたどり着けるか」を記録しておく。これをL, Rとおくと、まず左にn回回した場合はLがn以下のインデックスをすべて反転済とみなせる。あとは残ったインデックスのうちRが最大のものを選び、その分だけ右に回すようにする。最後に先頭の位置が最初決めたところになるよう回す。これは(L, R)のペアで配列をとってソートしたりなんだりすればO(NlogN)でできる。右→左のパターンも同様。これらを先頭固定のO(N)と合わせてO(|A|^2 log|A|).

感想

本番中に大筋で正しい方針にはたどり着いたが通せず。終了後もバグ取りとか細部の詰めが必要ですぐには通せなかった。実装力大事

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
     
     
void main() {
    auto A = readln.chomp.map!(x => x == '1').array;
    auto B = readln.chomp.map!(x => x == '1').array;
    auto N = A.length.to!int;
     
    if (A.any && !B.any) {
        writeln(-1);
        return;
    }
     
    auto L = new int[](N);
    auto R = new int[](N);
     
    foreach (i; 0..N) {
        foreach (j; 0..N) {
            if (B[((i-j)%N+N)%N]) {
                L[i] = j;
                break;
            }
        }
        foreach (j; 0..N) {
            if (B[(i+j)%N]) {
                R[i] = j;
                break;
            }
        }
    }

     
    int ans = 1 << 29;
     
    foreach (i; 0..N) { // A[i]を先頭にする
        int flip = 0;
        auto LR = new Tuple!(int, int)[](N);
     
        foreach (j; 0..N) {
            int k = (i + j) % N;
            if (B[j] != A[k]) {
                flip++;
                LR[j] = tuple(L[k], R[k]);
            } else {
                LR[j] = tuple(0, 0);
            }
        }

        // 左 -> 右
        LR.sort!"a[0] < b[0]";
     
        auto r_max = new int[](N + 1);
        r_max[N] = 0;
     
        for (int j = N - 1; j >= 0; j--) {
            r_max[j] = max(LR[j][1], r_max[j+1]);
        }

        foreach (j; 0..N) {
            int left = LR[j][0];
            int right = r_max[j+1] + left;
            int pos = i - left + right;
            pos = (pos % N + N) % N;
            pos = min(pos, N - pos);
            ans = min(ans, left + right + pos + flip);
            debug {writeln([i, j, left, right, pos]);}
        }


        // 右 -> 左
        LR.sort!"a[1] < b[1]";
     
        auto l_max = new int[](N + 1);
        l_max[N] = 0;
     
        for (int j = N - 1; j >= 0; j--) {
            l_max[j] = max(LR[j][0], l_max[j+1]);
        }

        foreach (j; 0..N) {
            int right = LR[j][1];
            int left = l_max[j+1] + right;
            int pos = i - left + right;
            pos = (pos % N + N) % N;
            pos = min(pos, N - pos);
            ans = min(ans, left + right + pos + flip);
            debug {writeln([i, j, left, right, pos]);}
        }        
    }
     
    ans.writeln;
}

AtCoder Grand Contest 019 C - Fountain Walk

http://agc019.contest.atcoder.jp/tasks/agc019_c

問題概要

東西方向に伸びる10⁸本の道と、南北方向に伸びる10⁸本の道がある。それぞれの道はすべて100メートルごとに等間隔で並んでおり、0から10⁸ -1の番号がついている。南北方向のx番目の道と東西方向のy番目の道が交差している点を(x, y)のように表す。

いまN個の噴水があり、これらはN個の異なる交差点にそれぞれ置かれている。噴水は交差点を中心にした半径10メートルの円形である。また東西方向・南北方向いずれの道にも噴水が2つ以上置かれることはない。

人が通行できるのはそれぞれの道と噴水の外周のみである。なお噴水の内部は通行できない。スタートの交差点とゴールの交差点が与えられるので最短の通行距離を求めよ。

N <= 2 × 10⁵

解法

曲がる場合は普通の道を直角に曲がるより噴水を経由した方が得である。ただしその得はあまり大きくないので、噴水を通るためにあえて遠回りするのはかえって損になる。つまり基本的には南北・東西に無駄なく移動しながら、できるだけ多くの噴水を通るのが最短となる。

通る噴水の数を最大化するためにはどうすればいいか？　例えばスタートが左下でゴールが右上の場合、噴水も左下から右上に並ぶようにとっていく必要がある。この最大値は最長増加部分列の考え方で計算可能。あとは単純な距離から噴水経由によって得した距離を引けばよい。

ただしひとつだけ厄介なコーナーケースがある。それは全部の行あるいは全部の列で噴水を通れる場合である。そのような場合に必ず噴水を通るとすると、最後の噴水では曲がれないのでショートカットにならない。普通に直線を通るところで半円を回る形になるのでその分距離が増える。

感想

なんとか本番で通せた(5WA)

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

alias Tuple!(long, "x", long, "y") Point;
immutable long MAX = 10^^8;

void main() {
    auto s = readln.split.map!(to!long);
    auto x1 = s[0], y1 = s[1], x2 = s[2], y2 = s[3];
    auto N = readln.chomp.to!int;
    auto P = new Point[](N);
    foreach (i; 0..N) {
        s = readln.split.map!(to!long);
        P[i] = Point(s[0], s[1]);
    }

    if (x1 > x2) swap(x1, x2), swap(y1, y2);
    if (y1 > y2) {
        y1 = MAX - y1;
        y2 = MAX - y2;
        foreach (i; 0..N) P[i].y = MAX - P[i].y;
    }

    if (x1 == x2) {
        real ans = (y2 - y1) * 100;
        bool hoge;
        foreach (i; 0..N) if (P[i].x == x1 && P[i].y >= y1 && P[i].y <= y2) hoge = true;
        if (hoge) {
            ans -= 20;
            ans += 10 * PI;
        }
        writefln("%.12f", ans);
        return;
    } else if (y1 == y2) {
        real ans = (x2 - x1) * 100;
        bool hoge;
        foreach (i; 0..N) if (P[i].y == y1 && P[i].x >= x1 && P[i].x <= x2) hoge = true;
        if (hoge) {
            ans -= 20;
            ans += 10 * PI;
        }
        writefln("%.12f", ans);
        return;
    }


    Point[] Q;
    foreach (i; 0..N) {
        if (P[i].x >= x1 && P[i].x <= x2 && P[i].y >= y1 && P[i].y <= y2) Q ~= P[i];
    }

    auto M = Q.length.to!int;
    Q.sort!"a[0] < b[0]"();
    auto st = new SegmentTree(M);
    long[] hoge;
    foreach (i; 0..M) hoge ~= Q[i].y;
    auto fuga = hoge.sort().uniq.array;
    int[long] comp;
    foreach (i; 0..fuga.length) comp[fuga[i.to!int]] = i.to!int;

    foreach (i; 0..M) {
        auto xxx = st.sum(0, comp[Q[i].y]) + 1;
        st.assign(comp[Q[i].y], xxx);
    }

    real ans = (x2 - x1) * 100 + (y2 - y1) * 100;
    auto xxx = st.sum(0, M-1).to!long;
    ans -= 20 * xxx;
    ans += 5 * xxx * PI;

    if (x2 - x1 + 1 == xxx || y2 - y1 + 1 == xxx) {
        ans += 5 * PI;
    } 

    writefln("%.12f", ans);
}

class SegmentTree {
    int[] table;
    int size;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new int[](size);
    }

    void assign(int pos, int num) {
        return assign(pos, num, 0, 0, size/2-1);
    }

    void assign(int pos, int num, int i, int left, int right) {
        if (left == right) {
            table[i] = num;
            return;
        }
        auto mid = (left + right) / 2;
        if (pos <= mid)
            add(pos, num, i*2+1, left, mid);
        else
            add(pos, num, i*2+2, mid+1, right);
        table[i] = max(table[i*2+1], table[i*2+2]);
    }

    void add(int pos, int num) {
        return add(pos, num, 0, 0, size/2-1);
    }

    void add(int pos, int num, int i, int left, int right) {
        if (left == right) {
            table[i] += num;
            return;
        }
        auto mid = (left + right) / 2;
        if (pos <= mid)
            add(pos, num, i*2+1, left, mid);
        else
            add(pos, num, i*2+2, mid+1, right);
        table[i] = max(table[i*2+1], table[i*2+2]);
    }

    int sum(int pl, int pr) {
        return sum(pl, pr, 0, 0, size/2-1);
    }

    int sum(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return 0;
        else if (pl <= left && right <= pr)
            return table[i];
        else
            return
                max(sum(pl, pr, i*2+1, left, (left+right)/2),
                    sum(pl, pr, i*2+2, (left+right)/2+1, right));
    }
}

CS Academy #43 D - Bad Triplet

https://csacademy.com/contest/round-43/task/bad-triplet/

問題概要

N頂点M辺の単純無向連結グラフが与えられる。各辺の長さはいずれも1である。このグラフからある3つの頂点A, B, Cを選んだとき、A-B間, A-C間, B-C間の最短距離が等しくなるようなA, B, Cの組合せが存在するか判定せよ。また存在するならば具体的にひとつ示せ。

N, M <= 10⁵

解法

まずグラフに次数3以上の頂点が存在する場合。この頂点をX, この頂点に繋がる点から適当に3つ選んだものをA, B, Cとおくと、A-B間に辺がある場合はA, B, X, A-C間に辺がある場合はA, C, X, B-C間に辺がある場合はB, C, Xを答えればよい（いずれも自明に最短距離１）。どの辺もない場合はA, B, Cが答えになる（Xを中心にして距離2）。

次に次数3以上の頂点がない場合。このときグラフは必ず1本のパスか1つのサイクルになる。パスになる場合答えは存在しない。サイクルになる場合、Nが3の倍数ならば等間隔に3つ点を取ればよく、そうでないならば答えは存在しない。

感想

天才か？？？？？？？？？？？？？？？？

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

int N, M;
vector<int> edges[101010];

int main() {
    cin >> N >> M;
    REP(i, M) {
        int a, b; cin >> a >> b;
        edges[a - 1].push_back(b - 1);
        edges[b - 1].push_back(a - 1);
    }


    REP(i, N) if (edges[i].size() >= 3) {
        int a = edges[i][0];
        int b = edges[i][1];
        int c = edges[i][2];
        
        if (find(edges[a].begin(), edges[a].end(), b) != edges[a].end()) {
            cout << i + 1 << " " << a + 1 << " " << b + 1 << endl;
            return 0;
        }

        if (find(edges[a].begin(), edges[a].end(), c) != edges[a].end()) {
            cout << i + 1 << " " << a + 1 << " " << c + 1 << endl;
            return 0;
        }

        if (find(edges[b].begin(), edges[b].end(), c) != edges[b].end()) {
            cout << i + 1 << " " << b + 1 << " " << c + 1 << endl;
            return 0;
        }

        cout << a + 1 << " " << b + 1 << " " << c + 1 << endl;
        return 0;
    }


    int d_min = 1 << 29;
    REP(i, N) d_min = min(d_min, (int)edges[i].size());

    if (d_min == 1 || N % 3) {
        cout << -1 << endl;
        return 0;
    }


    deque<pair<int, int>> q;
    vector<bool> used(N, 0);
    vector<int> dist(N, 1 << 29);
    q.push_back({0, 0});
    
    while (!q.empty()) {
        int n = q.front().first;
        int d = q.front().second;
        q.pop_front();
        if (used[n]) continue;
        
        dist[n] = d;
        used[n] = true;

        for (auto m: edges[n]) if (!used[m]) q.push_back({m, d + 1});
    }


    REP(i, N) if (dist[i] == N / 3) cout << i + 1 << " ";
    cout << 1 << endl;
}

AtCoder Grand Contest 009 C - Division into Two

http://agc009.contest.atcoder.jp/tasks/agc009_c

問題概要

昇順ソート済みのN要素の数列Sが与えられる。この数列を2つの集合X, Yに分割する。ただしX, Yは以下の条件を満たしていなければならない。

• Xに含まれるどの相異なる2要素も差の絶対値がA以上
• Yに含まれるどの相異なる2要素も差の絶対値がB以上

条件を満たすような分割の仕方が何通りあるか求めよ。

1 <= N <= 10⁵

解法

DPの計算量を落としていく系の問題。まず分割を「Sの要素を小さい順にX, Yどちらかに追加していく操作」と言い換えると、S[i]をX, Yに入れられるかどうかはX, Yそれぞれに最後に入れた要素だけに依存するため、以下のようなdpが立つ。

dp(i, x, y): S[i]を追加したときにXの最後の要素がS[x]でYの最後の要素がS[y]であるような分割の総数

このdpはO(N³)かかり、全然間に合わない。ここでx, yのうちどちらかは必ず直前に入れた要素になっていることを考えると、x, yのうちどちらかは必ず直前の数になっているはずである。つまり実質ありうるのはdp(i, i, y), dp(i, x, i)の2パターンしかない。ゆえに次元をひとつ落として以下のようなdpが可能になる。

dp(i, isX, j): S[i]を追加したとき、S[i]を入れた箱がX（もしくはY）であり、S[i]を入れなかった方の集合の最後の要素がS[j]であるような分割の総数

これで状態数が削減され、N×N×N のdpが N×2×N に落ちた。すなわちO(N²)である。しかしこれでもまだ時間が足りない。状態数はこれ以上落ちそうにないので、今度は遷移の方を工夫する。状態を（Xの最後の要素, Yの最後の要素）のように表すことにすると遷移は以下のようになる。

• ① (S[i-1], S[j]) -> (S[i], S[j]) ※ S[i] - S[i-1] >= Aのときだけ可
• ② (S[i-1], S[j]) -> (S[i-1], S[i]) ※ S[i] - S[j] >= Aのときだけ可
• ③ (S[j], S[i-1]) -> (S[i], S[i-1]) ※ S[i] - S[j] >= Bのときだけ可
• ④ (S[j], S[i-1]) -> (S[j], S[i]) ※ S[i] - S[i-1] >= Bのときだけ可

これらを上のdpの形で表すと

• ① dp(i, X, j) += dp(i-1, X, j) if S[i] - S[i-1] >= A
• ② dp(i, Y, i-1) += dp(i-1, X, j) if S[i] - S[j] >= A
• ③ dp(i, X, i-1) += dp(i-1, Y, j) if S[i] - S[j] >= B
• ④ dp(i, Y, j) += dp(i-1, Y, j) if S[i] - S[i-1] >= B

②, ③の形はつまり S[i] - S[j] >= A かつ j <= i - 2 であるようなすべてのjについてdp(i-1, X, j)を加算する、ということである。①, ④はj→jという遷移なので加算というよりはS[i]-S[i-1]である限りdp(j)の値が保存されるが、そうでなくなった瞬間そこの値が0になる、ということである（定性的に言うと、S[i-1]がXに入っていてS[i]-S[i-1] < A なら、 S[i]をXに入れることはできないので、S[j]が入ってる方に入れるしかなく、S[j]が最後の要素であるということがありえなくなってしまうということ）。

以上より実はdpの遷移においてjの値を個別に見ていく必要はなく、「あるjまでのdp(j)の合計をとる」「あるj以下のdp(j)をまとめて0にする」という操作だけが必要であることがわかる。このような操作を高速に行う方法はいろいろあると思うが、自分は以下のような実装を行った。

• セグメント木を2本用意する。それぞれが上のdpでいうXかYかの部分に対応
• それぞれのセグ木に対して「どこまでのjがゼロクリアされたか」を覚えておく変数を用意
• あとは上のdpの通りに計算

これでO(NlogN)になる。セグ木でやってるところをがんばってなんとかするとO(N)にもなるらしい。

感想

何とか解けたが時間かかりまくった。このレベルを本番で通すのはまだまだ難しそう

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!long);
    auto N = s[0].to!int;
    auto A = s[1];
    auto B = s[2];
    auto S = N.iota.map!(_ => readln.chomp.to!long).array;
    S ~= - 10L ^^ 18 - 10;
    S.sort();

    auto st1 = new SegmentTree(N + 1);
    auto st2 = new SegmentTree(N + 1);
    st1.add(0, 1);
    st2.add(0, 1);
    int lb1 = 0;
    int lb2 = 0;

    foreach (i; 2..N+1) {
        int j = S.assumeSorted.lowerBound(S[i] - A + 1).length.to!int - 1;
        int k = S.assumeSorted.lowerBound(S[i] - B + 1).length.to!int - 1;
        st2.add(i - 1, st1.sum(lb1, min(j, i - 2)));
        st1.add(i - 1, st2.sum(lb2, min(k, i - 2)));
        if (S[i] - S[i - 1] < A) lb2 = i - 1;
        if (S[i] - S[i - 1] < B) lb1 = i - 1;
    }

    writeln( (st1.sum(lb1, N + 1) + st2.sum(lb2, N + 1)) % MOD );
}

class SegmentTree {
    long[] table;
    int size;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new long[](size);
    }

    void add(int pos, long num) {
        return add(pos, num, 0, 0, size/2-1);
    }

    void add(int pos, long num, int i, int left, int right) {
        (table[i] += num) %= MOD;
        if (left == right)
            return;
        auto mid = (left + right) / 2;
        if (pos <= mid)
            add(pos, num, i*2+1, left, mid);
        else
            add(pos, num, i*2+2, mid+1, right);
    }

    long sum(int pl, int pr) {
        if (pl > pr) return 0;
        return sum(pl, pr, 0, 0, size/2-1);
    }

    long sum(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return 0;
        else if (pl <= left && right <= pr)
            return table[i];
        else
            return
                (sum(pl, pr, i*2+1, left, (left+right)/2) +
                 sum(pl, pr, i*2+2, (left+right)/2+1, right)) % MOD;
    }
}

AtCoder Grand Contest 006 D - Median Pyramid Hard

http://agc006.contest.atcoder.jp/tasks/agc006_d

問題概要

N段のピラミッドがあり、i段目は(2i-1)個のブロックからなる。最下段の(2N-1)個のブロックには(1, 2, …, 2N-1)を並べ替えた数字がそれぞれ書き込まれている。最下段以外のi段目のブロックのj番目の数字は、(i+1)段目のj番目, (j+1)番目, (j+2)番目のブロックの中央値となる。いま最下段に書き込まれた数字の列が与えられるので、最上段の1個のブロックに書き込まれることになる数を答えよ。

解法

2分探索。中では以下のような計算を回す。

数xをひとつ定め、最下段のすべての数字を

• x以上ならば1
• x未満ならば0

と書き換える。この0/1数列で元と同様の操作を行った結果として最上段が1になるならば答えはx以上の範囲にあり、0になるならば答えはx未満の範囲にあることになる。これで2分探索の範囲を絞っていくことができる。そしてこの判定は以下のように行うことで十分高速にできる。

• 最下段の真ん中3要素が 111, 110, 011 のとき → 最上段は1になる
• 最下段の真ん中3要素が 000, 001, 100 のとき → 最上段は0になる
• 最下段の真ん中3要素が 101, 010 のとき → 真ん中から横に見ていって、途中で同じ数が連続した場合にはその数が最上段になる。仮にそのような数がなければ（＝数列が010101…の繰り返しの場合）、ひとつ上の段に行くたび真ん中の数が反転することになる。

2分探索の中ではO(N)かかるので全体でO(NlogN)になって十分高速に求まる。

感想

この問題すごすぎないですか？リアルタイムで参加してて解説読んでめちゃくちゃ感動した記憶があります

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto N = readln.chomp.to!int;
    auto M = 2 * N - 1;
    auto A = readln.split.map!(to!int).array;
 
    int hi = M + 1;
    int lo = 0;
    while (hi - lo > 1) {
        int mid = (hi + lo) / 2;
        auto B = A.map!(a => a >= mid).array;
        int a = B[N-2], b = B[N-1], c = B[N];
        if ((a & b) || (b & c)) {
            lo = mid;
        } else if ((!a & !b) || (!b & !c)) {
            hi = mid;
        } else {
            bool ok = false;
            for (int l = N - 3, r = N + 1; l >= 0; l--, r++) {
                if (B[l] == B[l+1]) {
                    if (B[l]) lo = mid;
                    else hi = mid;
                    ok = true;
                    break;
                } else if (B[r] == B[r-1]) {
                    if (B[r]) lo = mid;
                    else hi = mid;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                bool hoge = B[N-1];
                if (M / 2 % 2) hoge ^= 1;
                if (hoge) lo = mid;
                else hi = mid;
            }
        }
    }
 
    lo.writeln;
}