ABC 123
Editorialが丁寧に書かれていてよかった。
A
- アンテナeとアンテナaが最も離れているので
e-a
だけ調べる
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int a, b, c, d, e, k; cin >> a >> b >> c >> d >> e >> k; if (e - a > k) cout << ":(" << endl; else cout << "Yay!" << endl; }
Submission #5124500 - AtCoder Beginner Contest 123
B
- 10で割った余りが一番小さいものを最後に注文するのが最短。
- 解説のコードが綺麗だった
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int f(int n) { return (n % 10 == 0 ? n : n / 10 * 10 + 10); } int main() { int A, B, C, D, E; cin >> A >> B >> C >> D >> E; int ans = numeric_limits<int>::max(); ans = min(ans, f(A) + f(B) + f(C) + f(D) + E); ans = min(ans, f(A) + f(B) + f(C) + f(E) + D); ans = min(ans, f(A) + f(B) + f(D) + f(E) + C); ans = min(ans, f(A) + f(C) + f(D) + f(E) + B); ans = min(ans, f(B) + f(C) + f(D) + f(E) + A); cout << ans << endl; }
Submission #5124543 - AtCoder Beginner Contest 123
C
- 一番運搬人数が少ないところを通るのにかかる時間+4が答え
- C++11以降ではstd::maxの引数に
initializer_list
が使えることを知らなかったのでこういう書き方をした。
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; ll f(ll n, ll p) { return (n % p == 0 ? n / p : n / p + 1); } int main() { ll N, A, B, C, D, E; cin >> N >> A >> B >> C >> D >> E; ll ans = max(f(N, A), f(N, B)); ans = max(ans, f(N, C)); ans = max(ans, f(N, D)); ans = max(ans, f(N, E)); cout << ans + 4 << endl; }
Submission #5124621 - AtCoder Beginner Contest 123
D
- 解けなかったので解説を見た。
- A, B, Cを大きい順にソートして
(i+1)*(j+1)*(k+1) <= K
を満たすi
,j
,k
についてA[i]+B[j]+C[k]
を求めて大きい順にソートすれば上位K
個が必ず求まる。 - 言われればそうなんだけど気が付かないものだなぁ
- 解説にはpriority-queueを使ったより高速な解法など4通りの解法が解説されていて良い。
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; ll A[1001], B[1001], C[1001]; int main() { int X, Y, Z, K; cin >> X >> Y >> Z >> K; REP(i, X) cin >> A[i]; REP(i, Y) cin >> B[i]; REP(i, Z) cin >> C[i]; sort(A, A + X, greater<ll>()); sort(B, B + Y, greater<ll>()); sort(C, C + Z, greater<ll>()); vector<ll> s; REP(i, X) { REP(j, Y) { REP(k, Z) { if ((i + 1) * (j + 1) * (k + 1) <= K) s.push_back(A[i] + B[j] + C[k]); } } } sort(s.begin(), s.end(), greater<ll>()); REP(i, K) cout << s[i] << endl; }
Submission #5125010 - AtCoder Beginner Contest 123
追記: priority-queueを使ったバージョン(参考: AtCoder ABC 123 D - Cake 123 (400 点) - けんちょんの競プロ精進記録)
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; using Data = pair<long long, tuple<ll, ll, ll>>; ll A[1001], B[1001], C[1001]; int main() { int X, Y, Z, K; cin >> X >> Y >> Z >> K; REP(i, X) cin >> A[i]; REP(i, Y) cin >> B[i]; REP(i, Z) cin >> C[i]; sort(A, A + X, greater<ll>()); sort(B, B + Y, greater<ll>()); sort(C, C + Z, greater<ll>()); priority_queue<Data> que; set<tuple<int, int, int>> se; que.push(Data(A[0] + B[0] + C[0], make_tuple(0, 0, 0))); REP(i, K) { auto e = que.top(); que.pop(); cout << e.first << endl; ll idxA = std::get<0>(e.second); ll idxB = std::get<1>(e.second); ll idxC = std::get<2>(e.second); if (idxA + 1 < X) { ll sum = e.first - A[idxA] + A[idxA + 1]; tuple<int, int, int> t = make_tuple(idxA + 1, idxB, idxC); Data d = Data(sum, t); if (!se.count(t)) { se.insert(t); que.push(d); } } if (idxB + 1 < Y) { ll sum = e.first - B[idxB] + B[idxB + 1]; tuple<int, int, int> t = make_tuple(idxA, idxB + 1, idxC); Data d = Data(sum, t); if (!se.count(t)) { se.insert(t); que.push(d); } } if (idxC + 1 < Z) { ll sum = e.first - C[idxC] + C[idxC + 1]; tuple<int, int, int> t = make_tuple(idxA, idxB, idxC + 1); Data d = Data(sum, t); if (!se.count(t)) { se.insert(t); que.push(d); } } } }
Submission #5125525 - AtCoder Beginner Contest 123
gcc 5と6以降でタプルの仕様が違うことを知らなかったので手元でコンパイル通るコードがジャッジシステム上ではコンパイルエラーになった。
std::tuple::tuple - cppreference.com によるとC++11に対してDefect Reportが出ていて、仕様が変更されたらしい。
make_tuple
を常に使うようにしたほうが安全だろう。