2018-07-21

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;

2018-07-17

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

Grundy数

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;
}

2018-07-16

E. Intercity Travelling | Educational Codeforces #47

f:id:parukii:20180716161240j:plain

int n;
cin >> n;
vector<mint> pw(n + 1), a(n + 1);
pw[0] = 1;
rep(i, n) {
    pw[i + 1] = pw[i] * 2;
    int x; cin >> x;
    a[i + 1] = x;
}

mint re, b;
rep(i, n) {
    b = b * 2 + a[i];
    re += (b + a[i + 1])*pw[n - 1 - i];
}
cout << re << endl;

2018-07-16

F. Dominant Indices | Educational Codeforces #47

マージ木

再帰で解く。

とりあえず、d[x]は最大の深さの分まで求めればいい。それ以降は0が続くので。

頂点xのxを除くすべての子孫についてdが計算済みとして、d[x]を計算する。d[x]のすべての子供だけを見ればd[x]が求まる。つまり、すべての子供yについてd[x][i+1] += d[y][i], d[x][0] = 1とすればよい。これを愚直にやるとO(N²)の計算量がかかって間に合わない。

そこで、d[y][i]が最大になるような子供zについてd[z][i]に他のd[y][i]をマージしていき、d[x] = d[z]とする。大きい方から小さい方へのマージしていくことでO(NlogN)の計算量で済む。

計算量の説明。大きいグループへ小さいグループをマージする時、マージ後のグループの大きさは、元の小さいグループの大きさの2倍以上。よって、小さいグループのほうの各要素はO(logN)回のマージでNの大きさになる。よって全体でO(NlogN)の計算量になる。

d[x][i] = 0の部分の実装が楽そうなのでデックを使ったらMLEした。 dequeの実装は

c++ - What really is a deque in STL? - Stack Overflow

のようなのが一般的で

[C++] STLの型の使い分け

にあるように各メモリブロックのサイズは512バイトの実装だったりする。なので、グラフの問題でよく書く大量のvectorみたいな感じでdequeを大量に確保するとMLEしてしまう。つまり、今回の問題でいえば

deque<int> d[1000001];

みたいなのはだめ。代わりにd[x]はvectorに逆順に入れておく。

const int MA = 1000006;
vi G[MA], C[MA];
vector<vi> d;
int ans[MA], dominant[MA];

int f(int u, int p) {
    // leaf
    if (u != 1 && sz(G[u])==1) {
        d.push_back(vi{1});
        RT sz(d)-1;
    }

    int ma = 0, re = 0;
    each(v, G[u]) {
        if (v != p) {
            int id = f(v, u);
            if (sz(d[id]) > ma) {
                ma = sz(d[id]);
                re = id;
            }
            C[u].push_back(id);
        }
    }

    auto &a = d[re];
    int nd = sz(a);
    a.push_back(1);
    int &dom = ans[u];
    dom = dominant[re] + 1;
    ma = a[nd-dom];
    if (ma == 1)dom = 0;

    each(id, C[u]) {
        if (id != re) {
            auto &b = d[id];
            int nb = sz(b);
            rep(i, sz(b)) {
                a[nd-(i + 1)] += b[nb-1-i];
                if (a[nd-(i + 1)] > ma || (a[nd-(i + 1)] == ma && i + 1 < dom)) {
                    ma = a[nd-(i + 1)];
                    dom = i + 1;
                }
            }
        }
    }

    dominant[re] = dom;
    RT re;
}

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

    int n;
    cin >> n;
    if (n <= 2) {
        rep(i, n)cout << 0 << endl;
        RT 0;
    }
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    f(1, 0);
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }
}

2018-07-14

D. Pave the Parallelepiped | Codeforces Round #497 (Div. 2)

とりあえず最大の入力以下の自然数の約数を列挙しておく。入力中最大の自然数をMとして、M以下の各自然数について、その倍数を見ていく。調和数を考えると $O(Mlog_eM)$ の計算量とわかる。

各データセットについて、別々に処理する。 A, B, Cのうち、少なくともひとつの約数になっている自然数の集合をSとする。これは事前に列挙した約数から簡単に求まる。Sの要素xについて、f(x)を xがA,B,Cのうちどれの約数になっているかのフラグとする。f(x)の値を数える。( $g_{f(x)}+=1$ のような感じで)3個の整数の選び方を考える。それぞれ順番を区別しないで数えるので注意。3値の大小は考慮せずに、{f(a),f(b),f(c)}=｛p,q,r}とする。(多重集合。p<=q<=r)。p,q,rを総当たりで固定する。p,q,rがすべて異なるとき、 $g_{p}g_{q}g_{r}$ を数える。p=qかつq≠rのとき、フラグがp=qとなる自然数から2個、rとなる自然数から1個選ぶので、 $(g_{p}個から重複を許しての2個の選び方)*g_{r}$ だけ数える。p≠qかつq=rの場合も同様。p=q=rのとき、 $(g_p個から重複を許しての3個の選び方)$ を数える。なお、p,q,rがA,B,Cのすべての約数をカバーする必要があるので注意。そのためには、フラグp,q,rとA,B,Cの対応をすべて試せばよい。

vector<vector<int>> divisorsAll(int n) {
    vector<vector<int>> res(n + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            res[j].push_back(i);
        }
    }
    return res;
}

int two(int n) {
    return n*(n + 1) / 2;
}
int three(int n) {
    return n*(n + 1)*(n + 2) / 6;
}

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

    auto D = divisorsAll(100005);
    vi E(100005);
    each(d, D)sort(all(d));

    int di[200 * 3] = {};
    int A[3];
    rep(i, 3)A[i] = i;

    while (T--) {
        int S[3];
        int m = 0;

        vi X(8), Y(8);
        rep(i, 3) {
            cin >> S[i];
            int a = S[i];
            each(d, D[a]) {
                E[d] |= 1 << i;
                di[m++] = d;
            }
        }
        sort(di, di + m);
        m = unique(di, di + m) - di;
        
        rep(i, m)Y[E[di[i]]]++;
        int re = 0;

        rep(i, 8)FOR(j, i + 1, 8) {
            // {1,2}, {2,1}
            // i, j, j
            int ok = 0;
            do {
                if ((i >> A[0] & 1) && (i >> A[1] & 1) && (j >> A[2] & 1))ok |= 1;
                if ((i >> A[0] & 1) && (j >> A[1] & 1) && (j >> A[2] & 1))ok |= 2;
            } while (next_permutation(A, A + 3));
            if (ok & 1)re += two(Y[i]) * Y[j];
            if (ok & 2)re += Y[i] * two(Y[j]);
            FOR(k, j + 1, 8) {
                // {1, 1, 1}
                ok = 0;
                do {
                    if ((i >> A[0] & 1) && (j >> A[1] & 1) && (k >> A[2] & 1))ok |= 1;
                } while (next_permutation(A, A + 3));
                if (ok)re += Y[i] * Y[j] * Y[k];
            }
        }
        // {3}
        re += three(Y[7]);
        cout << re << endl;
        rep(i, m)E[di[i]] = 0;
    }
}

2018-07-10

F. Berland and the Shortest Paths | Codeforces Round #496 (Div. 3)

木 BFS 最短経路木

単一始点最短経路問題で、すべての頂点に最短で到達するのに必要な辺だけを選ぶと木になることが知られている(最短経路木)。

なので、この問題では最短経路木を列挙すればいいことがわかる。根でない頂点vに最短距離で到達した時、直前の頂点をuとする。d(x)を頂点xまでの最短距離とすると、d(u) + 1 = d(v)かつ辺(u, v)が存在するならば、どの辺(u, v)を使ってもよい。必要な分だけ別の辺を使えばいい。

int N, M, K;
vector<string> ans;
void f(int u, vector<vi> &cand, string &re, vi &U, vi &V) {
    if (u == N) {
        ans.push_back(re);
        return;
    }
    if (sz(cand[u])==0) {
        f(u + 1, cand, re, U, V);
    }
    each(e, cand[u]) {
        int v = U[u] ^ V[v] ^ u;
        re[e] = '1';
        f(u + 1, cand, re, U, V);
        re[e] = '0';
        if (sz(ans) == K)return;
    }
}

int main() {
    cin >> N >> M >> K;

    vector<vi> G(N);
    vi U(M), V(M);
    rep(i, M) {
        cin >> U[i] >> V[i];
        --U[i]; --V[i];
        G[U[i]].push_back(i);
        G[V[i]].push_back(i);
    }

    vi D(N, INT_MAX/2);
    D[0] = 0;
    queue<int> Q;
    Q.push(0);
    vector<vi> cand(N);
    vi vis(N);
    while (sz(Q)) {
        int u = Q.front();
        Q.pop();
        each(e, G[u]) {
            int v = u ^ U[e] ^ V[e];
            if (D[u] + 1 <= D[v]) {
                if (D[u] + 1 < D[v])Q.push(v);
                D[v] = D[u] + 1;
                cand[v].push_back(e);
            }
        }
    }

    string temp(M, '0');
    f(0, cand, temp, U, V);

    cout << sz(ans) << endl;
    each(re, ans)cout << re << endl;
}

2018-07-10

E2. Median on Segments (General Case Edition) | Codeforces Round #496 (Div. 3)

Binary Indexed Tree 数え上げ

f(x) を「中央値をxとする部分文字列の数」とする。f(m)が解。

$g(y) = \sum_{y \leq x}f(x)$ とおくと

$f(m) = g(m) - g(m+1)$ を得る。

あとは、g(y)を求めるだけ。g(y)の値は、中央値がy以上の部分文字列の数を表す。部分文字列の中央値がy以上である必要十分条件は

(y以上の値の数)>=(y未満の値の数)

とわかる。

よって

h(y, z) := 「部分文字列a[0, z)内での(y以上の値の数)-(y未満の値の数)」

とすれば、 h(y, r) - h(y, l) >= 0, l<rとなるような組(l, r)を数えればいいことがわかる。なので、BITなどを使えば簡単に求まる。

ll f(vi a, int b) {
    int n = sz(a);
    rep(i, n) {
        if (a[i] < b)a[i] = -1;
        else a[i] = 1;
    }
    ll re = 0;
    BIT bit(2*n+2);
    int s = 0;
    rep(i, n) {
        bit.add(n + s, 1);
        s += a[i];
        re += bit.sum(0, n + s);
    }
    return re;
}

int main() {
    int N, M;
    cin >> N >> M;
    vi A(N);
    rep(i, N)cin >> A[i];
    ll re = f(A, M) - f(A, M+1);
    cout << re << endl;
}