ABC 123

Editorialが丁寧に書かれていてよかった。

A

A - Five Antennas

  • アンテナ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

B - Five Dishes

  • 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

C - Five Transportations

  • 一番運搬人数が少ないところを通るのにかかる時間+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

D - Cake 123

  • 解けなかったので解説を見た。
  • 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を常に使うようにしたほうが安全だろう。