AtCoder Grand Contest 034

競技プログラミング

結果

　A,Bの2完でレート+1。C問題を解けないようでは厳しい。

A問題

　C,Dのうち右にある方を先に移動させたいという気持ちから考えていって方針は早い段階で立ったのだが、実装で悩んでしまった。最終的には多少冗長でも1マスずつ見ていくようにループを書くのが見通しが良かった。こういうのをもっと短い時間ですっきり実装できるようになりたい。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    A--; B--; C--; D--;

    if (C < D) {
        //普通にBから移動
        bool ok_B = true;
        for (ll i = B + 1; i < D; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_B = false;
                break;
            }
        }

        bool ok_A = true;
        for (ll i = A + 1; i < C; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_A = false;
                break;
            }
        }

        cout << (ok_A && ok_B ? "Yes" : "No") << endl;
    } else {
        bool ok_B = false;
        for (ll i = B; i <= D; i++) {
            //左右が空ならOK
            if (S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.') {
                ok_B = true;
                break;
            }
        }

        bool ok_A = true;
        for (ll i = A + 1; i < C; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_A = false;
                break;
            }
        }

        cout << (ok_A && ok_B ? "Yes" : "No") << endl;
    }
}

B問題

　AAA...AAAABCとなっている場合Aが並んでいる数だけ操作できる。AAA...AAAABCBCとなっている場合、2回目のBCにもその前に並んでいるAがそのまま流れ込んでくる。そんな感じで実装する。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string s;
    cin >> s;
    
    ll ans = 0, A_num = 0;
    for (ll i = 0; i < (ll)s.size() - 1; i++) {
        if (s[i] == 'A') {
            A_num++;
        } else if (A_num > 0 && s[i] == 'B' && s[i + 1] == 'C') {
            ans += A_num;
            i += 1;
        } else {
            A_num = 0;
        }
    }

    cout << ans << endl;
}

C問題

　解説PDFの問題の言い換えはできていたし、二分探索で操作回数を決めて、「1個以上X − 1個以下の要素を選ぶ数列が高々1つ」なのでll a = mid / X, b = mid % X;という分解ができるのもなんとなく考えていたが詰めきれなかった。X個選んだときの利得でソートして上位k個を無条件に選び、残り分をpriority_queueに入れて上から取っていくというような実装をしてみたが半分ほどしかACにならなかった。確かによく考えてみると上位k個の中にb点までの利得が高いものがあり、k個以外の中にはb点までの利得が良くないがb点以上の利得がそこそこなものがあるような場合で、後者をX点まで選んで前者からX点未満まで選ぶ方が良くなるのか。少し気づきにくいところでもある気がするが、解きたい問題ではあった。もう少し時間があれば可能性があったかもしれないし、それはA,B問題をもっと早く解けていればということでもあって、力をつけていくしかない。解説を読めばすぐ通るコードは書けた。本番で解くとしたら落ち着いて計算量を考え直して、判定部分でO(N)が許される→探索できそうというように思考が流れれば良いのだろうか。次こそは。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, X;
    cin >> N >> X;

    struct Test {
        ll b, l, r;
    };
    vector<Test> tests(N);
    for (ll i = 0; i < N; i++) {
        cin >> tests[i].b >> tests[i].l >> tests[i].r;
    }
    sort(tests.begin(), tests.end(), [&](Test& lhs, Test& rhs) {
        ll lv = (X - lhs.b) * lhs.r + lhs.b * lhs.l;
        ll rv = (X - rhs.b) * rhs.r + rhs.b * rhs.l;
        return lv > rv;
    });
    vector<ll> score(N);
    for (ll i = 0; i < N; i++) {
        score[i] = (X - tests[i].b) * tests[i].r + tests[i].b * tests[i].l;
    }
    vector<ll> score_sum(N + 1, 0);
    for (ll i = 0; i < N; i++) {
        score_sum[i + 1] = score_sum[i] + score[i];
    }

    ll default_sum = 0;
    for (ll i = 0; i < N; i++) {
        default_sum -= tests[i].b * tests[i].l;
    }

    ll ok = X * N, ng = -1;
    while (ok != ng + 1) {
        ll mid = (ok + ng) / 2;

        ll a = mid / X;
        ll b = mid % X;

        bool flag = false;
        for (ll i = 0; i < N; i++) {
            ll curr_sum = default_sum;

            //iを除いた上位a個の和
            curr_sum += (i >= a ? score_sum[a] : score_sum[a + 1] - score[i]);

            //iからb個選ぶ
            curr_sum += tests[i].l * min(tests[i].b, b);
            curr_sum += tests[i].r * (b - min(tests[i].b, b));

            if (curr_sum >= 0) {
                flag = true;
                break;
            }
        }

        (flag ? ok = mid : ng = mid);
    }

    cout << ok << endl;
}