接着剤の精進日記

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

AtCoder Beginner Contest 344(ABC344)

atcoder.jp

A - Spoiler

| でフラグを切り替え、フラグによって出力をするかしないかを判断する

提出コード

void solve() {
    string S;
    cin >> S;
    bool skip = false;
    for (char c : S) {
        if (c == '|') skip = !skip;
        else if (!skip) cout << c;
    }
    cout << endl;
}

B - Delimiter

0 が出てくるまで値を読み込みvectorなどに格納し、逆順に出力する

提出コード

void solve() {
    vector<int> A;
    int n;
    while (true) {
        cin >> n;
        A.push_back(n);
        if (n == 0) break;
    }
    reverse(ALL(A));
    for (auto a : A)
        cout << a << endl;
}

C - Divide and Divide

最大ケースでも $ NML = 10^6 $ なので予め前計算した結果をsetなどに入れておくことで各クエリに高速に答えられる

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    int M;
    cin >> M;
    vector<int> B(M);
    REP(i, M) cin >> B[i];
    int L;
    cin >> L;
    vector<int> C(L);
    REP(i, L) cin >> C[i];
    set<int> st;
    REP(i, N) REP(j, M) REP(k, L) { st.insert(A[i] + B[j] + C[k]); }
    int Q;
    cin >> Q;
    while (Q--) {
        int X;
        cin >> X;
        cout << (st.count(X) ? "Yes" : "No") << '\n';
    }
}

D - String Bags

$ dp[i][j] := i $ 番目の袋まで見たときに $ j $ 文字目まで一致している状態に必要な最小金額としてDPをする

提出コード

void solve() {
    string T;
    int N;
    cin >> T >> N;
    vector<int> A(N);
    vector<vector<string>> S(N);
    REP(i, N) {
        cin >> A[i];
        REP(j, A[i]) {
            string s;
            cin >> s;
            S[i].emplace_back(s);
        }
    }
    int sz = T.size();
    vector<int> dp(sz + 1, INF);
    dp[0] = 0;
    REP(i, N) {
        vector<int> nxt(sz + 1, INF);
        REP(j, sz + 1) {
            if (dp[j] == INF) continue;
            chmin(nxt[j], dp[j]);
            int len = S[i].size();
            REP(k, len) {
                int l = S[i][k].size();
                if (j + l > sz) continue;
                bool ok = true;
                REP(m, l) {
                    if (T[j + m] != S[i][k][m]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    chmin(nxt[j + l], dp[j] + 1);
                }
            }
        }
        swap(dp, nxt);
    }
    cout << (dp[sz] < INF ? dp[sz] : -1) << endl;
}

E - Insert or Erase

ABC225D と同じように各値について自分の前後の値の情報を持っておき、各クエリごとにそれらを更新する

提出コード

void solve() {
    int N;
    cin >> N;
    map<int, pair<int, int>> node;
    vector<int> A(N);
    REP(i, N) {
        cin >> A[i];
        node[A[i]] = {-1, -1};
    }
    REP(i, N - 1) {
        node[A[i]].second = A[i + 1];
        node[A[i + 1]].first = A[i];
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int x, y;
            cin >> x >> y;
            if (node[x].second == -1) {  // 末尾
                node[x].second = y;
                node[y].first = x;
                node[y].second = -1;
            }
            else {  // それ以外
                int z = node[x].second;
                node[x].second = y;
                node[y].first = x;
                node[y].second = z;
                node[z].first = y;
            }
        }
        else if (q == 2) {
            int x;
            cin >> x;
            if (node[x].first == -1) {  // 先頭
                int y = node[x].second;
                node[y].first = -1;
            }
            else if (node[x].second == -1) {  // 末尾
                int y = node[x].first;
                node[y].second = -1;
            }
            else {  // それ以外
                node[node[x].first].second = node[x].second;
                node[node[x].second].first = node[x].first;
            }
            node.erase(x);
        }
    }
    int start = -1;
    for (auto [key, value] : node) {
        if (value.first == -1) {
            start = key;
            break;
        }
    }
    while (start != -1) {
        cout << start << " ";
        start = node[start].second;
    }
    cout << endl;
}

F - Earn to Advance

マス $ (i, j) $ から マス $ (k, l) $ まで移動するのに必要な最小コストは予めDPで求められるので前計算しておく
また、マス $ (i, j) $ から マス $ (k, l) $ へ移動するため必要な最小行動回数は現在の所持金と必要なコストから求めることができるので以下のDPをする
$ dp[i][j] := $ マス $ (i, j) $ にたどり着くのに必要な (最小の行動回数, その時の所持金の最大)のペア

提出コード

void solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> P(N, vector<ll>(N));
    REP(i, N) REP(j, N) cin >> P[i][j];
    vector<vector<ll>> R(N, vector<ll>(N - 1));
    REP(i, N) REP(j, N - 1) cin >> R[i][j];
    vector<vector<ll>> D(N - 1, vector<ll>(N));
    REP(i, N - 1) REP(j, N) cin >> D[i][j];
    int sz = N * N;
    vector<vector<ll>> cost(sz, vector<ll>(sz, LINF));
    REP(i, N) REP(j, N) {  // y, x
        int start = i * N + j;
        cost[start][start] = 0;
        REP(k, i, N) REP(l, j, N) {
            int from = k * N + l;
            if (l + 1 < N) {  // R
                int ny = k, nx = l + 1;
                int to = ny * N + nx;
                chmin(cost[start][to], cost[start][from] + R[k][l]);
            }
            if (k + 1 < N) {  // D
                int ny = k + 1, nx = l;
                int to = ny * N + nx;
                chmin(cost[start][to], cost[start][from] + D[k][l]);
            }
        }
    }
    dump(cost);
    vector<LP> dp(sz, LP(LINF, -LINF));  // move, money
    dp[0] = LP(0, 0);
    REP(i, sz) {
        REP(j, sz) {
            if (i == j) continue;
            if (cost[i][j] == LINF) continue;
            int y1 = i / N, x1 = i % N;
            int y2 = j / N, x2 = j % N;
            ll cur_money = dp[i].second;
            ll need_money = cost[i][j];
            ll need_move_cnt = abs(y1 - y2) + abs(x1 - x2);

            if (cur_money >= need_money) {
                if (dp[j].first > dp[i].first + need_move_cnt) {
                    dp[j].first = dp[i].first + need_move_cnt;
                    dp[j].second = cur_money - need_money;
                }
                else if (dp[j].first == dp[i].first + need_move_cnt) {
                    chmax(dp[j].second, cur_money - need_money);
                }
            }
            else {
                ll need = need_money - cur_money;
                ll need_cnt = ceil_div(need, P[y1][x1]);
                ll earned_money = need_cnt * P[y1][x1];
                if (dp[j].first > dp[i].first + need_cnt + need_move_cnt) {
                    dp[j].first = dp[i].first + need_cnt + need_move_cnt;
                    dp[j].second = earned_money + cur_money - need_money;
                }
                else if (dp[j].first == dp[i].first + need_cnt + need_move_cnt) {
                    chmax(dp[j].second, earned_money + cur_money - need_money);
                }
            }
        }
    }
    cout << dp[sz - 1].first << endl;
}

AtCoder Beginner Contest 340(ABC340)

atcoder.jp

A - Arithmetic Progression

for文で出力する

提出コード

void solve() {
    int A, B, D;
    cin >> A >> B >> D;
    for (int i = A; i <= B; i += D) {
        cout << i << " ";
    }
    cout << endl;
}

B - Append

vectorなどで実際に値を追加していき、各クエリに答えれば良い

提出コード

void solve() {
    int Q;
    cin >> Q;
    vector<int> A;
    while (Q--) {
        int q, x;
        cin >> q >> x;
        if (q == 1) A.emplace_back(x);
        else {
            int n = A.size();
            cout << A[n - x] << endl;
        }
    }
}

C - Divide and Divide

再帰関数などで操作をシミュレートできる
同じ値に対して愚直にシミュレートするとTLEするのでメモ化再帰することで間に合うようになる

提出コード

void solve() {
    ll N;
    cin >> N;
    map<ll, ll> dp;
    dp[0] = 0;
    auto dfs = [&](auto &&self, ll n) -> ll {
        if (dp.contains(n)) return dp[n];
        if (n == 1) return 0;
        ll res = n;
        res += self(self, ceil_div(n, 2)) + self(self, floor_div(n, 2));
        dp[n] = res;
        return dp[n];
    };
    cout << dfs(dfs, N) << endl;
}

D - Super Takahashi Bros.

与えられた入力をグラフと見なすことでダイクストラで解くことができる

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N), B(N), X(N);
    REP(i, N - 1) {
        cin >> A[i] >> B[i] >> X[i];
        --X[i];
    }
    vector<ll> dist(N, LINF);
    dist[0] = 0;
    priority_queue<LP, vector<LP>, greater<LP>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (dist[v] < d) continue;
        dumps(d, v);

        if (v < N - 1) {
            int nv = v + 1;
            ll nd = d + A[v];
            if (chmin(dist[nv], nd)) pq.push({nd, nv});
        }
        if (v < N - 1) {
            int nv = X[v];
            ll nd = d + B[v];
            if (chmin(dist[nv], nd)) pq.push({nd, nv});
        }
    }
    cout << dist[N - 1] << endl;
}

E - Mancala 2

$ B_i $ の箱に入っているボールの個数を $ X $ とすると、すべての箱に $ \lfloor \frac{X}{N} \rfloor $ 個のボールを入れ、残りの $ X \pmod{N} $ 個のボールを $ B_i + 1 $ から順に入れていく操作になる
これは1点変更・区間加算のクエリの操作ができれば良いので遅延セグメント木などを使えば良い

提出コード

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N), B(M);
    REP(i, N) cin >> A[i];
    REP(i, M) cin >> B[i];
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);
    REP(i, M) {
        ll id = B[i];
        ll x = seg.prod(id, id + 1);
        seg.set(id, 0);
        ll all = x / N;
        seg.apply(0, N, all);
        ll rest = x % N;
        seg.apply(id + 1, min(id + 1 + rest, N), 1);
        rest = rest - (min(id + 1 + rest, N) - (id + 1));
        seg.apply(0, max(0LL, rest), 1);
    }
    REP(i, N) cout << seg.prod(i, i + 1) << " ";
    cout << endl;
}

F - S = 1

三角形の面積公式から、$ (X, Y) $ の座標を使って $ |AY - BX| = 2 $ と表すことができる
よって、$ ax + by = c $ の不定方程式を解ければ良い
$ AY - BX = 2 $ が解を持つには $ 2 \equiv 0 \pmod{gcd(X, Y)} $ であれば良い
後は、拡張ユークリッドの互除法で実際に解を求めることができる
求めた解は $ c = gcd(X, Y) $ のときの解であるため、$ \frac{2}{gcd(X,Y)} $ 倍して出力する

参考

qiita.com

提出コード

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

void solve() {
    ll X, Y;
    cin >> X >> Y;
    if (2 % gcd(X, Y) != 0) {
        cout << -1 << endl;
        return;
    }
    ll x, y;
    extGCD(-Y, X, x, y);
    cout << 2 / gcd(X, Y) * x << " " << 2 / gcd(X, Y) * y << endl;
}

AtCoder Beginner Contest 336(ABC336)

atcoder.jp

A - Long Loong

問題文通りの文字列を作って出力する

提出コード

void solve() {
    int N;
    cin >> N;
    string S = "L";
    S += string(N, 'o');
    S += "ng";
    cout << S << endl;
}

B - CTZ

__builtin_ctz を使って求めれば良い

提出コード

void solve() {
    int N;
    cin >> N;
    cout << __builtin_ctz(N) << endl;
}

C - Even Digits

$ N $ を5進数と見なして変換を行う

提出コード

void solve() {
    ll N;
    cin >> N;
    string ans = "";
    N--;
    if (N == 0) {
        cout << 0 << endl;
        return;
    }
    while (N > 0) {
        int r = N % 5;
        char c = '0';
        if (r == 1) c = '2';
        else if (r == 2) c = '4';
        else if (r == 3) c = '6';
        else if (r == 4) c = '8';
        ans += c;
        N /= 5;
    }
    reverse(ALL(ans));
    cout << ans << endl;
}

D - Pyramid

$ L[i] := i $ を頂点としたときに作れるピラミッド数列の左側のサイズ
$ R[i] := i $ を頂点としたときに作れるピラミッド数列の右側のサイズ
を予め求めておくと、各 $ i $ が作れるピラミッド数列のサイズは $ \min(L[i], R[i]) $ となる

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    vector<int> L(N + 2), R(N + 2);
    REP(i, 1, N + 1) L[i] = min(L[i - 1] + 1, A[i - 1]);
    for (int i = N; i >= 1; i--)
        R[i] = min(R[i + 1] + 1, A[i - 1]);
    int ans = 0;
    REP(i, 1, N + 1) ans = max(ans, min(L[i], R[i]));
    cout << ans << endl;
}

E - Digit Sum Divisible

桁和の最大は $ 9 \times 14 = 144 $ であるので、桁和を全探索する
桁和を $ k $ と固定した場合についてそれぞれ桁DPで条件を満たすものの個数を数え上げる

提出コード

void solve() {
    string N;
    cin >> N;
    int sz = N.size();
    ll ans = 0;
    for (int K = 1; K <= 200; K++) {
        vector dp(sz + 1, vector(2, vector(K + 1, vector(K + 1, 0LL))));
        dp[0][0][0][0] = 1;
        REP(i, N.size()) {
            int d = N[i] - '0';
            REP(j, 2) REP(k1, K + 1) {
                REP(k2, K + 1) {
                    REP(l, 10) {
                        int ni = i + 1;
                        int nj = j;
                        if (j == 0) {
                            if (l < d) nj = 1;
                            if (l > d) continue;
                        }
                        int nk1 = (k1 * 10 + l) % K;
                        int nk2 = (k2 + l);
                        if (nk2 > K) continue;
                        dp[ni][nj][nk1][nk2] += dp[i][j][k1][k2];
                    }
                }
            }
        }
        ans += (dp[sz][0][0][K] + dp[sz][1][0][K]);
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 333(ABC333)

atcoder.jp

A - Three Threes

$ N $ 回 $ N $ を出力する

提出コード

void solve() {
    int N;
    cin >> N;
    REP(i, N) cout << N;
    cout << endl;
}

B - Pentagon

五角形の頂点を何回移動してたどり着けるかを数え一致していれば Yes

提出コード

void solve() {
    string S, T;
    cin >> S >> T;
    string U = "ABCDEABCDE";
    int s = 10, t = 10;
    REP(i, 10) REP(j, 10) {
        if (S[0] == U[i] and S[1] == U[j]) chmin(s, abs(j - i));
        if (T[0] == U[i] and T[1] == U[j]) chmin(t, abs(j - i));
    }
    cout << (s == t ? "Yes" : "No") << endl;
}

C - Repunit Trio

解の最大値が $ 112222222233 $ であるので12桁までのレピュニットを作り、$ 12 ^ 3 $ 通りの候補を作成、重複を削除してソートをしたものの $ N $ 番目のものが答え

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> repu;
    REP(l, 13) {
        ll i = 1;
        REP(_, l) i = i * 10 + 1;
        repu.push_back(i);
    }
    vector<ll> cand;
    for (ll num1 : repu) {
        for (ll num2 : repu) {
            for (ll num3 : repu) {
                cand.push_back(num1 + num2 + num3);
            }
        }
    }
    sort(ALL(cand));
    cand.erase(unique(ALL(cand)), cand.end());
    cout << cand[N - 1] << endl;
}

D - Erase Leaves

頂点 $ 1 $ を削除するためには頂点 $ 1 $ の子が $ 1 $ つである必要がある
そのため子の部分木のサイズが最大のものを残し、それ以外を削除する操作をするのが最適となる

提出コード

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    REP(i, N - 1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<int> sz(N);
    auto dfs = [&](auto &&self, int v, int par) -> int {
        sz[v] = 1;
        for (auto &e : g[v]) {
            if (e == par) continue;
            sz[v] += self(self, e, v);
        }
        return sz[v];
    };
    dfs(dfs, 0, -1);
    int ans = INF;
    int sum = 0;
    for (auto nv : g[0]) {
        sum += sz[nv];
    }
    for (auto nv : g[0]) {
        chmin(ans, sum - sz[nv] + 1);
    }
    cout << ans << endl;
}

E - Takahashi Quest

クエリを逆から考えるとクエリ $ 2 $ のときポーションを獲得し、クエリ $ 1 $ のときにそのポーションを持っていれば消費すると考えれば良い
上記をシミュレーションし、持っているポーションの最大値とポーションを獲得するかどうかを求めれば良い

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> need(202020);
    vector<int> t(N), x(N);
    int ma = 0;
    int sum = 0;
    REP(i, N) cin >> t[i] >> x[i];
    vector<int> ans;
    for (int i = N - 1; i >= 0; i--) {
        if (t[i] == 1) {
            if (need[x[i]]) {
                need[x[i]]--;
                sum--;
                ans.emplace_back(1);
            }
            else ans.emplace_back(0);
        }
        else {
            need[x[i]]++;
            sum++;
            chmax(ma, sum);
        }
    }
    REP(i, 202020) if (need[i] > 0) {
        cout << -1 << endl;
        return;
    }
    cout << ma << endl;
    reverse(ALL(ans));
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
}

AtCoder Beginner Contest 328(ABC328)

atcoder.jp

A - Not Too Hard

題意の通り条件を満たすものの合計を求める

提出コード

void solve() {
    int N, X;
    cin >> N >> X;
    int sum = 0;
    REP(i, N) {
        int A;
        cin >> A;
        if (A <= X) sum += A;
    }
    cout << sum << endl;
}

B - 11/11

$ i, j $ が1種類の数字だけであるかどうかを判定する
to_stringで文字列にしておくと多分楽

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> D(N);
    REP(i, N) cin >> D[i];
    int ans = 0;
    REP(i, N) {
        int m = i + 1;
        for (int d = 1; d <= D[i]; d++) {
            string md = to_string(m) + to_string(d);
            bool ok = true;
            REP(j, (int)md.size() - 1) {
                if (md[j] != md[j + 1]) ok = false;
            }
            if (ok) ans++;
        }
    }
    cout << ans << endl;
}

C - Consecutive

条件を満たすものの個数の累積和を前計算しておくことで各クエリに対して $ O(1) $ で答えることができる

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> cum(N + 1);
    REP(i, N - 1) cum[i + 1] = cum[i] + (S[i] == S[i + 1]);
    cum[N] = cum[N - 1];
    dump(cum);
    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << cum[r] - cum[l] << endl;
    }
}

D - Take ABC

stackなどで先頭から順に文字を積んでいき、末尾3個は ABC の場合に消去する操作を行い、最終的に残った値を出力すればいい

提出コード

void solve() {
    string S;
    cin >> S;
    vector<char> st;
    for (char c : S) {
        if (st.size() < 2) st.emplace_back(c);
        else {
            if (c == 'C') {
                char c2 = st.back();
                st.pop_back();
                char c1 = st.back();
                st.pop_back();
                if (c1 == 'A' and c2 == 'B') {
                    continue;
                }
                st.emplace_back(c1);
                st.emplace_back(c2);
                st.emplace_back(c);
            }
            else {
                st.emplace_back(c);
            }
        }
    }
    for (auto c : st)
        cout << c;
    cout << endl;
}

E - Modulo MST

全域木なので $ N - 1 $ 本の辺を選ぶ場合のみ考えれば良く、これは最大で $ _{28} C _7 = 1184040 $ 通りなので全探索すれば良い
$ M - (N - 1) $ 個の $ 0 $ と $ N - 1 $ 個の $ 1 $ を並べた配列にnext_permutationを使うとcombinationの列挙ができる

提出コード

void solve() {
    ll N, M, K;
    cin >> N >> M >> K;
    vector<ll> u(M), v(M), w(M);
    REP(i, M) {
        cin >> u[i] >> v[i] >> w[i];
        --u[i], --v[i];
    }
    ll ans = LINF;
    vector<int> cmb;
    REP(i, M - (N - 1)) cmb.emplace_back(0);
    REP(i, N - 1) cmb.emplace_back(1);
    do {
        ll sum = 0;
        UnionFind uf(N);
        bool ok = true;
        REP(i, M) if (cmb[i]) {
            if (uf.issame(u[i], v[i])) {
                ok = false;
                break;
            }
            uf.unite(u[i], v[i]);
            sum += w[i];
            if (sum >= K) sum -= K;
        }
        if (ok) chmin(ans, sum);
    } while (next_permutation(ALL(cmb)));
    cout << ans << endl;
}

F - Good Set Query

$ u - v = d $ という関係式を満たすかどうかは、ある頂点 $ u, v $ の間の距離が $ d $ であるという関係式として考える
そうするとポテンシャル付きUnion Findを使うことで関係式を保存し、新しく関係式を追加する際に過去の関係式と矛盾するかどうかを判定できる

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    PotentializedUnionFind<ll> uf(N);
    vector<int> ans;
    REP(i, Q) {
        int a, b, d;
        cin >> a >> b >> d;
        --a, --b;
        if (uf.issame(a, b)) {
            if (uf.dist(a, b) == d) ans.emplace_back(i + 1);
        }
        else {
            uf.unite(a, b, d);
            ans.emplace_back(i + 1);
        }
    }
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
}