【ABC357】AtCoder Beginner Contest 357【C++】

コンテスト名

サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

コンテストURL

https://atcoder.jp/contests/abc357

開催日

2024/06/08 21:00-22:40

---

A: Sanitize Hands

解法

• $M$ から $H_i$ を順番に引いて、 $M$ が $0$ 以上であれば $i$ 人目の宇宙人はすべての手を消毒できる

ABC357A.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

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

    int num = 0;
    while(m-H[num]>=0 && num<n){
        m -= H[num];
        num++;
    }

    cout << num << endl;
    return 0;
}

B: Uppercase and Lowercase

解法

• 文字列 $S$ に含まれる小文字の数を数えて判定する
• 'A' $<$ 'Z' $<$ 'a' $<$ 'z' を利用する
• transform(S.begin(), S.end(), S.begin(), ::tolower) transform(S.begin(), S.end(), S.begin(), ::toupper) で変換する

ABC357B.cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

    int lowercnt = 0;
    for(int i=0; i<s.size(); i++){
        if(s[i]>='a'){
            lowercnt++;
        }
    }

    if(lowercnt>s.size()/2){
        transform(s.begin(), s.end(), s.begin(), ::tolower);
    }else{
        transform(s.begin(), s.end(), s.begin(), ::toupper);
    }

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

C: Sierpinski carpet

解法

• 再帰的に解く
• カーペットのレベル $K$ と左上の座標を引数とした再帰関数を考える
• 中央のブロックは $3^{K-1} \times 3^{K-1}$ のすべて白いブロック
• 中央以外の 8 つのブロックはレベル $K - 1$ のカーペット
• マスの色は vector<vector<char>> に記録する

ABC357C.cpp

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<vector<char>> G;

void allwhite(int num, int x, int y){
    for(int i=x; i<x+pow(3, num-1); i++){
        for(int j=y; j<y+pow(3, num-1); j++){
            G[i][j] = '.';
        }
    }
}

void f(int num, int x, int y){
    if(num==0){
        G[x][y] = '#';
        return;
    }

    for(int i=x; i<x+3; i++){
        for(int j=y; j<y+3; j++){
            if(i==x+1 && j==y+1){
                allwhite(num, x+pow(3, num-1), y+pow(3, num-1));
            }else{
                f(num-1, x+(i-x)*pow(3, num-1), y+(j-y)*pow(3, num-1));
            }
        }
    }
}

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

    G.assign(pow(3, n), vector<char>(pow(3, n)));
    f(n, 0, 0);

    for(int i=0; i<pow(3, n); i++){
        for(int j=0; j<pow(3, n); j++){
            cout << G[i][j];
        }
        cout << '\n';
    }

    return 0;
}

D: 88888888

解法

• 等比数列の和を求める
• $N$ の桁数を $K$ とおくと、 $V_N = N(1 + 10^K + 10^{2K} + \cdots 10^{(N - 1)K})$ である
• $(1 + 10^K + 10^{2K} + \cdots 10^{(N - 1)K})$ は初項 $1$ 、公比 $10^K$ 、項数 $N$ の等比数列の和だから、 $V_N = N \times \frac{(10^{KN} - 1)}{10^K - 1}$
• 分子 $N(10^{KN} - 1)$ に、分母 $10^K - 1$ の $(\text{mod} \ 998244353)$ における逆元をかけて求める
  • $10^K - 1$ は 素数 $998244353$ で割り切れない整数であるため、 $X \times (10^K - 1) \equiv 1 \ (\text{mod} \ 998244353)$ を満たす $X$ は一意に存在する

ABC357D.cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

long long int modpow(long long int a, long long int n, long long int m){
	long long int res = 1;
	while(n>0){
		if(n&1){
            res = res * a % m;
        }
		a = a * a % m;
		n >>= 1;
	}
	return res;
}

long long int modinv(long long a, long long m){
	long long int b = m, u = 1, v = 0;
	while(b){
		long long int t = a / b;
		a -= t * b;
        swap(a, b);
		u -= t * v;
        swap(u, v);
	}
	u %= m; 
	if(u<0){
        u += m;
    }
	return u;
}

int main(){
    const int MOD = 998244353;

    long long int n;
    cin >> n;

    string s = to_string(n);
    int k = s.size();

    long long int bunshi = (n%MOD * (modpow(modpow(10, n, MOD), k, MOD) - 1)) % MOD;
    long long int bunboinv = modinv(modpow(10, k, MOD) - 1, MOD);

    cout << (bunshi * bunboinv) % MOD << endl;
    return 0;
}