C. Liebig's Barrels | Educational Codeforces Round 44

int N, K, L;
cin >> N >> K >> L;
int M = N*K;
vi A(M);
rep(a, M)cin >> A[a];
sort(A.rbegin(), A.rend());
// 必ずできる一番小さい樽の大きさで制限
ll lim = (ll)A.back() + L;
ll re = 0;
// 使ってない板の数、作った樽の数
int cnt = 0, taru = 0;
// 板の長さを降順に見ていく
// 大きい樽を貪欲に作っていく
each(a, A) {
    // 一番小さい樽との大きさの差がL以下
    // かつ板がaも合わせてK個ある
    if (a <= lim && cnt >= K - 1) {
        cnt -= K - 1;
        taru++;
        re += a;
    } else {
        // あとで使う板
        cnt++;
    }
}
if (taru < N)re = 0;
cout << re << endl;

夏合宿の朝は早い | JAG Domestic 2016

起こす人uから起こされる人vへ辺(u, v)を張るようなグラフを考える。このグラフは閉路があってややこしい。とりあえず強連結成分分解してみよう。各強連結成分において誰か一人でも起きれば、その強連結成分内において全員が必ず起きる。よって強連結成分S内の全員が起きる確率は、他の強連結成分の人たちから起こされることがなければ1-\sum _{v∈S}{p_v}である。更に、各強連結成分を1つの頂点につぶしたようなグラフを考える。ただし、自己ループの辺は取り除く。このグラフはDAGになっている。入次数が0の頂点は先程の数式のとおり。入次数が0の頂点の人々が全員起きた場合、このグラフはDAGになっているので、他の強連結成分の人々も全員起きることがわかる。よって、入次数が0の頂点の人々が起きる確率の積が解。

int N;
while (cin >> N, N) {
    vector<vi> G(N);
    vector<double> P(N);
    rep(a, N) {
        int m;
        cin >> P[a] >> m;
        rep(b, m) {
            int c;
            cin >> c;
            --c;
            G[a].push_back(c);
        }
    }
    TarjanSCC scc(G);
    vi indeg(N), cnt(N);
    vector<double> sleep(N, 1.0);
    rep(a, N) {
        cnt[scc[a]]++;
        sleep[scc[a]] *= P[a];
    }
    rep(a, N)each(b, G[a])if(scc[a]!=scc[b])indeg[scc[b]]++;
    double re = 1;
    rep(a, N)if (cnt[a] && !indeg[a]) {
        re *= 1 - sleep[a];
    }
    cout << re << endl;
}

yukicoder #690 : E869120 and Constructing Array 4

N=32とする。1<=v<w<=31としてを満たすすべての辺(v, w)の辺を貼ると1から2<=x<=31までの経路の和は2x-2通りである。これは経路数をf(x)と表すと f(x) = f(1) + f(2) +...+ f(x-2) + f(x-1) = (f(1)+f(2)+...+f(x-2)) + f(x-1) = f(x-1) + f(x-1) = 2f(x-1)であるため。よってKを2進数として各桁をみてk(>=0)ビット目が立っていたら頂点k+2から頂点Nに辺を張ればよい。

int K, N = 32;
cin >> K;
vector<pii> E;
for (int w = 2; w <= N - 1; w++)
    for (int v = 1; v < w; ++v)
        E.emplace_back(v, w);
rep(a, 30)if (K >> a & 1)E.emplace_back(a + 2, N);
cout << N << ' ' << sz(E) << endl;
each(e, E)cout << e.first << ' ' << e.second << endl;

yukicoder #689 : E869120 and Constructing Array 3

/**
2以外の素数はすべて奇数

x*x<=Kであるような最大のxを考える。
a+bが奇数であるような偶数aをx個と奇数bもx個使って
素数がx*x個作れる。
K' = K-x*x
としてK'に対しても同様に繰り返していけばいい。
以前に使った偶数、奇数に対しては素数を作らないように注意。
**/

// n以下の自然数が素数であるかどうか
vector<bool> sieveFlags(int n) {
    vector<bool> f(n + 1);
    for (int i = 3; i <= n; i += 2)f[i] = true;
    for (int i = 3; (long long)i*i <= n; i += 2) {
        if (f[i])for (int j = i * 3; j <= n; j += i)f[j] = false;
    }
    if (n >= 2)f[2] = true;
    return f;
}

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

    const int MA = 1000001;
    auto A = sieveFlags(MA+1000);
    int K;
    cin >> K;
    vi re, used(MA), B;
    for (int a = 2; K > 0; a += 2) { // 偶数
        bool ok = true;
        // 今まで使った奇数との和が素数にならないか
        each(b, B)if (A[a + b]) {
            ok = false;
            break;
        }
        if (!ok)continue;

        // x*x個素数を作る
        int x = 1;
        for (; (x+1)*(x+1) <= K; ++x);
        // まだ使っていない奇数でa+bが素数であるもの
        for (int b = 3; b < MA; b += 2)if (!used[b] && A[a + b]) {
            ok = true;
            // いままで使った偶数との和が素数にならないか
            for(int c=2;c<a;c+=2)if(A[b+c]){
                ok = false;
                break;
            }
            if (!ok)continue;

            rep(c, x) {
                re.push_back(a);
                re.push_back(b);
            }
            used[b] = true;
            // 使った奇数
            B.push_back(b);
            K -= x*x;
            break;
        }
    }
    cout << sz(re) << endl;
    rep(a, sz(re))cout << re[a] << (a != sz(re) - 1 ? ' ' : '\n');
}

C. Elevator | Codeforces Round #483 (Div. 1)

http://codeforces.com/blog/entry/59484?#comment-431237

これを見てそのとおりに書いた。

using P = array<int, 7>;
static bitset<2001> vis[10][10][10][10][10];

int N;
cin >> N;

vi A(N), B(N);
rep(a, N)cin >> A[a] >> B[a];

queue<P> Q;
Q.push({ 0,0,0,0,1,0,0 });

while (sz(Q)) {
    auto p = Q.front(); Q.pop();
    auto &v = vis[p[0]][p[1]][p[2]][p[3]][p[4]];
    if (v[p[5]])continue;
    int d = p[6]++, i = p[5], cur = p[4];
    v[p[5]] = 1;
    if (p[3] == 0 && i == N) {
        cout << d << endl;
        break;
    }
    if (i < N && A[i] == cur && p[0]==0) {
        auto np = p;
        np[0] = B[i];
        np[5]++;
        sort(np.begin(), np.begin() + 4);
        Q.push(np);
    }

    if (cur > 1) {
        p[4]--; Q.push(p); p[4]++;
    }
    if (cur < 9) {
        p[4]++; Q.push(p); p[4]--;
    }

    rep(a, 4) if (p[a] == cur) {
        p[a] = 0;
        sort(p.begin(), p.begin() + 4);
        Q.push(p);
        break;
    }
}

A. Finite or not? | Codeforces Round #483 (Div. 1)

ll p, q, b;
cin >> p >> q >> b;
ll g = gcd(p, q);
// とりあえず約分
q /= g;
// 分母をb^kの形にできればOK
// そのためには分母qをgcd(b, q)で割り続けて
// bと互いに素な素因数をもつかどうか判定する
string re = "Finite";
while (q > 1) {
    ll h = gcd(q, b);
    if (h == 1) {
        re = "Infinite";
        break;
    }
    // 1秒しかないのでgcdの呼び出し回数を減らす工夫
    // while(q%h==0)の部分を取り除くとTLE
    while(q%h==0)q /= h;
}
cout << re << endl;

B. XOR-pyramid | Codeforces Round #483 (Div. 1)

/**
実験すると各引数が二項係数と同じ個数だけxorに使われることがわかる。例えば
f(1, 2, 4, 8)
= (1)⊕(2⊕2⊕2)⊕(4⊕4⊕4)⊕(8)
であり、各引数はC(3, 0), C(3, 1), C(3, 2), C(3, 3)
回だけ使われている。
xorは同じ整数同士で打ち消し合うので二項係数の偶奇だけわかればいい。
**/

// C[a][b] % mod, a, b <= nを求める
vector<vector<int>> combinations(int n, int mod) {
    auto res = vector<vector<int>>(n + 1, vector<int>(n + 1));
    rep(i, n + 1) res[i][0] = 1;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j)
        res[i][j] = (res[i - 1][j - 1] + res[i - 1][j]) % mod;
    return res;
}

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

    int N;
    cin >> N;
    auto C = combinations(N, 2);

    vi A(N);
    rep(a, N)cin >> A[a];

    // X[l][r]:=f(A[l], A[l+1],..., A[r])
    vector<vi> X(N, vi(N));
    for (int a = 1; a <= N; ++a) { // 長さaの部分文字列
        vi Y;
        rep(b, a) {
            // 奇数だけ拾っていく
            if (C[a - 1][b])Y.push_back(b);
        }
        for (int l = 0; l + a <= N; ++l) {
            int r = l + a;
            int x = 0;
            each(y, Y) {
                // ここで10^9回程度計算する必要があるが2secで
                // なんとか間に合う
                x ^= A[l + y];
            }
            X[l][r - 1] = x;
        }
    }

    // l<=a, b<=rならばクエリ[l, r]に対して[a, b]の値も
    // 見る必要がある。DPで内側のセグメントを伸ばしていく
    for (int len = 1; len <= N; ++len) {
        for (int l = 0; l + len <= N; ++l) {
            int r = l + len - 1;
            if (l > 0)smax(X[l - 1][r], X[l][r]);
            if (r < N - 1)smax(X[l][r + 1], X[l][r]);
        }
    }

    int Q;
    cin >> Q;
    rep(q, Q) {
        int l, r;
        cin >> l >> r;
        cout << X[l - 1][r - 1] << endl;
    }
}