ABC 119

A

A - Still TBD

  • 2019年より後か、2019年かつ5月以降ならHeiseiを出力し、それ以外ならTBDを出力する
#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)
using ll = long long int;
 
using namespace std;
 
int main() {
  string S;
  cin >> S;
  stringstream ss(S);
  int y, m, d;
  char c;
  ss >> y >> c >> m >> c >> d;
  if (y > 2019 || (y == 2019 && m >= 5))
    cout << "TBD" << endl;
  else
    cout << "Heisei" << endl;
}

Submission #5195221 - AtCoder Beginner Contest 119

B

B - Digital Gifts

  • JPYならそのまま、BTCなら日本円に換算してから総和を取る
#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)
using ll = long long int;
 
using namespace std;
 
int main() {
  int N;
  cin >> N;
  double ans = 0.0;
  REP(i, N) {
    double x;
    string u;
    cin >> x >> u;
    if (u == "JPY")
      ans += x;
    else
      ans += x * 380000.0;
  }
  cout << ans << endl;
}

Submission #5196369 - AtCoder Beginner Contest 119

C

C - Synthetic Kadomatsu

  • 自力では解法が思いつかなかった
  • 合成魔法の使い方を全探索すればよい
  • 長さ0の竹を3本用意しておき、合成魔法を3本の竹のどれかに対して使うと考えると書きやすい
    • 初回の合成魔法をコスト0とすれば同じ結果になる（dfs関数内で返り値を-30しているのはこの処理）
    • 3本の初期竹に対して、少なくとも1回は合成魔法を使う必要があることに注意
#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)
using ll = long long int;
 
using namespace std;
 
vector<int> l;
int N, A, B, C;
 
int dfs(int mp, int a, int b, int c, int n) {
  int tmp = numeric_limits<int>::max() >> 1;
  if (n == (int)l.size()) {
    if ((a == 0) || (b == 0) || (c == 0)) {
      return tmp;
    } else {
      return mp + abs(A - a) + abs(B - b) + abs(C - c) - 30;
    }
  }
  tmp = min(tmp, dfs(mp + 10, a + l[n], b, c, n + 1));
  tmp = min(tmp, dfs(mp + 10, a, b + l[n], c, n + 1));
  tmp = min(tmp, dfs(mp + 10, a, b, c + l[n], n + 1));
  tmp = min(tmp, dfs(mp, a, b, c, n + 1));
  return tmp;
}
 
int main() {
  cin >> N >> A >> B >> C;
  l.resize(N);
  REP(i, N) cin >> l[i];
  cout << dfs(0, 0, 0, 0, 0) << endl;
}

Submission #5220254 - AtCoder Beginner Contest 119

D

  • sとtをソートしておく
  • x[i]よりも左にある神社・寺のうち最も右にあるものの添字（l, l2とした）を二分探索で求める
  • 最小の移動距離は次のうちのどれか
    • 左側にある神社・寺のうち遠い方までの距離 (max(x[i] - t[l2], x[i] - s[l]))
    • 左側の神社に行ってから右側の寺に行くまでの距離 ((x[i] - s[l]) + (t[l2 + 1] - s[l]))
    • 左側の寺に行ってから右側の神社に行くまでの距離 ((x[i] - t[l2]) + (s[l + 1] - t[l2]))
    • 右側の神社に行ってから左側の寺に行くまでの距離 ((s[l + 1] - x[i]) + (s[l + 1] - t[l2]))
    • 右側の寺に行ってから左側の神社に行くまでの距離 ((t[l2 + 1] - x[i]) + (t[l2 + 1] - s[l]))
    • 右側にある神社・寺のうち遠い方までの距離 (max(s[l + 1] - x[i], t[l2 + 1] - x[i]))
  • sとtの左端と右端に遠い距離の神社・寺をいれておくと端の処理が楽
#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)
using ll = long long int;
 
using namespace std;
 
int main() {
  ll A, B, Q;
  cin >> A >> B >> Q;
  vector<ll> s(A + 2), t(B + 2), x(Q);
  s[0] = -1e12;
  s[A + 1] = 1e12;
  t[0] = -1e12;
  t[B + 1] = 1e12;
  REP(i, A) cin >> s[i + 1];
  REP(i, B) cin >> t[i + 1];
  REP(i, Q) cin >> x[i];
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  REP(i, Q) {
    int l = 0, r = A + 2;
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (s[mid] <= x[i])
        l = mid;
      else
        r = mid;
    }
    int l2 = 0, r2 = B + 2;
    while (r2 - l2 > 1) {
      int mid = (l2 + r2) / 2;
      if (t[mid] <= x[i])
        l2 = mid;
      else
        r2 = mid;
    }
    cout << min({max(x[i] - t[l2], x[i] - s[l]),
                 (x[i] - s[l]) + (t[l2 + 1] - s[l]),
                 (x[i] - t[l2]) + (s[l + 1] - t[l2]),
                 (s[l + 1] - x[i]) + (s[l + 1] - t[l2]),
                 (t[l2 + 1] - x[i]) + (t[l2 + 1] - s[l]),
                 max(s[l + 1] - x[i], t[l2 + 1] - x[i])})
         << endl;
  }
}