コンテスト名
サントリープログラミングコンテスト2024(AtCoder Beginner Contest 357)
コンテストURL
開催日
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;
}