AtCoder Beginner Contest 129

結果

 E問題までの5完。Fを解けている人が少なく、Eまでの早解きゲームになっていたようだ。近のRatedでは6回連続でレートが伸びており、たまたま上手くいっている感じは否めないが気分は良い。

f:id:tokumini:20190610095604p:plain

A問題

 ちゃんと問題文を読めているかちょっと不安になりつつの提出だった。

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

int main() {
    ll P, Q, R;
    cin >> P >> Q >> R;
    cout << P + Q + R - max({ P, Q, R }) << endl;
}

B問題

 脳を使いたくなかったのでO(N^2)で大丈夫であることを確認した後は問題文に書いてある通りのことを実装した。

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

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

    ll ans = INT_MAX;
    for (ll T = 0; T < N - 1; T++) {
        ll S1 = 0, S2 = 0;
        for (ll i = 0; i < N; i++) {
            if (i <= T) {
                S1 += W[i];
            } else {
                S2 += W[i];
            }
        }
        ans = min(ans, abs(S1 - S2));
    }

    cout << ans << endl;
}

C問題

 最初は2個前までの数字だけを保持して上手くやろうと考えていたけどこんがらがってしまったのでおとなしくdp配列を使うわかりやすい形で実装した。

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

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

    vector<bool> ok(N + 1, true);
    for (ll i = 0; i < M; i++) {
        ok[a[i]] = false;
    }

    constexpr ll MOD = 1e9 + 7;
    vector<ll> dp(N + 1, 0);
    dp[0] = 1;
    dp[1] = (ok[1] ? 1 : 0);
    for (ll i = 2; i <= N; i++) {
        if (ok[i]) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        } else {
            dp[i] = 0;
        }
    }

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

D問題

 上下と左右それぞれでどれだけ繋がっているかを事前計算する部分で手間取ってしまった。累積和とって後ろからmaxを取り直していくだけなんだけど、障害物マスをINT_MAXとかで初期化すれば上手いこと場合分けいらなくなるのでは? とか余計なことを考えたのがまずかった。おとなしく毎回場合分けを書いてAC。もっと簡単に実装できたのにやっているときにはなかなか思い浮かばない。

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

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

    vector<vector<ll>> row(H, vector<ll>(W, 0));
    vector<vector<ll>> col(H, vector<ll>(W, 0));

    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            row[i][j] = (S[i][j] == '.' ? 1 : 0);
        }
        for (ll j = 1; j < W; j++) {
            row[i][j] = (S[i][j] == '.' ? row[i][j] + row[i][j - 1] : 0);
        }
        for (ll j = W - 2; j >= 0; j--) {
            row[i][j] = (S[i][j] == '.' ? max(row[i][j], row[i][j + 1]) : 0);
        }
    }
    for (ll j = 0; j < W; j++) {
        for (ll i = 0; i < H; i++) {
            col[i][j] = (S[i][j] == '.' ? 1 : 0);
        }
        for (ll i = 1; i < H; i++) {
            col[i][j] = (S[i][j] == '.' ? col[i][j] + col[i - 1][j] : 0);
        }
        for (ll i = H - 2; i >= 0; i--) {
            col[i][j] = (S[i][j] == '.' ? max(col[i][j], col[i + 1][j]) : 0);
        }
    }

    ll ans = 0;
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            ans = max(ans, row[i][j] + col[i][j]);
        }
    }

    cout << ans - 1 << endl;
}

E問題

 桁DPを書くだけとは思いつつ慣れていないのでこれがまた苦労する。普通のdpでも実装はメモ化再帰に頼りがちではあるけど、桁dpは特にforループで書く方法がわからない。特に困っていないので習得しようという気にもあまりならない。

 解説PDFを読んでみて、dp配列を二つ持たないといけないやつも今回みたいな以上・未満で二つ考えるのと同じことなのだなと思った。そう考えるとdp配列を二つ持たないといけない問題もめちゃくちゃ突飛な発想を求められているわけでもないのか。桁dpならすぐ見えることをちょっと見た目が変わっただけでわからなくなるのは寂しい。

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

string L;
constexpr ll MOD = 1e9 + 7;
vector<vector<ll>> memo;

ll solve(ll i, bool small) {
    if (i == L.size()) {
        return 1;
    }

    if (memo[i][small] != -1) {
        return memo[i][small];
    }

    ll result = 0;
    if (small) {
        result = 3 * solve(i + 1, small) % MOD;
    } else {
        if (L[i] == '0') {
            //(0, 0)だけ
            result = solve(i + 1, false);
        } else {
            //(1, 0), (0, 1), (0, 0)
            result = (2 * solve(i + 1, small) % MOD + solve(i + 1, true)) % MOD;
        }
    }

    return memo[i][small] = result;
}

int main() {
    cin >> L;
    memo.resize(L.size(), vector<ll>(2, -1));
    cout << solve(0, false) << endl;
}

F問題

 数列の[i, j)範囲について問題の答えを返す関数solve(ll i, ll j)を作ったとき、solve(0, L) = pow(10, d) * solve(0, L / 2) + solve(L / 2, L) (dは[L / 2, L)内にある数の桁数の和)という感じで分解できそうだという方針でやっていたけどサンプル3が合わず撃沈。どれくらい合わないのか確かめるために提出してみたらいくつもWAになったしTLEまでたくさん出たので全然ダメだった。

 解説PDFを読んでなんとかAC。桁が同じものはまとめて計算できそうというところにそもそも気づいていないし、気づいてもそこから行列累乗まで落とし込める気はしない。2段階考察が足りていなかった。

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

ll L, A, B, M;

vector<vector<ll>>& operator*=(vector<vector<ll>>& lhs, vector<vector<ll>> rhs) {
    auto result = lhs;
    for (ll i = 0; i < result.size(); i++) {
        for (ll j = 0; j < result[i].size(); j++) {
            result[i][j] = 0;
            for (ll k = 0; k < lhs.size(); k++) {
                (result[i][j] += lhs[i][k] * rhs[k][j] % M) %= M;
            }
        }
    }
    return lhs = result;
}

int main() {
    cin >> L >> A >> B >> M;

    ll ans = 0;
    ll pre = 0;
    ll s = A;
    for (ll d = 1; d <= 18; d++) {
        ll target = 1;
        for (ll j = 0; j < d; j++) {
            target *= 10;
        }
        ll low = pre - 1, eq_high = L;
        while (low != eq_high - 1) {
            ll mid = (low + eq_high) / 2;
            ll s_mid = A + B * mid;
            (s_mid < target ? low = mid : eq_high = mid);
        }

        ll C_d = eq_high - pre;
        pre = eq_high;

        vector<vector<ll>> mat = {
                { target % M,     0, 0 },
                {          1,     1, 0 },
                {          0, B % M, 1 }
        };

        vector<vector<ll>> result = {
                { 1, 0, 0 },
                { 0, 1, 0 },
                { 0, 0, 1 }
        };

        while (C_d) {
            if (C_d % 2 == 1) {
                result *= mat;
            }

            C_d /= 2;
            mat *= mat;
        }

        vector<ll> v = { ans, s, 1 };
        ans = 0;
        s = 0;
        for (ll i = 0; i < 3; i++) {
            (ans += v[i] * result[i][0] % M) %= M;
            (s += v[i] * result[i][1] % M) %= M;
        }
    }

    cout << ans << endl;
}