No.727 仲介人moko - yukicoder

解は Π_{0<=i<N}{H(i*2+1, 2)(N-i)2} / N!

ただし、Πは総乗、H(n, r) = C(n+r-1, r) とする。

これは以下のように得る。残った売り手買い手から1人ずつ選んでペアを作り、既存の順番に挿入するということを繰り返すことを考える。 既存の順番がi個のペアをすでに作っているとする。この時、売り手、買い手の選び方が(N-i)2通り。この2人をどこに挿入するか。既存の列は2i人を含み、その間と端に重複を許して2人を挿入するのでH(2i+1, 2)通り。 あとは挿入順を無視するためにN!で割る。

namespace comb {
    const int N = 2000006;
    mint fact[N];
    mint rev[N];

    void init() {
        fact[0] = 1;
        for (int i = 1; i < N; ++i)fact[i] = fact[i - 1] * i;
        for (int i = 0; i < N; ++i)rev[i] = fact[i].inverse();
    }

    mint C(int n, int r) {
        if (n < r)return 0;
        return fact[n] * rev[r] * rev[n - r];
    }

    mint H(int n, int r) {
        return C(n + r - 1, r);
    }

    mint P(int n, int r) {
        assert(n >= r);
        return fact[n] * rev[n - r];
    }

    mint catalan(int n) {
        return fact[2 * n] * rev[n + 1] * rev[n];
    }
}

void solve() {
    comb::init();

    int N;
    cin >> N;
    mint re = comb::rev[N];
    rep(i, N) re *= comb::H(2 * i + 1, 2) * (N - i)*(N - i);
    cout << re << endl;
}

No.728 ギブ and テイク - yukicoder

i<jとする。 (i, j)が満たしたい条件は A[i]+R[i]>=A[j]かつA[i]>=A[j]-L[j]

jをループで固定する。jを昇順に見ていくならば A[i]+R[i]>=A[j]を満たすiはjが増加するごとに条件がきつくなる。 なのでi<jについて A[i]+R[i]の値を優先順位度付きキューで持っておいて、 A[i']+R[i']<A[j]となるような添え字i'を取り除いていく。

あとはA[i]>=A[j]-L[j]であるが、 取り除いたあとに残っているすべてのi<jとなる添え字iについて A[i]の値をBinary Indexed Treeで管理して条件を満たすものだけ数えればいい。

const int MAX_N = 300005;
int N, A[MAX_N], L[MAX_N], R[MAX_N];

void solve() {
    cin >> N;
    rep(i, N)cin >> A[i];
    rep(i, N)cin >> L[i] >> R[i];

    // a+r<=2*10^9<INT_MAX
    priority_queue<pii, vector<pii>, greater<pii>> Q;

    BinaryIndexedTree<int> bit(N);

    ll re = 0;
    rep(i, N) {
        while (!Q.empty()) {
            auto p = Q.top();
            if (p.first >= A[i]) {
                break;
            } else {
                bit.add(p.second, -1);
                Q.pop();
            }
        }

        int p = lower_bound(A, A + N, A[i] - L[i]) - A;
        re += bit.sum(p, i);

        bit.add(i, 1);
        Q.push(mp(A[i] + R[i], i));
    }

    cout << re << endl;
}

D: Median of Medians - AtCoder Regular Contest 101 | AtCoder

中央値がxの場合=>中央値がx以上の場合

f(x) := 「x以上の値が中央値となる連続部分列の個数」とする。 ここで部分列がH(N, 2)個あるので、そのちょうど真ん中になるのが中央値。 つまり f(x) >= ceil(H(N, 2)/2) を満たす最大のxが解。fは単調増加なので二分探索が使える。

x以上の値が中央値となる連続部分列を数える

二分探索で条件を固定することで、入力を単純にとらえられる。 x以上の値とx未満の値かどうかだけをみる。前者が半数以上となるような 連続部分列は中央値がx以上である。 前者を+1, 後者を-1とすると、連続部分列の和が0以上ならば、中央値がx以上となるはず。 この数列をCとする。 とりあえず累積和を求めておく S[i] = Σ_{0<=j<=i}C[j]とすると [l, r)の部分和は S[r]-S[l]であり、中央値の条件は S[r]-S[l]>=0つまり S[r]>=S[l] よって、rを小さいほうから見ていって、Binary Indexed TreeなどでS[l]を数えていけばいい。

const int MAX_N = 100005;
int N, A[MAX_N], B[MAX_N];

// sm(C[i]), sorted
int S[MAX_N], T[MAX_N];

// 和のインデックス(BITで使う)
int g(int y) {
    return lower_bound(T, T + N + 1, y) - T;
};

ll f(int x) {
    // S[r]-S[l]>=0
    // を満たすようなS[l]の数
    BinaryIndexedTree<int> bit(N + 1);
    int b = B[x];

    rep(i, N) {
        int c = A[i] >= b ? 1 : -1;
        T[i + 1] = S[i + 1] = S[i] + c;
    }

    sort(T, T + N + 1);

    ll cnt = 0;
    bit.add(g(0), 1);
    rep(i, N) {
        int j = g(S[i + 1]);
        cnt += bit.sum(0, j + 1);
        bit.add(j, 1);
    }

    return cnt;
}

void solve() {
    cin >> N;
    rep(i, N) {
        cin >> A[i];
        B[i] = A[i];
    }

    sort(B, B + N);
    int M = unique(B, B + N) - B;

    // ceil(H(N,2)/2)
    // = ceil(N*(N+1)/4)
    // オーバーフロー注意!!
    ll need = (N*(N + 1ll) + 3) / 4;

    int ok = 0, ng = M;
    while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        if (f(mid) >= need) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    cout << B[ok] << endl;
}

E. Hash Swapping | soundhound2018-summer-final-open

方針 O(Qsqrt(N))で間に合いそうなので平方分割を試す

クエリは[l, r)で0-indexedとする。

f(x, i) = 106i ord(S[x][i])(0<=i<N) とおくと Σ_{l<=i<r}f(x, i) / (106l) が解。

平方分割の工夫 g(x, k) = Σ_{kR<=i<=(k+1)R}f(x, i) とおく。 とりあえず[l, r)に含まれるすべての[kR, (k+1)R)について swap(g(x, k), g(y, k)) はわかる。 このとき、f(x, i)、f(y, i)の更新をどうしたらよいか。 愚直にf(x, i)とf(y, i)を交換すると1クエリにO(N)かかってしまう。 そこでR = ceil(sqrt(N))として f'(x, floor(i/R), i mod R) = f(x, i) とする。 ここで vector F[x][R];として F[x][floor(i/R)][i mod R] = f'(x, floow(i/R), i mod R) のようにgを表せば swap(F[x][k], F[y][k])をO(sqrt(N))回繰り返せば済む。

次に[kR, (k+1)R)に収まらないインデックスiについて考える。 この添字の個数はO(sqrt(N))個。 その一通りについて f(x, i)とf(y, i)の値を交換する。(実際には多次元配列Gを使う) その分g(x, floor(i/R))とg(x, floor(i/R))へ足したり引いたりする。O(1)

よって全体でO(Qsqrt(N))

const int MA = 200005, R = 450;
int N, M, ord[20][MA], Q;

mint smo[20][R];
vector<mint> va[20][R];
mint& f(int x, int i) {
    RT va[x][i / R][i%R];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N >> M;
    rep(i, M) {
        rep(j, R) {
            va[i][j].reserve(R);
            va[i][j].resize(R);
        }

        string s; cin >> s;
        mint pw = 1;
        rep(j, N) {
            ord[i][j] = s[j] - 'a' + 1;
            f(i, j) = pw * ord[i][j];
            smo[i][j / R] += f(i, j);
            pw *= 1000000;
        }
    }

    cin >> Q;
    FOR(t, 1, Q + 1) {
        int typ, x, y, l, r;
        cin >> typ >> x >> y >> l >> r;
        --x; --y; --l;
        if (typ==1) {
            while (l%R && l<r) {
                smo[x][l / R] += f(y, l) - f(x, l);
                smo[y][l / R] += f(x, l) - f(y, l);
                swap(f(x, l), f(y, l));
                l++;
            }
            while (r%R && l < r) {
                r--;
                smo[x][r / R] += f(y, r) - f(x, r);
                smo[y][r / R] += f(x, r) - f(y, r);
                swap(f(x, r), f(y, r));
            }

            for (int i = l; i < r; i += R) {
                int j = i / R;
                swap(smo[x][j], smo[y][j]);
                swap(va[x][j], va[y][j]);
            }
        } else {

            mint re = 0;
            mint pw = mint(1000000).pow(l);

            while (l%R && l<r) {
                re += f(x, l++);
            }
            while (r % R && l < r) {
                re += f(x, --r);
            }
            for (int i = l; i < r; i += R) {
                int j = i / R;
                re += smo[x][j];
            }
            re /= pw;
            cout << re << endl;

        }
    }
}

Manhattan Center (manhattan-center) | CSA

与えられた頂点のK個からなる部分集合について、最適なPの座標はx座標の中央値となる。 なので、Pの候補は与えられた頂点のx座標に限られる。

これらx座標を昇順に見ていく。(以下、x[k]<x[k+1]とする)

P=x[0]としてとりあえず近いK個を集合Lに入れておく。残った頂点は集合Rに入っているとする。

x[k] -> x[k+1]と変化したとする。x[k]のときの最適な構成Lから、x[k+1]のときの最適な構成L'を得たい。そのために、Lから遠くなった頂点を取り除きつつ、Rの近くなった頂点を突っ込んでいく。

(xl, yl) ∈ L, (xr, yr) ∈ R, xl<=x[k]<=xrとすると yl + (x[k] - xl) > yr + (xr-x[k]) ならば(xl, yl)の代わりに(xr, yr)を使ったほうがよい。 そのため、yl-xlが最大となるような(xl, yl)とyr+xrが最小となるような(xr, yr)を比較していく。

あとはマンハッタン距離の和を動的に求めたい。y座標については総和を足し引きするだけ。Pの座標によらないため。x座標については、Binary Indexed Treeで座標ごとに座標の和、その座標の頂点数を数えておけば簡単。

int N, K;
cin >> N >> K;

priority_queue<pii, vector<pii>, greater<pii> > R;
priority_queue<pii> L;

vector<int> xs;
vi X(N), Y(N);
rep(i, N) {
    int x, y;
    cin >> x >> y;
    R.push(mp(y + x, i));
    X[i] = x;
    Y[i] = y;
    xs.push_back(x);
}
sort(all(xs));
xs.erase(unique(all(xs)), xs.end());

auto id = [&](int x) {
    RT (int)(lower_bound(all(xs), x) - xs.begin());
};

BIT bit(sz(xs)), cnt(sz(xs));
ll sm = 0, re = LLONG_MAX;
auto add = [&](int k) {
    sm += Y[k];
    L.push(mp(Y[k] - X[k], k));
    cnt.add(id(X[k]), 1);
    bit.add(id(X[k]), X[k]);
};

while (sz(L) < K && sz(R)) {
    auto q = R.top(); R.pop();
    int k = q.second;
    add(k);
}
each(p, xs) {
    while (sz(L) && sz(R)) {
        auto l = L.top();
        auto r = R.top();
        if (l.first + p > r.first - p) {
            R.pop();
            if (X[r.second] < p) {
                continue;
            }
            L.pop();
            add(r.second);

            sm -= Y[l.second];
            cnt.add(id(X[l.second]), -1);
            bit.add(id(X[l.second]), -X[l.second]);
        } else {
            break;
        }
    }
    ll z = cnt.sum(id(p)) * p - bit.sum(id(p));
    ll w = bit.sum(id(p), sz(xs)) - cnt.sum(id(p), sz(xs))*p;

    smin(re, z + w + sm);
}
cout << re << endl;

No.715 集合と二人ゲーム | yukicoder

grundy数を出力して図にしてみる。 f:id:parukii:20180717130948p:plain 十分大きな整数について、そのgrundy数が34周期になっていることがわかる。

int dp[201];
int g(int n) {
    if (dp[n] != -1)RT dp[n];
    set<int> S;
    for (int i = 0; i < n; ++i) {
        int l = max(0, i - 1);
        int r = max(n - 2 - i, 0);
        S.insert(g(l) ^ g(r));
    }
    int re = 0;
    while (S.count(re))re++;;
    return dp[n] = re;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    MEM(dp, -1);
    rep(i, 88)g(i);

    int N;
    cin >> N;
    set<int> S;
    rep(i, N) {
        int a;
        cin >> a;
        S.insert(a);
    }
    S.insert((int)1e9 + 1);

    int sm = 0, cnt = 0, pre = -1;
    for (int x : S) {
        if (x - pre > 1) {
            int y = cnt >= 54 ? (cnt - 54) % 34 + 54 : cnt;
            sm^=dp[y];
            cnt = 1;
        } else {
            cnt++;
        }
        pre = x;
    }
    
    cout << (sm ? "First" : "Second") << endl;
}