2018-04-23

E - Everything on It | AtCoder Regular Contest 096

包除原理

公式解説動画のとおりに実装。

ちなみに2^{2^k} mod p (pは素数)はフェルマーの小定理より 2^{2^k mod (p-1)} mod p で求まる。

vector<vi> dp;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
 
    int N, M;
    while (cin >> N >> M) {
        MOD = M;
        dp = vector<vi>(N + 1, vi(N + 1));
        dp[0][0] = 1;
 
        for (int a = 1; a <= N; ++a)for (int b = 0; b <= a; ++b) {
            sadd(dp[a][b], dp[a - 1][b]);
            if (b > 0) {
                sadd(dp[a][b], dp[a - 1][b - 1]);
                sadd(dp[a][b], mul(dp[a - 1][b], b));
            }
        }
 
        vi A(N + 1);
        rep(a, N + 1) {
            MOD = M - 1;
            int p = powm(2, N - a);
            MOD = M;
            int q = powm(2, p);
            rep(b, a + 1) {
                int r = powm(2, (ll)(N - a)*b);
                int s = mul(q, mul(dp[a][b], r));
                sadd(A[a], s);
            }
        }
 
        auto C = combinations(N, M);
 
        int re = 0;
        rep(a, N + 1) {
            int p = mul(C[N][a], A[a]);
            if (a % 2)p = mul(p, -1);
            sadd(re, p);
        }
        cout << re << endl;
    }
}

2018-04-11

E. Byteland, Berland and Disputed Cities | Educational Codeforces Round 42 (Rated for Div. 2)

とりあえず、頂点を座標の昇順に並べておく。以下のように構成できる。 f:id:parukii:20180411194319j:plain

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

    int n;
    cin >> n;
    vll b, r, p, xs;
    rep(i, n) {
        ll x;
        cin >> x;
        char c;
        cin >> c;
        if (c == 'B')b.push_back(x);
        if (c == 'R')r.push_back(x);
        if (c == 'P')p.push_back(x);
    }

    sort(all(b));
    sort(all(r));
    sort(all(p));

    ll ans = 0;

    if (sz(p) == 0) {
        ans += !sz(b) ? 0 : b.back() - b[0];
        ans += !sz(r) ? 0 : r.back() - r[0];
    } else {
        if (sz(b) && b[0] < p[0])ans += p[0] - b[0];
        if (sz(r) && r[0] < p[0])ans += p[0] - r[0];
        if (sz(b) && b.back() > p.back())ans += b.back() - p.back();
        if (sz(r) && r.back() > p.back())ans += r.back() - p.back();
        int bL = 0, bR = 0, rL = 0, rR = 0;
        rep(i, sz(p) - 1) {
            ll low = p[i], high = p[i + 1];
            while (bL < sz(b) && b[bL] <= low)bL++;
            while (rL < sz(r) && r[rL] <= low)rL++;
            while (bR < sz(b) && b[bR] < high)bR++;
            while (rR < sz(r) && r[rR] < high)rR++;
            int bN = bR - bL, rN = rR - rL;

            if (bN > 0 && rN > 0) {
                ll u = 3 * (high - low);
                ll v = 2 * (high - low);
                ll bM = max(b[bL] - low, high - b[bR - 1]);
                ll rM = max(r[rL] - low, high - r[rR - 1]);
                FOR(j, bL, bR - 1)smax(bM, b[j + 1] - b[j]);
                FOR(j, rL, rR - 1)smax(rM, r[j + 1] - r[j]);
                u -= bM + rM;
                ans += min(u, v);
            } else if (bN > 0) {
                ll bM = max(b[bL] - low, high - b[bR - 1]);
                FOR(j, bL, bR - 1)smax(bM, b[j + 1] - b[j]);
                ans += 2 * (high - low) - bM;
            } else if (rN > 0) {
                ll rM = max(r[rL] - low, high - r[rR - 1]);
                FOR(j, rL, rR - 1)smax(rM, r[j + 1] - r[j]);
                ans += 2 * (high - low) - rM;
            } else {
                ans += high - low;
            }
        }
    }

    cout << ans << endl;
}

2018-04-06

F. Mahmoud and Ehab and yet another xor task | Codeforces Round #473 (Div. 2)

エディトリアルの通り。j<iまで見てxorsumで作れる集合をSとする。a[i]∈Sのとき、x∈Sであればa[i]⊕∈SなのでSの元はそのままで、各元の構成の仕方が2倍になる。a[i]∉Sのとき、x∈Sならばa[i]⊕x∉Sなので、集合にa[i]⊕xを加えるだけ。|S|が2倍になる。

int main() {
    int N, Q;
    cin >> N >> Q;
    vi A(N);
    rep(i, N)cin >> A[i];

    set<int> S;
    S.insert(0);
    mint val = 1;

    vi L(Q), X(Q);
    vector<vi> qs(N);
    rep(i, Q) {
        cin >> L[i] >> X[i];
        qs[--L[i]].push_back(i);
    }

    vector<mint> ans(Q);
    rep(i, N) {
        if (S.count(A[i])) {
            val *= 2;
        } else {
            set<int> T = S;
            each(x, S)T.insert(x^A[i]);
            S = T;
        }
        each(j, qs[i]) {
            if (S.count(X[j]))ans[j] = val;
        }
    }

    each(a, ans)cout << a << endl;
}

2018-04-04

E. Mahmoud and Ehab and the xor-MST | Codeforces Round #473 (Div. 2)

XOR 桁DP

まず最上位ビットについて考えてみよう。最上位ビットが異なる頂点同士を結ぶと、ほかの全てのビットが異なる頂点同士を結ぶよりも高コストなので、できるだけ少なく済ませたい。そこで0b0???のグループと0b1???のグループに分けてそれぞれ木になっているとしよう。このとき、0b00...0と0b10...0を辺で結べばコストは最上位ビット1回分だけで済む。同様の問題を別れた部分木についても解く。つまり上位d-1桁が等しい値についてd桁目が異なる場合、d桁目で1本だけ辺を結べば済む。あとは、上位d-1桁が等しい値であるが、これは桁DPで数えていく。

dp[i][j] := i桁目まで見てj(0: n-1と一致, 1: n-1より小さい)ような上位i桁の数はいくつあるか

ll dp[51][2];

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

    ll n;
    cin >> n;
    n--;

    ll ans = 0;
    dp[0][0] = 1;
    rep(i, 50) {
        int k = 50 - 1 - i;
        int d = n >> k & 1;
        ll cost = 1ll << k;
        rep(les, 2) {
            ll x = dp[i][les];
            if (!x)continue;
            if (les) {
                ans += x * cost;
                dp[i + 1][1] += x * 2;
            } else {
                if (d == 1) {
                    ans += x * cost;
                    dp[i + 1][1] += x;
                }
                dp[i + 1][0] += x;
            }
        }
    }
    cout << ans << endl;
}

2018-04-04

D. Mahmoud and Ehab and another array construction task | Codeforces Round #473 (Div. 2)

素因数分解貪欲整数

辞書順最小にしたいので先頭からbの値を決めていく。とりあえず、aの要素を使える限り使っていく。例えば、入力例2は

a={10, 3, 7}
b={10, 3, 7}

b[i]をa[i]の要素として使えるかどうかを判定するには、あらかじめ十分大きな素数の集合を用意しておく。a[i]を素因数分解して、素数の集合にすべての素因数が含まれているならば可。その場合、その素数の集合から素因数分解で得られた素数を取り除く。

しかし、a[i] = b[i]とできない添字iがあるかもしれない。たとえば、

2 7 8
2 7 9
    *

のような場合である。この場合、a[i]より大きい整数を昇順に見ていく。素数でなくてもよいので注意。もし、残った素数の集合で素因数分解できるならば、その値は使える値として最小である。なお、a[i]<=10⁵より、最悪でも10⁵を超える最小の素数まで見ればb[i]を得られる。

このようにa[i]<b[i]となる添字iが存在した場合、残りのj>i, b[j]を構成する方法は簡単。残った素数のリストから小さい順に素数を並べていけばいい。

最後に必要な素数の集合の大きさだが、10⁵以下の素数は10⁴個未満であり、またn<=10⁵より、10⁵+10⁴個ほどの素数があればよい。これには1500000以下の素数を列挙すれば十分。

vector<int> sieve(int n) {
    vector<bool> f(n + 1);
    for (int i = 3; i <= n; i += 2) f[i] = 1;
    for (int i = 3; i <= sqrt(n); i += 2) if (f[i]) for (int j = i * 3; j <= n; j += i) f[j] = 0;
    vector<int> res;
    if (n >= 2)res.push_back(2);
    for (int i = 3; i <= n; i += 2) if (f[i]) res.push_back(i);
    return res;
}

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

    auto primes = sieve(1500000);

    set<int> P(all(primes));
    int N;
    cin >> N;
    vi A(N);
    rep(i, N)cin >> A[i];

    vi ps(100);
    int gr = 0;
    rep(i, N) {
        if (gr) {
            auto it = P.begin();
            cout << *it;
            P.erase(it);
        } else {
            auto factorize = [&](int a) {
                int m = 0;
                for (int j = 2; j*j <= a; ++j) {
                    if (a%j == 0) {
                        ps[m++] = j;
                        while (a%j == 0)a /= j;
                        if (!P.count(j)) return -1;
                    }
                }
                if (a > 1) {
                    ps[m++] = a;
                    if (!P.count(a))return -1;
                }
                return m;
            };

            int m = factorize(A[i]);

            if (m != -1) {
                cout << A[i];
                rep(j, m) P.erase(ps[j]);
            } else {
                gr = 1;
                int x;
                for (x = A[i] + 1;; ++x) {
                    m = factorize(x);
                    if (m != -1)break;
                }
                cout << x;
                rep(j, m)P.erase(ps[j]);
            }
        }
        cout << (i != N - 1 ? ' ' : '\n');
    }
}

2018-04-04

B. Mahmoud and Ehab and the message | Codeforces Round #473 (Div. 2)

int N, K, M;

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

    cin >> N >> K >> M;

    // 各単語の番号
    map<string, int> id;
    rep(i, N) {
        string s; cin >> s;
        id[s] = i;
    }

    // 各単語の送信コスト
    vi A(N);
    rep(i, N)cin >> A[i];

    // そのグループに属す単語で最小のコスト
    vi cost(K, INT_MAX);
    map<int, int> g;
    rep(i, K) {
        int x; cin >> x;
        rep(j, x) {
            int k;
            cin >> k;
            --k;
            // 番号kの単語はグループiに属す
            g[k] = i;
            smin(cost[i], A[k]);
        }
    }

    ll ans = 0;
    rep(i, M) {
        string s;
        cin >> s;
        // 単語sと同じグループに属す単語で最小のコストを使う
        ans += cost[g[id[s]]];
    }
    cout << ans << endl;
}

2018-04-04

A. Mahmoud and Ehab and the even-odd game | Codeforces Round #473 (Div. 2)

ゲーム

Nのパリティを見る。

(1) Nが偶数のとき

最初のターンでMahmoudがN個取ってMahmoudの勝ち。

(2) N >= 3 かつNが奇数のとき

最初のターンでMahmoudは2<=a<N個の偶数しか取れない。よってEhabのターンでN-a個は奇数であり、EhabがN-a個取って勝つ。

(3) Nが1のとき

最初のターンでMahmoudは何もできないので、Ehabの勝ち。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int n;
    cin >> n;
    cout << (n % 2 ? "Ehab" : "Mahmoud") << endl;
}