接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 320（ABC320）

AtCoder Beginner Contest 320（ABC320）

AtCoderBeginnerContest AtCoderBeginnerContest320 ABC ABC320

atcoder.jp

A - Leyland Number

問題文の通り計算して出力する

提出コード

void solve() {
    ll A, B;
    cin >> A >> B;
    ll a = 1;
    ll b = 1;
    REP(i, B) a *= A;
    REP(i, A) b *= B;
    cout << a + b << endl;
}

B - Longest Palindrome

連続部分列を全通り試し、回分判定を行う

提出コード

void solve() {
    string S;
    cin >> S;
    int N = S.size();
    int ans = 1;
    REP(i, N) {
        REP(j, i + 1, N) {
            string t = "";
            REP(k, i, j + 1) t += S[k];
            int sz = t.size();
            bool ok = true;
            REP(k, sz / 2) {
                if (t[k] != t[sz - k - 1]) {
                    ok = false;
                    break;
                }
            }
            if (ok) chmax(ans, sz);
        }
    }
    cout << ans << endl;
}

C - Slot Strategy 2 (Easy)

$ S_i = S_j $ かつ $ S_j = S_k $ を満たす $ i, j, k $ を考える
$ i, j, k $ が全て異なる場合、$ max(i, j, k) $ となる
それ以外の場合、同じ位置 $ x $ にあるものは $ x + M $ 後に押すことになるのでこれを各場合ごとに求めその最小を出力する

提出コード

void solve() {
    const int N = 3;
    int M;
    cin >> M;
    vector<string> S(N);
    REP(i, N) cin >> S[i];
    int ans = INF;
    REP(i, M) REP(j, M) REP(k, M) {
        if (S[0][i] == S[1][j] and S[0][i] == S[2][k]) {
            int mi = INF;
            if (i == j and i == k) mi = i + M * 2;
            else if (i == j) mi = i + M;
            else if (i == k) mi = i + M;
            else if (j == k) mi = j + M;
            else mi = max({i, j, k});
            chmin(ans, mi);
        }
    }
    cout << (ans == INF ? -1 : ans) << endl;
}

D - Relative Position

人1は原点にいて、与えられる情報は矛盾しないので人1からBFSで到達可能な頂点とその座標を決めていく

提出コード

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<int> A(M), B(M), X(M), Y(M);
    using T = tuple<ll, ll, ll>;
    vector<vector<T>> G(N);
    REP(i, M) {
        cin >> A[i] >> B[i] >> X[i] >> Y[i];
        A[i]--, B[i]--;
        G[A[i]].emplace_back(B[i], X[i], Y[i]);
        G[B[i]].emplace_back(A[i], -X[i], -Y[i]);
    }

    vector<LP> xy(N, {-1, -1});
    vector<bool> used(N, false);
    xy[0] = {0, 0};
    queue<int> q;
    q.emplace(0);
    while (!q.empty()) {
        auto v = q.front();
        q.pop();
        if (used[v]) continue;
        used[v] = true;
        for (auto [nv, x, y] : G[v]) {
            if (used[nv]) continue;
            ll nx = xy[v].first + x;
            ll ny = xy[v].second + y;
            xy[nv] = {nx, ny};
            q.emplace(nv);
        }
    }
    REP(i, N) {
        if (!used[i]) cout << "undecidable" << endl;
        else cout << xy[i].first << " " << xy[i].second << endl;
    }
}

E - Somen Nagashi

イベントソートっぽく各時点におけるそうめんを流すイベントと人 $ i $ が戻ってくるイベントを管理する
人が並んでいる情報をsetなどで持っておき、そうめんが流れてきたときに人がいるかどうかを判定すれば良い

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    // -1、人、null
    // 1、W, S
    using U = tuple<ll, ll, ll>;
    vector<ll> T(M), W(M), S(M);
    Compress<ll> cmp;
    REP(i, M) {
        cin >> T[i] >> W[i] >> S[i];
        cmp.add(T[i]);
        cmp.add(T[i] + S[i]);
    }
    cmp.add(LINF);
    cmp.build();
    int sz = cmp.size();
    vector<vector<U>> event(sz);

    REP(i, M) { event[cmp.get(T[i])].emplace_back(1, W[i], S[i]); }
    set<int> st;
    vector<ll> ans(N);
    REP(i, N) st.emplace(i);
    REP(i, sz) {
        sort(ALL(event[i]));
        for (auto v : event[i]) {
            auto [type, w, s] = v;
            if (type == -1) {
                st.emplace(w);
            }
            else {
                if (!st.empty()) {
                    auto p = *st.begin();
                    ans[p] += w;
                    ll nxt_t = cmp[i] + s;
                    event[cmp.get(nxt_t)].emplace_back(-1, p, 0);
                    st.erase(st.begin());
                }
            }
        }
    }
    REP(i, N) cout << ans[i] << endl;
}