ABC 118

コンテストが終了してから参加した。

A問題

書いてあるとおりにやる。

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  if(B % A == 0) cout << A+B << endl;
  else cout << B-A << endl;
}

Submission #4292453 - AtCoder Beginner Contest 118

B問題

各食べ物についてそれを好んでいる人数を数えて、好んでいる人数がNである食べ物の種類数を出力する。

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int N, M;
  int cnt[31];
 
  cin >> N >> M;
 
  for(int i=0; i<M; ++i) cnt[i] = 0;
 
  for(int i=0; i<N; ++i) {
    int K;
    cin >> K;
    for(int j=0; j<K; ++j) {
      int A;
      cin >> A;
      cnt[A-1] += 1;
    }
  }
 
  int ans = 0;
  for(int i=0; i<M; ++i) {
    if(cnt[i] == N) ans++;
  }
  cout << ans << endl;
}

Submission #4292700 - AtCoder Beginner Contest 118

C問題

各モンスターの体力の最大公約数が答え。最終的な体力が最小になるように減らし合う操作はユークリッドの互除法と一致する。

#include <bits/stdc++.h>
 
using namespace std;
 
int gcd(int a, int b) {
  if(a < b) swap(a, b);
  if(b == 0) return a;
  return gcd(b, a%b);
}
 
int main() {
  int N;
  int A[100001];
  cin >> N;
  for(int i=0; i<N; ++i) {
    cin >> A[i];
  }
  int ans = gcd(A[0], A[1]);
  for(int i=2; i<N; ++i) {
      ans = gcd(ans, A[i]);
  }
  cout << ans << endl;
}

Submission #4292977 - AtCoder Beginner Contest 118

D問題

n本ちょうどのマッチ棒を使って作れる最大の数をdp[n]として動的計画法。 long long intに収まらないので数はstringで表現した。大小比較が面倒だが、桁数が違うなら桁数が大きい方・桁数が同じなら辞書順が大きい方が数として大きいことを利用した。

#include <bits/stdc++.h>
 
using namespace std;
 
int N, M;
int A[10];
int num[] = {-1, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string dp[10010];
 
 
int main() {
  cin >> N >> M;
  for(int i=0; i<M; ++i) {
    cin >> A[i];
  }
 
  for(int i=0; i<=N; ++i) {
    for(int j=0; j<M; ++j) {
      int n = num[A[j]];
      string tmp;
      stringstream ss;
 
      if(i < n) continue;
      if(i == n) ss << A[j];
      else if(dp[i-n] != "") ss << A[j] << dp[i-n];
      else continue;
      ss >> tmp;
      if(tmp.size() > dp[i].size() || (tmp.size() == dp[i].size() && tmp > dp[i])) {
        dp[i] = tmp;
      }
    }
  }
  cout << dp[N] << endl;
}

Submission #4293711 - AtCoder Beginner Contest 118