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

2018-07-10

E1. Median on Segments (Permutations Edition) | Codeforces Round #496 (Div. 3)

数列なので中央値mはちょうど1つだけある。mの位置に注目すると、条件を満たす部分文字列は、mから左へ0以上、右へ0以上の長さだけ伸ばしたものに限られる。

部分文字列がmの左側へl, 右側へrだけ伸ばしたものであるとする。また、m以外の値はmとの大小関係だけわかればよい。

q[i] = 1 (p[i] > mのとき)
q[i] = -1(p[i] < mのとき)

とおく。mの位置をtとおくと $f(a, b) = \sum_{i=a}^{b-1}q_i$ とおくと $0 \leq f(t-l, t) + f(t+1, t+1+r) \leq 1$ であれば条件を満たす。これは、部分文字列の左側と右側合わせて、

(mより大きい値の数) - (mより小さい値の数) = 0 または 1

ということ。

少し変形して $- f(t-l, t) \leq f(t+1, t+1+r) \leq 1 - f(t-l, t)$ と得る。よって事前にf(t +1, t+1+r)をrの総当たりで固定して数えておく。あとはf(t-l, t)も総当たりして、各lについて条件を満たす $f(t+1, t+1+r)$ を数えればいい。

map<int, int> L, R;
    
int N, M;
cin >> N >> M;
vi A(N);
int p = -1;
rep(i, N) {
    cin >> A[i];
    if (A[i] == M)p = i;
}

L[0] = 1;
R[0] = 1;

int x = 0;
for (int i = p - 1; i >= 0; --i) {
    if (A[i] > M)x++;
    else if (A[i] < M)x--;
    L[x] += 1;
}
x = 0;
for (int i = p + 1; i < N; ++i) {
    if (A[i] > M)x++;
    else if (A[i] < M)x--;
    R[x] += 1;
}

ll re = 0;
each(l, L) {
    // l + r = 0
    if (R.count(-l.first)) {
        re += (ll)l.second * R[-l.first];
    }
    // l + r = 1
    if (R.count(1 - l.first)) {
        re += (ll)l.second * R[1 - l.first];
    }
}
cout << re << endl;

2018-07-10

D. Polycarp and Div 3 | Codeforces Round #496 (Div. 3)

ある非負整数が3の倍数かどうかは、各桁の値の和が3の倍数かどうかを調べればいい。なので

dp[i][j] := 「もとの数字の上位i桁まで確定して、今作っている数の桁の和を3で割ったあまりがjであるときの最大の仕切りの数」

のようなDPを解く。

int dp[200005][3];

int main() {
    MEM(dp, -1);
    dp[0][0] = 0;

    string S;
    cin >> S;
    int N = sz(S);

    rep(i, N) {
        int a = S[i] - '0';
        rep(j, 3) if(dp[i][j]!=-1){
            smax(dp[i + 1][(j + a) % 3], dp[i][j] + ((j+a)%3==0));
            smax(dp[i + 1][a % 3], dp[i][j] + (a % 3 == 0));
        }
    }
    int re = -1;
    rep(j, 3)smax(re, dp[N][j]);
    cout << re << endl;
}

2018-07-06

B. Sonya and Exhibition | Codeforces Round #495 (Div. 2)

一人しかいない場合を考えてみる。その人が見る花壇の長さをa, その花壇に含まれるバラの数をx, ユリの数をyとおく。 x+y=aの条件でxyを最大にしたい。 $xy = x(a-x) = -x^{2} + ax = -(x - \frac{a}{2})^{2} + a^{2}/4$ を得る。よってaが偶数の時 $x = \frac{a}{2}$ で最大。 aが奇数のとき $x = \frac{a\pm 1}{2}$ で最大。簡単のため $x \leq y$ とすると、x, yの値は $x = \lfloor a/2 \rfloor , y = \lceil a/2 \rceil$ となる。要するに、バラとユリをできるだけ均等な数にするのが最適。

単純な構成。バラとユリを交互に置くことで、この条件を一人だけでなくすべての人が満たすことができる。