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; }