AtCoder Beginner Contest 125

競技プログラミング

結果

　23分33秒で全完、122位だった。C問題で少し時間がかかってしまったが、順位表を見ているとD問題を先に解いている人も多く、難しめではあったのかもしれない。100位以内の壁は厚い。

A問題

　まぁA問題だし素直に割るだけなんだろうなーという感じで実装しながら脳内で確認する動き。余りを考えるのは苦手。

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

int main() {
    ll A, B, T;
    cin >> A >> B >> T;
    cout << B * (T / A) << endl;
}

B問題

　これはさすがに入力取りながら答えを求められる程度の問題だと思ったら最初にVがN個連続、そしてCがN個連続という形式の入力だったので結局一度受け取ってから別のforループで答えを求めるいつものパターンに。

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

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

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

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans += max(V[i] - C[i], (ll)0);
    }
    cout << ans << endl;
}

C問題

　A_iを抜いた最大公約数が求まれば良いとはすぐ思ったが、愚直に計算するとO(N^2)かかってしまう。計算量を落とす方法がすぐにはわからなくて方針が間違っているのかと二分探索とか素因数を一つ一つ考えていくとか疑い出したが、累積和っぽいイメージでA_1, \dots A_{i - 1}の最大公約数とA_{i + 1}, \dots, A_{N}の最大公約数をあらかじめ計算しておけば、これらの最大公約数を取ればいいだけということに気づいて勝ち。

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

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

    vector<ll> B(N), C(N);
    B[0] = A[0];
    for (ll i = 1; i < N; i++) {
        B[i] = gcd(B[i - 1], A[i]);
    }
    C[N - 1] = A[N - 1];
    for (ll i = N - 2; i >= 0; i--) {
        C[i] = gcd(C[i + 1], A[i]);
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ll p = (i == 0 ? C[i + 1] : i == N - 1 ? B[N - 2] : gcd(B[i - 1], C[i + 1]));
        ans = max(ans, p);
    }

    cout << ans << endl;
}

　B_iを[1, i]の最大公約数として計算してしまったが、こういうのも右側は開区間で取った方が実装がきれいになりそうだ。範囲系のものは大抵[i, j)として定義してしまうので問題ない気がするし、こうした方が区間を取るミスも少しは減らせそうか。

　解説PDFを見たら、GCDを変えない初期値としてB_0 = 0としていた。なるほど確かにgcd(X, 0) = gcd(0, X) = Xとなるのは自分の実装でも計算してみるとわかる。当たり前なんだろうけどこれは勉強になった。

D問題

　いかにもDPですという顔をしている問題に見えた。そういうつもりで考えていくとi番目のものを考えるときに直前で操作を行ったかどうかの2通りを考えれば良いということはすぐに見えるものなので、細部を詰めて実装して難なくAC。

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

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

    vector<vector<ll>> dp(2, vector<ll>(N + 1, 0));
    dp[1][0] = INT_MIN;

    for (ll i = 0; i < N; i++) {
        //操作する
        dp[1][i + 1] = max(dp[0][i] - A[i], dp[1][i] + A[i]);

        //操作しない
        dp[0][i + 1] = max(dp[0][i] + A[i], dp[1][i] - A[i]);
    }

    cout << dp[0][N] << endl;
}

　他のDPでもそうだけど、直前だけに依存するなら無駄に過去の情報を保持する必要もない。今までは考えやすいように(メモリ使用量が大丈夫なことを確認して)冗長でも長さ分取るようにしていたが、そろそろ必要なところだけを残すようにした方が良いかなとも思う。

　解説PDFを見たら、最終的に負のまま残るのは負であるものが奇数個のとき1個、偶数個のとき0個なので簡単に計算できるとあってそれは全く気づいていなかった。解いているときにすぐDPに向いてしまって問題の考察をサボっているという感じは確かにあったが、こんな簡単な性質を見落としているとは。やけにD問題解いた人多いなと思ったのはこういうからくりだったのか。できればこういう解法が浮かぶような考察をしていきたいと思っているのでこれは反省点。すぐ知っているアルゴリズムに帰着させようとしすぎてはいけない。