D: Xor Sum 2 - AtCoder Regular Contest 098

排他的論理和が総和以下っぽい。詳しく説明する。

とする。 まずが成り立つ。更にも成り立つ。

部分文字列の左端lを固定してみる。このときr=lならば明らかに条件を満たす。

A[l]⊕A[l+1]⊕...⊕A[r] < A[l]+A[l+1]+...+A[r]

が成り立つと仮定する。このとき、先のxorの性質により

A[l]⊕A[l+1]⊕...⊕A[r]⊕A[r+1] < A[l]+A[l+1]+...+A[r]+A[r+1]

が成り立つ。 よって右端をいくら伸ばしても常に総和のほうが大きい。 つまりl<=r<=Nについて順に

等しい、等しい、等しい、等しい、総和のほうが大きい、総和のほうが大きい

のように等しい場合は左側に、値が異なる場合は右側に寄るので、値が等しくなる場合を二分探索する。

実行時間はO(Nlog(N))

int N;
cin >> N;
vector<ll> S(N + 1), T(N + 1);
rep(a, N) {
    int b;
    cin >> b;
    S[a + 1] = S[a] ^ b;
    T[a + 1] = T[a] + b;
}
ll re = 0;
rep(l, N) {
    int ok = l + 1, ng = N + 1;
    while (ng - ok > 1) {
        int r = (ok + ng) / 2;
        ll s = S[r] ^ S[l];
        ll t = T[r] - T[l];
        (s == t ? ok : ng) = r;
    }
    re += ok - l;
}
cout << re << endl;

E: Range Minimum Queries - AtCoder Regular Contest 098

取り出したQ個の要素の最小値miについてmi>=A[i]が成り立つとする。

このとき、Aのmi未満の要素は使えないので*の記号で表すと

{A[0], A[1]}, *, {A[3]} , *, *, {A[6], A[7], A[8]}, *, {A[10]}

のように*でAの要素がいくつかのグループに分けられる。このグループの中で K個以上要素を含むものから小さい要素を貪欲に取っていけば、最小値と最大値がともに求まる。

const int INF = 1 << 30;
int N, K, Q;
cin >> N >> K >> Q;
vi A(N);
each(a, A)cin >> a;
priority_queue<int, vector<int>, greater<int> > pq;
int re = INF;
each(mi, A) {
    vi B;
    rep(b, N+1) {
        if (b<N && A[b] >= mi) {
            B.push_back(A[b]);
        } else {
            if (sz(B) >= K) {
                sort(all(B));
                for (int c = 0; c + K <= sz(B); ++c) {
                    pq.push(B[c]);
                }
            }
            B.clear();
        }
    }
    if (sz(pq) >= Q) {
        int ma = -1;
        rep(c, Q) {
            ma = pq.top();
            pq.pop();
        }
        smin(re, ma - mi);
    }
    while (sz(pq)) pq.pop();
}
cout << re << endl;

D: Dice Room | JAG Asia 2010 (AOJ 2245)

出入り口に使う面の組、行の組（列の組）ごとに操作回数を考える。具体的には頭の中でサイコロを回転させつつ展開図に操作回数や行または列の対応を書き込んでいく。すると上のような図を得る。あとは最小値を計算するだけ。

// faceA, faceB, rowA, rowB, cost
int ROW_MAGIC[6][5] = {
{0,2,2,2,0},
{0,2,0,0,2},
{1,3,0,0,3},
{1,3,2,2,3},
{4,5,0,2,1},
{4,5,2,0,1}
};
// faceA, faceB, colA, colB, cost
int COL_MAGIC[6][5] = {
{0,2,0,2,1},
{0,2,2,0,1},
{1,3,0,2,2},
{1,3,2,0,2},
{4,5,0,0,2},
{4,5,2,2,2}
};

int main() {
    string S[6][3];
    const char E = '*';
    while (1) {
        rep(a, 6)rep(r, 3) {
            cin >> S[a][r];
            if (S[a][r] == "#")return 0;
        }
        int re = 9;
        rep(a,6){
            int fa, fb, ra, rb, d, oka=0,okb=0;
            int *p = ROW_MAGIC[a];
            fa = p[0], fb = p[1], ra = p[2], rb = p[3], d = p[4];
            rep(c, 3) {
                if (S[fa][ra][c] == E)oka = 1;
                if (S[fb][rb][c] == E)okb = 1;
            }
            if (oka&&okb)smin(re, d);
        }
        rep(a, 6) {
            int fa, fb, ca, cb, d, oka = 0, okb = 0;
            int *p = COL_MAGIC[a];
            fa = p[0], fb = p[1], ca = p[2], cb = p[3], d = p[4];
            rep(r, 3) {
                if (S[fa][r][ca] == E)oka = 1;
                if (S[fb][r][cb] == E)okb = 1;
            }
            if (oka&&okb)smin(re, d);
        }
        cout << re << endl;
    }
}

E. Pencils and Boxes | Educational Codeforces Round 44

int N, K, D;
cin >> N >> K >> D;
vi A(N);
// とりあえずソートしておく
rep(a, N)cin >> A[a];
sort(all(A));
vi in(N+1), out(N+1);
// 小さい方から0個をすべて使って箱詰めできている
in[0] = 1; out[0] = 1;
ll cur = 0;
rep(a, N) {
    cur += in[a];
    // 小さい方からa個すべて使って箱詰めできている
    if (cur > 0) {
        // 少なくともK個使わなければならない。
        // より大きな鉛筆と一緒に詰めるために
        // いくつかの鉛筆を入れなくて良い。
        // その場合、差がD以下に収まりやすいように、小さいものは
        // すべてまとめたほうがいい。(小さい方から少なくともK個)
        int L = a + K;
        // 差がDを超えない範囲ですべて使える
        int R = lower_bound(all(A), A[a] + D + 1) - A.begin();
        // 小さい方から、L<=b<=R個使って構成できる
        if (L <= R) {
            in[L]++;
            out[R]++;
        }
    }
    cur -= out[a];
}
if (cur+in[N] > 0)cout << "YES" << endl;
else cout << "NO" << endl;

D. Sand Fortress | Educational Codeforces Round 44

構成のベースは以下の２通り。 適切な最大の高さxは二分探索で求める。この通りに構成したときに、余りが出る場合があるが、x以下のすべての高さが存在するので、余りをrとするとceil(r/x)個だけ同じ高さの横に挿入すればいい。

// Hが大きすぎても無意味なので適当な値で制限
const ll LIM = 3000000000ll;

ll N, H;
cin >> N >> H;

if (H > LIM || N < H*(H + 1) / 2) {
    H = LIM;
    ll L = 0, R = H + 1;
    while (R - L > 1) {
        ll mid = (L + R) / 2;
        ll use = mid * (mid + 1) / 2;
        if (use <= N)L = mid;
        else R = mid;
    }
    ll re = L + (N - L*(L + 1) / 2 + L - 1) / L;
    cout << re << endl;
} else {
    ll L = H, R = LIM + 1;
    while (R - L > 1) {
        ll mid = (L + R) / 2;
        ll use = mid * (mid + 1) / 2 + (H + mid - 1)*(mid - H) / 2;
        if (use <= N)L = mid;
        else R = mid;
    }
    ll use = L * (L + 1) / 2 + (H + L - 1)*(L - H) / 2;
    ll re = 2 * L - H + (N - use + L - 1) / L;
    cout << re << endl;
}

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つの頂点につぶしたようなグラフを考える。ただし、自己ループの辺は取り除く。このグラフは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;
}