AtCoder Beginner Contest 357

SuntoryProgrammingContest2024（AtCoder Beginner Contest 357） - AtCoder

結果

A - Sanitize Hands : AC(3:28)
B - Uppercase and Lowercase : AC(10:47)
C - Sierpinski carpet : AC(47:29)
D - 88888888 : 提出無し
E - Reachability in Functional Graph : WA

A - Sanitize Hands

消毒液の入ったボトルがあり、そのボトルで$${M}$$本の手を消毒できる
$${N}$$人の宇宙人がいて、それぞれ手の本数は$${H_{i}}$$本である
順番に手を消毒していったとき、何人が全ての手を消毒できるか求める問題

自分の回答

int main() {
  int N, M;
  cin >> N >> M;

  int ans = 0;
  for(int i = 0; i < N; i++){
    int h;
    cin >> h;
    if(h <= M){
      ans++;
    }
    M -= h;
  }

  printf("%d\n", ans);
}

そのまま

公式解説

省略

B - Uppercase and Lowercase

英大文字と英小文字からなる文字列$${S}$$が与えられるため、その文字列において大文字の方が多ければ全て大文字に、小文字の方が多ければ全て小文字にして出力する問題

自分の回答

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

  int L = 0, U = 0;
  for(char c : S){
    if(islower(c)){
      L++;
    }
    else{
      U++;
    }
  }
  if(U > L){
    transform(S.begin(), S.end(), S.begin(), ::toupper);
  }
  else{
    transform(S.begin(), S.end(), S.begin(), ::tolower);
  }

  printf("%s\n", S.c_str());
}

そのまま

公式解説

省略

C - Sierpinski carpet

一辺が$${3^K}$$なシェルピンスキーのカーペットを出力する問題

自分の回答

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

  for(int i = 0; i < pow(3, N); i++){
    for(int j = 0; j < pow(3, N); j++){
      bool b = true;
      for(int k = 3; k <= pow(3, N); k *= 3){
        int l = k / 3, r = l * 2;
        if(l <= i % k && i % k < r && l <= j % k && j % k < r){
          b = false;
          break;
        }
      }
      printf(b ? "#" : ".");
    }
    printf("\n");
  }
}

全マス見て行ってそのマスが白かを判定する

フラクタルだから再帰でやるのが正攻法な気もする

公式解説

省略

D - 88888888

正整数$${N}$$が与えられる
$${N}$$を文字列として$${N}$$回連結した値を$${998244353}$$で割った余りを求める問題

自分の回答

正直一切とっかかりがわからなかった

公式解説

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

int main() {
	long long n,x;
	mint r = 1;

	cin>>n;
	x=n;
	while(x){
		x/=10;
		r*=mint(10);
	}
    
	mint ans=mint(n)*(r.pow(n)-mint(1))*((r-mint(1)).inv());
	cout<<(ans.val())<<endl;
	return 0;
}

https://atcoder.jp/contests/abc357/editorial/10183より

そうか結合した値は等比数列の和か
そしたらmodでの累乗をすれば求められるのか

なるほど

E - Reachability in Functional Graph

$${N}$$頂点$${N}$$辺の有向グラフがあり、各頂点からは頂点$${a_{i}}$$へ伸びている
頂点$${(u,v)}$$の組であり、頂点$${u}$$から頂点$${v}$$へ到達可能な組の個数を求める問題

自分の回答

各頂点がいくつの頂点へ行けるかを調べればその総和になると思ったから辺を逆向きにしていくつの頂点から来たかを調べたけどどうも探索の部分がちゃんとできていなかったっぽい

公式解説

Editorial - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）

やっぱり考え方は合ってたか
んでこのタイプのグラフ(Functional Graph)は連結成分に必ず閉路が一つあり、どの頂点から辿って行っても閉路に行きつく
閉路における各頂点の組み合わせ数はその閉路を構成する頂点数になって、他の頂点は閉路からの深さを足した分になる

なるほど