読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

Codeforces Round #350 (Div. 2) A ~ E

結果

f:id:pakapa104:20160506131236p:plain

pretest通したやつは全部通ってた。

今回は初めてCオープンしてみましたが、いい感じ。A, Bは落とさないように気を付けても結局落ちたりして費用対効果が薄いので…だったら高い得点を取れるうちにCを解いてしまった方がよさそうという考え。

レーティングはこんな感じ↓

f:id:pakapa104:20160506131641p:plain

早く濃い青になるぞ!

A. Holidays

間違えるのが怖いので全探索しました。

ちゃんと考えるなら、最小は月曜始まり、最大は土曜始まり。

    int N;
    cin >> N;
    int mi = 99999999;
    int ma = -1;
    rep(k, 7) {
        int cnt = 0;
        rep(i, N) {
            if ((i + k) % 7 <= 1) {
                cnt++;
            }
        }
        mi = min(mi, cnt);
        ma = max(ma, cnt);
    }

    cout << mi << " " << ma << endl;

B. Game of Robots

規則性のアレ。

1から順に引いていって、引けなくなったらそれが答えの添え字。

    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i, N) cin >> a[i];

    K--;
    int t = 1;
    while (K - t >= 0) {
        K -= t;
        t++;
    }

    cout << a[K] << endl;

C. Cinema

辞書順ソート。

(audio, subtitles)を出現回数の対に読み替えてpairでソートすればいいんだけど、なんか怖かったので本番はinf * (audioの出現回数) + (subの出現回数) という1次元のスコアでソートした。

あと↓のコードのvector a, 使ってないね。ごめんなさい。

    int N;
    cin >> N;
    vector<int> a(N);
    map<int, int> cnt;
    rep(i, N) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    int M;
    cin >> M;
    vector<int> b(M);
    rep(i, M) cin >> b[i];
    vector<int> c(M);
    rep(i, M) cin >> c[i];

    vector<P> li(M);
    rep(i, M) li[i] = P(10000000 * cnt[b[i]] + cnt[c[i]], i);

    sort(all(li));

    cout << li[M - 1].second + 1 << endl;

D1. Magic Powder - 1

愚直なシミュレーションが許されるので、魔法の粉を1ずつ割り振っていく。

何に割り振るかというと、クッキーを作れる枚数は bi / ai (切り捨て) の最小値なので、bi / ai が最小となるbiに粉を割り振ります。

    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    vector<int> b(N);
    rep(i, N) cin >> b[i];

    int mi;
    while (K >= 0) {
        mi = 99999999;
        int arg = -1;
        rep(i, N) {
            if (b[i] / a[i] < mi) {
                mi = b[i] / a[i];
                arg = i;
            }
        }

        if (K == 0) break;
        b[arg]++;
        K--;
    }

    cout << mi << endl;

D2. Magic Powder - 2

二分探索。

クッキーをm枚焼けるならばm枚以下は必ず焼くことができます。また、m枚焼けないならばm枚以上焼くことはできません。すなわちこの問題はmについて単調性を持ちます。

判定関数は、ai * m が材料iの必要な量なので、max(0, ai * m - bi) の総和 <= k であるかを判定すればよいです。(すなわち、材料の不足分を補えるだけの粉があるか、という意味です)

にぶたんの上限をうまく決めないとオーバーフローしそうだったのでPythonにしました。

def check(m):
    need = 0
    for ax, bx in zip(a, b):
        need += max(0, ax * m - bx)
    return need <= k

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

l = 0
r = 10 ** 10
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m
print(l)

E. Correct Bracket Sequence Editor

初めてアイデアらしきものを自力で思いつけたE問題。

当初考えていた方針は以下。

  1. 各位置iについて(ペアとなる括弧の位置Pair、削除されていない右側最近の位置Right、同左側Light)を記録しておくことでL, Rの移動をO(1)にする
  2. 削除クエリの更新はimos法 & BIT でO(logN)にする

で、全体でO(NlogN)で解けるという算段でしたが実装が間に合わず、終了後もバグらせの谷へ……。

結局、Legendary grandmaster, anta さんのコードを参考にしました。

  • コードをブロック化して変数のスコープを小さくしていたり(これはtorusさんのブログにも書いてあったテク)
  • イテレータを使いこなしていたり、
  • assertで事故防止していたり(コメントとしても使えるなこれ)

と、学ぶべきところがたくさんあるなあ…と思わされるコードでした。

以下のコードはantaさんのを見ながら写した後で、自分で空で書いたやつ。写経の時はいつも自分の身に染み込ませるつもりでそうしてます。

    int n, m, p;
    cin >> n >> m >> p;
    p--;
    string s, ops;
    cin >> s >> ops;
    V match(n, -1);
    {
        stack<int> stk;
        rep(i, n) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                auto j = stk.top(); stk.pop();
                match[i] = j;
                match[j] = i;
            }
        }
    }

    set<int> rem;
    rep(i, n) rem.insert(i);
    rep(i, m) {
        if (ops[i] == 'L') {
            p = *(-- rem.lower_bound(p));
        } else if (ops[i] == 'R') {
            p = *rem.lower_bound(p + 1);
        } else {
            assert(ops[i] == 'D');
            int q = match[p];
            if (q < p) swap(q, p);
            assert(p <= q);
            auto pt = rem.lower_bound(p);
            auto qt = rem.lower_bound(q);
            assert(*pt == p && *qt == q);
            ++ qt;  // [pt, qt)の半開区間にする
            rem.erase(pt, qt);  // [pt, qt)に含まれる括弧を削除
            if (qt != rem.end()) {
                p = *qt;    // qtがremの範囲内にあれば、次の位置はqt
            } else {
                // p = *(-- rem.lower_bound(p)); <--- p はもうeraseしてしまったので存在しない!!!
                -- qt;
                p = *qt;
            }
        }
    }

    string ans;
    for (int i : rem) {
        ans += s[i];
    }
    cout << ans << endl;

まとめ

今回は簡単だったみたいですけど、自力で4完できて5問目にも噛みつけたのでよかったです。

普段のRoundでも4完できるようになりたいですね。

とっとと次の色に行きたいので明日のVK Cup Div.2も出ます。