AtCoder Beginner Contest 336（ABC336）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 336での成績：1004位
パフォーマンス：1507相当
レーティング：1496→1497 (+1) :)#AtCoder #ABC336 https://t.co/pD8OqeJgF9

— ボンド@競プロ (@bond_cmprog) January 14, 2024

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;
}