AtCoder Beginner Contest 182 に参加しました

調子よかった回のことばっかり書いてる気がしてきたから、そうでもない回のことも書いておきます。
atcoder.jp

成績

A - twiblr

問題：（リンク）
の制約見落としてた。max とる必要なし

コードを表示

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll a, b;
    cin >> a >> b;
    cout << max(0ll, (2 * a + 100) - b) << '\n';
}

B - Almost GCD

問題：（リンク）
std::max_element 使うと楽？

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> cnt(1010, 0);
    for (int k = 2; k < 1010; k++) {
        rep(i, n) if (a[i] % k == 0) cnt[k]++;
    }
    cout << max_element(cnt.begin(), cnt.end()) - cnt.begin() << '\n';
}

C - To 3

問題：（リンク）
場合分けした。でもbit全探索の方が楽だしバグらせないし賢いね。

コードを表示

#include <bits/stdc++.h>
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
int main() {
    ll n;
    cin >> n;
    string s = to_string(n);
    vector<int> cnt(3);
    for (char c : s) cnt[(c - '0') % 3]++;
    if (n % 3 == 0) {
        cout << 0 << '\n';
    } else if (n % 3 == 1) {
        if (cnt[1] >= 1 && sz(s) > 1) {
            cout << 1 << '\n';
        } else if (cnt[2] >= 2 && sz(s) > 2) {
            cout << 2 << '\n';
        } else {
            cout << -1 << '\n';
        }
    } else if (n % 3 == 2) {
        if (cnt[2] >= 1 && sz(s) > 1) {
            cout << 1 << '\n';
        } else if (cnt[1] >= 2 && sz(s) > 2) {
            cout << 2 << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
}

D - Wandering

問題：（リンク）
累積累積maxみたいなのを見ればOK。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> maxs(n);
    maxs[0] = a[0];
    rep(i, n - 1) {
        a[i + 1] += a[i];
        maxs[i + 1] = max(maxs[i], a[i + 1]);
    }

    ll ans = 0, pos = 0;
    rep(i, n) {
        chmax(ans, pos + maxs[i]);
        pos += a[i];
    }
    cout << ans << '\n';
}

E - Akari

問題：（リンク）
お前も鬼にならないか？ならない。
またまたグリッドを照らすんか、逆に Lamp とか Lamps とは何が違うんや？と少しフリーズしてしまってもったいない。ブロックとブロックの間に電球が存在するか？を縦横に全部みればOK。
配列外参照で1ペナ。めっちゃ配列外参照しちゃう。配列内参照が難しいんかもしれん。逆にね。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
    int h, w, n, m;
    cin >> h >> w >> n >> m;
    vector<vector<bool>> lamp(h, vector<bool>(w));
    vector<vector<bool>> block(h, vector<bool>(w));
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        lamp[--a][--b] = true;
    }
    rep(i, m) {
        int c, d;
        cin >> c >> d;
        block[--c][--d] = true;
    }

    vector<vector<bool>> ok(h, vector<bool>(w));
    rep(i, h) {
        rep(j, w) {
            if (lamp[i][j]) {
                int k = j;
                for (; k >= 0 && !block[i][k]; k--) {
                    ok[i][k] = 1;
                }
                k = j;
                for (; k < w && !block[i][k]; k++) {
                    ok[i][k] = 1;
                }
                j = k;
            }
        }
    }
    rep(j, w) {
        rep(i, h) {
            if (lamp[i][j]) {
                int k = i;
                for (; k >= 0 && !block[k][j]; k--) {
                    ok[k][j] = 1;
                }
                k = i;
                for (; k < h && !block[k][j]; k++) {
                    ok[k][j] = 1;
                }
                i = k;
            }
        }
    }
    int ans = 0;
    rep(i, h) rep(j, w) ans += ok[i][j];
    cout << ans << '\n';
}

F - Valid payments

問題：（リンク）
タイトルと設定みた段階ですでに苦手意識が止まらん。お金払う系、解けたためしがない（ Payment, Pay to Win ）。

「ルンルンが店員に渡したコインのいずれかと同じ種類のコインが店員から返されることはありませんでした。」という条件から、 種類のコインそれぞれについて（基本的には）店員が使うかルンルンが使うかの二択になる（どっちも使わない、もありだけど）。二択を繰り返す問題は DP、と歴史の教科書に書いてあるので、DP！！！
コンテスト終了には間に合わなかったけどなんとか解けて嬉しい。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main() {
    int n;
    ll x;
    cin >> n >> x;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    auto f = [&](ll num, int i) {
        for (int j = n - 1; j > i; j--) num %= a[j];
        return num / a[i];
    };

    using P = pair<ll, int>;
    map<P, ll> memo;
    auto dp = [&](auto dp, ll num, int i) -> ll {
        if (i >= n) return 0;
        if (i == n - 1) return 1;
        if (memo.count(P(num, i))) return memo[P(num, i)];

        ll ret = 0;
        ll nnum = num / a[i + 1] * a[i + 1];

        ret += dp(dp, nnum, i + 1);
        if (f(num, i) > 0) ret += dp(dp, nnum + a[i + 1], i + 1);

        return memo[P(num, i)] = ret;
    };
    cout << dp(dp, x, 0) << '\n';
}

おわり

Highest まであと14
黄色まであと178