AtCoder Beginner Contest 128

結果

　E問題までの5完。思ったよりレートが伸びて1級になった。

A問題

　足す部分を分けてしまったが別に1行で済むなぁと思いながら直すのも面倒だったので。

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

int main() {
    ll A, P;
    cin >> A >> P;
    P += 3 * A;
    cout << P / 2 << endl;
}

B問題

　restaurantの綴りに自信がなくて型の名前がRになった。構造体を作ってソートするやつって上手いことスニペットにできたりするんだろうか。

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

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

    struct R {
        ll P, index;
        string S;
    };
    vector<R> rs(N);
    for (ll i = 0; i < N; i++) {
        cin >> rs[i].S >> rs[i].P;
        rs[i].index = i + 1;
    }

    sort(rs.begin(), rs.end(), [](R& lhs, R& rhs) {
        return lhs.S != rhs.S ? lhs.S < rhs.S : lhs.P > rhs.P;
    });

    for (const R& r : rs) {
        cout << r.index << endl;
    }
}

C問題

　ネストが深くなって脳が混乱した。計算量もちゃんとは考えてないけどC問題ならこれで通るだろうというメタ読みをするなど。

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

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> k(M), p(M);
    vector<vector<ll>> s(M);
    for (ll i = 0; i < M; i++) {
        cin >> k[i];
        for (ll j = 0; j < k[i]; j++) {
            ll t;
            cin >> t;
            s[i].push_back(t - 1);
        }
    }
    for (ll i = 0; i < M; i++) {
        cin >> p[i];
    }

    ll ans = 0;
    for (ll i = 0; i < (1 << N); i++) {
        bool ok = true;
        for (ll j = 0; j < M; j++) {
            ll num = 0;
            for (ll k : s[j]) {
                if (i & (1 << k)) {
                    num++;
                }
            }
            if (num % 2 != p[j]) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans++;
        }
    }

    cout << ans << endl;
}

D問題

　ちょっと悩んだけど操作が4種類というのが多いのでいくらか不要になりそうということを考えてみると手持ちのものを詰めていくのは最後にまとめて捨てるのと同義になるし、そうなると左右からどれだけ取るかの全探索で終わり。もう少し上手い実装はありそう。かなり力技っぽい書き方になってしまった。最後マイナスの要素を捨てていくところでこんなにif文まみれにしてしまうなんて。

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

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> V(N);
    for (ll i = 0; i < N; i++) {
        cin >> V[i];
    }

    ll ans = 0;
    for (ll i = 0; i <= K; i++) {
        for (ll j = 0; j <= K - i; j++) {
            vector<ll> copy = V;
            vector<ll> picked;
            for (ll k = 0; k < i; k++) {
                if (copy.empty()) {
                    break;
                }
                picked.push_back(copy.front());
                copy.erase(copy.begin());
            }
            for (ll k = 0; k < j; k++) {
                if (copy.empty()) {
                    break;
                }
                picked.push_back(copy.back());
                copy.pop_back();
            }

            sort(picked.begin(), picked.end());
            ll tmp = 0;
            ll rem = K - i - j;
            for (ll e : picked) {
                if (e >= 0) {
                    tmp += e;
                } else {
                    if (rem > 0) {
                        rem--;
                    } else {
                        tmp += e;
                    }
                }
            }

            ans = max(ans, tmp);
        }
    }

    cout << ans << endl;
}

E問題

　最初は遅延セグメント木に投げればなんとかなったりしないかと手を抜きたい思考が出ていたけど、ちゃんと考えて解説PDFそのままな感じの思考過程でなんとかなった。

　本番では不要な部分が多い汚いコードを書いてしまったので書き直し（元)。最初は工事だけでソートできなきゃいけないんじゃないかとかいろいろ迷走していたので無用な構造体ばかりになっていた。setも値を引数にとっての削除ができるんだからpriority_queueとmapを使って管理するなんてことをしなくて良かったんだった。種々の制約のおかげでかなり書きやすいし解いてて楽しい問題。

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

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

    enum Type {
        STOP_END, STOP_START, WALK_START
    };
    struct Query {
        Type type;
        ll time, pos;
        bool operator<(const Query& rhs) const {
            return (time != rhs.time ? time > rhs.time : type > rhs.type);
        }
    };
    priority_queue<Query> pq;

    for (ll i = 0; i < N; i++) {
        ll S, T, X;
        cin >> S >> T >> X;
        pq.push({ STOP_START, S - X, X });
        pq.push({ STOP_END,   T - X, X });
    }

    for (ll i = 0; i < Q; i++) {
        ll D;
        cin >> D;
        pq.push({ WALK_START, D, -1 });
    }

    set<ll> st;
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();

        if (top.type == STOP_START) {
            st.insert(top.pos);
        } else if (top.type == STOP_END) {
            st.erase(top.pos);
        } else {
            cout << (st.empty() ? -1 : *st.begin()) << endl;
        }
    }
}

F問題

　45分くらい残った状態で入れたのでなんとか通したかったが、ダメだった。中央から見て対称な位置を踏むような経路は取れそうとは思っていたけど詰めきれなかった。解説を読んでもよくわからず、他の人のコードを読んでなんとか通るコードは書いたがまた微妙に理解が怪しい。r < Cだったらbreakという処理を入れないとが負の場合を考慮してしまうあたりを今ようやくわかり始めてきた。

　下の実装、実は回のループ内でvector<bool> (N, false)を初期化しているんだけど108msで普通に通る。こういうものの初期化なら問題ないのか。上手くやるには訪問かどうかのフラグvector<ll> (N)を使ってを書き込んでいき、いま訪問したものがと一致していないかどうかを判定すれば良いようだ。

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

int main() {
    ll N;
    cin >> N;
    vector<ll> S(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
    }

    auto isOK = [N](ll x) {
        return 0 <= x && x < N;
    };

    ll ans = 0;
    for (ll C = 1; C < N; C++) {
        vector<bool> visit(N, false);
        ll l = 0, r = N - 1;
        ll score = 0;
        while (true) {
            l += C;
            r -= C;
            if (!isOK(l) || !isOK(r) || visit[l] || visit[r] || l == r || r < C) {
                break;
            }
            visit[l] = visit[r] = true;
            score += S[l] + S[r];
            ans = max(ans, score);
        }
    }

    cout << ans << endl;
}