A. Fair | Codeforces Round #485 (Div. 1)

各商品をスタート地点として見てBFSっぽいことをする。はじめにキューへすべての始点入れておくだけ。

int N, M, K, S;

vi G[100005];
int dis[100005][102];
vi pos[102];

void bfs(int kind) {
    queue<pii> Q;
    each(p, pos[kind]) {
        Q.push({ p,0 });
        dis[p][kind] = 0;
    }
    while (sz(Q)) {
        int u, d;
        tie(u, d) = Q.front();
        Q.pop();
        each(v, G[u]) {
            if (dis[v][kind] == -1) {
                dis[v][kind] = d + 1;
                Q.push({ v, d + 1 });
            }
        }
    }
}

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

    MEM(dis, -1);
    cin >> N >> M >> K >> S;
    rep(a, N) {
        int kind;
        cin >> kind;
        pos[--kind].push_back(a);
    }
    rep(a, M) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    rep(a, K) {
        bfs(a);
    }
    rep(a, N) {
        sort(dis[a], dis[a] + K);
        int re = accumulate(dis[a], dis[a] + S, 0);
        cout << re << ' ';
    }
    cout << endl;
}
広告を非表示にする

B. Petr and Permutations | Codeforces Round #485 (Div. 1)

転倒数の偶奇は操作回数のそれと等しい。

 l, r \in \mathbb{N}, 1 \leq  l \lt r \leq Nとおく。 l番目の要素とr番目の要素を交換したとする。 l番目とr番目の間にz個の要素があるとする。
また、そのうち、もとのl番目より大きい要素をgL個, 小さい要素をlL(=z-gL)個とする。 まずl番目と間z個の関係だけで転倒数の増減を見ると
gL - lL = gL - (z-gL) = 2gL-z
だけ転倒数が増減する。
同様にr番目より大きい要素をgR個, 小さい要素をlR(=z-gR)個とすると、r番目と間の要素で
lR - gR = (z-gR)-gR = z-2gR
だけ増減する。 更に、l番目とr番目の関係だけ見ると転倒数が+-1だけ増減するので全体で
(2gL-z)+(z-2gR)+-1=2(gL-gR)+-1
だけ転倒数が増減することがわかる。よって、1回の操作での転倒数の増減は常に奇数

long long inversionNumber(const vector<int> &a) {
    long long res = 0;
    int n = (int)a.size();
    BinaryIndexedTree<long long> bit(n + 1);
    for (int x : a) {
        res += bit.sum(x + 1, n + 1);
        bit.add(x, 1);
    }
    return res;
}

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

    int N;
    cin >> N;
    vi A(N);
    each(a, A)cin >> a, --a;
    ll inv = inversionNumber(A);
    string re = "Um_nik";
    if (3 * N % 2 == inv % 2)re = "Petr";
    cout << re << endl;
}
広告を非表示にする

D: Xor Sum 2 - AtCoder Regular Contest 098

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

x, y, z \in \mathbb{Z}_+とする。 まずx\oplus y \leq x+yが成り立つ。更に「x \lt y ならば x\oplus z \lt y+z」も成り立つ。

部分文字列の左端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)

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

// 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

構成のベースは以下の2通り。 f:id:parukii:20180522141301j:plain 適切な最大の高さ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;
}
広告を非表示にする