AtCoder Beginner Contest 280

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder

結果

A - Pawn on a Grid:AC(1:58)
B - Inverse Prefix Sum:AC(8:09)
C - Extra Character:AC(11:21)
D - Factorial and Multiple:WA

A - Pawn on a Grid

$${H}$$行$${W}$$列のマス目がある
$${S_{i,j}}$$が「#」のとき$${i}$$行$${j}$$列にコマが置かれており、「.」のとき置かれていない
マス目にコマがいくつ置かれているかを求める問題

自分の回答

int main(){
  int H, W;
  cin >> H >> W;

  int ans = 0;
  char C;
  for(int i = 0; i < H * W; i++){
    cin >> C;
    if(C == '#'){
      ans++;
    }
  }

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

そのまま

公式解説

省略

B - Inverse Prefix Sum

長さ$${N}$$の数列$${S=(S_{1},S_{2},…,S_{N})}$$が与えられ、$${S_{k}=A_{1}+A_{2}+…+A_{k}}$$となる数列$${A=(A_{1},A_{2},…,A_{N})}$$を求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }

  printf("%d", S[0]);
  for(int i = 1; i < N; i++){
    printf(" %d", S[i] - S[i - 1]);
  }
  printf("\n");
}

$${A}$$は初項$${S_{1}}$$、$${i}$$項目は$${S_{i}-S_{i-1}}$$なためそのまま

公式解説

int main(){
	int n;
	scanf("%d",&n);
	int s[11];
	s[0]=0;
	for(int i=1;i<=n;i++)scanf("%d",s+i);

	int a[10];
	for(int i=0;i<n;i++)a[i]=s[i+1]-s[i];
	
	for(int i=0;i<n;i++)printf("%d%c",a[i],i==n-1?'\n':' ');
}

https://atcoder.jp/contests/abc280/editorial/5304より

そうか$${S_{0}=0}$$とすれば処理を統一できるのか

なるほど

C - Extra Characte

文字列$${S,T}$$が与えられ、$${T}$$は$${S}$$に1文字挿入して作られたものである
挿入された文字が$${T}$$の何文字目かを求める問題

自分の回答

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

  for(int i = 0; i < S.size(); i++){
    if(S[i] != T[i]){
      printf("%d\n", i + 1);
      return 0;
    }
  }
  printf("%d\n",T.size());
}

先頭から比較して違うのがあったらその番号を出力
S.size()でやって最後まで無かったら$${T}$$の最後なためT.size()を出力

公式解説

省略

D - Factorial and Multiple

2以上の整数$${K}$$が与えられ、$${N!}$$が$${K}$$の倍数となる正の整数$${N}$$を求める問題

自分の回答

とりあえず素因数分解すればいいのはすぐ見えたけどその先が上手くいかなかった
$${K}$$の素因数の指数が全て1ならば最大の素因数が答えになるからいいんだけどそうじゃない場合、それを素数でない数に下から埋めていくイメージはあるんだけどプログラムに固められなかった

公式解説

int main() {
	long long k,p,a,n,x,ans=1;
	cin >> k;
	for(p=2;(p*p)<=k;p++){
		a=0;
		while(k%p==0)k /= p, a++;
		n=0;
		while(a>0){
			n+=p;
			x=n;
			while(x%p==0)x /= p,a--;
		}
		ans=max(ans,n);
	}
	ans=max(ans,k);
	cout << ans <<endl;
	return 0;
}

https://atcoder.jp/contests/abc280/editorial/5330より

考え方は合ってたのか
素因数分解と同時に進めればいいのか

なるほど