問題A: Sanitizer

N人の人が順番に手を消毒します。各人が必要とする消毒液の量 $H_i$ が与えられ、合計 $M$ 単位の消毒液があるとき、何人目までが完全に手を消毒できるかを求める問題です。

実装としては、配列に格納された各 $H_i$ を順に累積し、その合計が $M$ を超えた時点のインデックスを確認します。累積和が $M$ を超えない場合は、全員が消毒可能です。

#include <iostream>
#include <vector>

int main() {
    int n;
    long long m;
    if (!(std::cin >> n >> m)) return 0;

    std::vector<int> requirements(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> requirements[i];
    }

    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (m >= requirements[i]) {
            m -= requirements[i];
            count++;
        } else {
            break;
        }
    }

    std::cout << count << std::endl;
    return 0;
}

問題B: Uppercase and Lowercase

与えられた文字列 $S$ において、大文字の数が小文字の数より多ければすべて大文字に、そうでなければすべて小文字に変換する問題です。

まず文字列を走査して大文字と小文字の個数をカウントし、その結果に基づいて toupper または tolower 関数を適用して変換を行います。

#include <iostream>
#include <string>
#include <cctype>

int main() {
    std::string s;
    std::cin >> s;

    int upper_count = 0;
    int lower_count = 0;
    for (char c : s) {
        if (std::isupper(c)) upper_count++;
        else lower_count++;
    }

    if (upper_count > lower_count) {
        for (char &c : s) c = std::toupper(c);
    } else {
        for (char &c : s) c = std::tolower(c);
    }

    std::cout << s << std::endl;
    return 0;
}

問題C: Sierpinski Carpet

レベル $K$ のフラクタル図形（シェルピンスキーのカーペット）を出力する問題です。レベル $K$ の図形は $3^K \times 3^K$ のサイズを持ち、中央の $3^{K-1} \times 3^{K-1}$ のブロックは空（'.'）で、それ以外の 8 つのブロックにはレベル $K-1$ の図形が入るという再帰的な構造をしています。

再帰関数を用いて、現在のレベル、開始座標（行・列）を指定してグリッドを埋めていくアプローチが有効です。レベル 0 の場合は '#' を書き込んで終了します。

#include <iostream>
#include <vector>
#include <cmath>

std::vector<std::vector<char>> grid;

void generate_carpet(int k, int r, int c) {
    if (k == 0) {
        grid[r][c] = '#';
        return;
    }

    int sub_size = std::pow(3, k - 1);
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (i == 1 && j == 1) {
                for (int dr = 0; dr < sub_size; ++dr) {
                    for (int dc = 0; dc < sub_size; ++dc) {
                        grid[r + sub_size + dr][c + sub_size + dc] = '.';
                    }
                }
            } else {
                generate_carpet(k - 1, r + i * sub_size, c + j * sub_size);
            }
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    int total_size = std::pow(3, n);
    grid.assign(total_size, std::vector<char>(total_size));

    generate_carpet(n, 0, 0);

    for (int i = 0; i < total_size; ++i) {
        for (int j = 0; j < total_size; ++j) {
            std::cout << grid[i][j];
        }
        std::cout << '\n';
    }
    return 0;
}

問題D: 88888888

整数 $N$ を $N$ 回並べてできる巨大な整数を $998244353$ で割った余りを求める問題です。 例えば $N=12$ なら、$121212...12$（12が12回繰り返される）となります。

$N$ の桁数を $d$ とすると、求める値は以下の等比数列の和として表せます： $$N \times \sum_{i=0}^{N-1} (10^d)^i = N \times \frac{(10^d)^N - 1}{10^d - 1} \pmod{998244353}$$ この計算には、繰り返し二乗法によるべき乗計算と、フェルマーの小定理を用いた逆元の計算が必要です。

#include <iostream>
#include <string>

using namespace std;

typedef long long ll;
const ll MOD = 998244353;

ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

ll modInverse(ll n) {
    return power(n, MOD - 2);
}

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

    string s = to_string(n);
    ll d = s.length();

    ll ratio = power(10, d);
    
    // 等比数列の和: n * (ratio^n - 1) / (ratio - 1)
    ll numerator = (power(ratio, n) - 1 + MOD) % MOD;
    ll denominator = (ratio - 1 + MOD) % MOD;
    
    ll result = (n % MOD) * numerator % MOD;
    result = result * modInverse(denominator) % MOD;

    cout << result << endl;

    return 0;
}