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

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(N2)の計算量がかかって間に合わない。

そこで、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;
    }
}

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

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

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

なので、この問題では最短経路木を列挙すればいいことがわかる。根でない頂点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;
}