接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 340（ABC340）

AtCoder Beginner Contest 340（ABC340）

AtCoderBeginnerContest AtCoderBeginnerContest340 ABC 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;
}