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

  • stをソートしておく
  • 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]))
  • stの左端と右端に遠い距離の神社・寺をいれておくと端の処理が楽
#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;
  }
}

ABC 120

本日の勝敗: int型の敗北

A

A - Favorite Sound

  • B/ACの小さい方
#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;
  cin >> A >> B >> C;
  cout << min(B / A, C) << endl;
}

B

B - K-th Common Divisor

  • 制約が緩いので何も考えずに公約数を全部求めてK番目に大きいものを出力した
#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, K;
  cin >> A >> B >> K;
  vector<int> n;
  FOR(i, 1, min(A, B) + 1) {
    if (A % i == 0 && B % i == 0) n.push_back(i);
  }
  cout << n[n.size() - K] << endl;
}

C

C - Unification

  • 01の個数のうち小さい方の2倍
  • 片方が残っていたら必ずどこかで隣り合うので、片方が消滅するまで取り除くことができるから
#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() {
  string S;
  cin >> S;
  size_t cnt = 0;
  REP(i, S.size()) {
    if (S[i] == '0') cnt++;
  }
  cout << 2 * min(cnt, S.size() - cnt) << endl;
}

D

D - Decayed Bridges

  • UnionFindを知っていますか?というだけの問題……のはずだった
  • 終わりから考えて、最初バラバラだった島をつないでいく方針で考える
  • 端が全て崩落しているときの不便さはN*(N-1)/2
  • 既に連結している島をつないでも不便さは変わらない
  • 連結していない島をつなぐと、それぞれの島群の島数の積だけ不便さが減る
  • 方針は一瞬で思いついたのだが、N<=10^5なのでN*(N-1)/2はint型に収まらないのにNをint型で宣言していたので切り捨てられてしまいWAを連発してしまった。他の人の解説ブログを見てNの型をlong longに書き直しただけでACだった。
#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;

struct UnionFind {
  vector<int> par;
  vector<int> rank;

  UnionFind(int n) : par(n), rank(n, 1) {
    for (int i = 0; i < n; ++i)
      par[i] = i;
  }

  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) swap(x, y);
    par[y] = x;
    rank[x] += rank[y];
  }

  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -rank[find(x)]; }
};

int main() {
  ll N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  vector<ll> ans(M);
  REP(i, M) {
    cin >> A[i] >> B[i];
    A[i]--;
    B[i]--;
  }
  UnionFind uf(N);
  ans[M - 1] = N * (N - 1) / 2;
  for (int i = M - 1; i > 0; --i) {
    if (uf.same(A[i], B[i])) {
      ans[i - 1] = ans[i];
      continue;
    }
    ans[i - 1] = ans[i] - uf.size(A[i]) * uf.size(B[i]);
    uf.unite(A[i], B[i]);
  }
  REP(i, M) cout << ans[i] << endl;
}

ABC 125

A

A - Biscuit Generator

  • B*T/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, T;
  cin >> A >> B >> T;
  cout << B * (T / A) << endl;
}

Submission #5139315 - AtCoder Beginner Contest 125

B

B - Resale

  • V[i]-C[i] > 0となるV[i]-C[i]の総和
#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 N;
  vector<int> V(N), C(N);
  cin >> N;
  REP(i, N) cin >> V[i];
  REP(i, N) cin >> C[i];
 
  int ans = 0;
  REP(i, N) {
    if (V[i] > C[i]) ans += V[i] - C[i];
  }
  cout << ans << endl;
}

Submission #5141279 - AtCoder Beginner Contest 125

C

C - GCD on Blackboard

  • 左端から順・右端から順に最大公約数を取った配列をL[i], R[i]として持っておく
  • 左端を除いた最大公約数はR[1], 右端を除いた最大公約数はL[N-2], 端以外のi番目を除いた最大公約数はgcd(L[i-1], R[i+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)
typedef long long int ll;
 
using namespace std;
 
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
 
int main() {
  int N;
  cin >> N;
  vector<int> A(N), L(N), R(N);
  REP(i, N) cin >> A[i];
  L[0] = A[0];
  R[N - 1] = A[N - 1];
  FOR(i, 1, N) {
    L[i] = gcd(L[i - 1], A[i]);
    R[N - 1 - i] = gcd(R[N - i], A[N - 1 - i]);
  }
  ll ans = max(R[1], L[N - 2]);
  FOR(i, 1, N - 1) { ans = max(ans, gcd(L[i - 1], R[i + 1])); }
  cout << ans << endl;
}

D

D - Flipping Signs

  • 相変わらずDが解けない
  • dp[i][0]iを選んで反転させない場合、dp[i][1]iを選んで反転させた場合の最大値とする。
  • このときdp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]-A[i]), dp[i+1][1] = max(dp[i][0]-A[i], dp[i][1]+A[i])になる。
    • iを選んで操作しないとき、i-1を選んで操作していなかったらiはそのままで、i-1を操作していたらiは反転している。
    • iを選んで操作するとき、i-1を選んで操作していなかったらiは反転していて、i-1を操作していたらiはそのまま。
  • 答えはdp[N][0]Nを選ぶことはできない)
#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 N;
ll dp[100001][2];
 
int main() {
  cin >> N;
  vector<ll> A(N);
  REP(i, N) { cin >> A[i]; }
  dp[0][0] = 0;
  dp[0][1] = numeric_limits<ll>::min() / 2;
  FOR(i, 1, N + 1) {
    dp[i][0] = max(dp[i - 1][0] + A[i - 1], dp[i - 1][1] - A[i - 1]);
    dp[i][1] = max(dp[i - 1][0] - A[i - 1], dp[i - 1][1] + A[i - 1]);
  }
  cout << dp[N][0] << endl;
}

Submission #5163661 - AtCoder Beginner Contest 125

ABC 121

A

A - White Cells

  • H * W - h * W - H * w + h * wが答え
#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 H, W, h, w;
  cin >> H >> W >> h >> w;
  cout << H * W - h * W - H * w + h * w << endl;
}

Submission #5133607 - AtCoder Beginner Contest 121

B

B - Can you solve this?

  • 問題文に書いてある条件を満たすかどうかを数える
#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 N, M, C;
  int B[21];
  int A[21][21];
 
  cin >> N >> M >> C;
  REP(i, M) cin >> B[i];
  REP(i, N) REP(j, M) cin >> A[i][j];
 
  int cnt = 0;
  REP(i, N) {
    int sum = C;
    REP(j, M) sum += A[i][j] * B[j];
    if (sum > 0) cnt++;
  }
  cout << cnt << endl;
}

Submission #5133653 - AtCoder Beginner Contest 121

C

C - Energy Drink Collector

  • 価格が安いものから貪欲
#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 N, M;
  vector<pair<ll, ll>> price;
  ll A, B;
 
  cin >> N >> M;
  REP(i, N) {
    cin >> A >> B;
    price.push_back(make_pair(A, B));
  }
 
  sort(price.begin(), price.end());
 
  ll ans = 0;
  REP(i, N) {
    if (M <= price[i].second) {
      ans += price[i].first * M;
      break;
    } else {
      ans += price[i].first * price[i].second;
      M -= price[i].second;
    }
  }
  cout << ans << endl;
}

D

  • 解けなかった
  • nが偶数のときn^(n-1)が1であることを利用すると4で割った余りに応じてf(0, n)は以下のようになる。
    • 0 → n
    • 1 →1
    • 2 → n^1
    • 3 → 0
  • f(A, B) = f(0, A-1) ^ f(0, B)を利用するとO(1)で解ける
    • AからBまでのiビットの総和は(0からBまでのiビットの総和) - (0からA-1までのiビットの総和)であり、その偶奇は両者のXORを取れば求まる。
#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) {
  int r = n % 4;
  if (r == 0) return n;
  else if (r == 1) return 1;
  else if (r == 2) return n ^ 1;
  else return 0;
}
 
int main() {
  ll A, B;
  cin >> A >> B;
  cout << (f(A - 1) ^ f(B)) << endl;
}

Submission #5134237 - AtCoder Beginner Contest 121

ABC 122

バイオインフォっぽかったがそんなことはなかった

A

A - Double Helix

  • 相補塩基を表示する
#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() {
  char b;
  cin >> b;
  if (b == 'A') cout << 'T' << endl;
  if (b == 'C') cout << 'G' << endl;
  if (b == 'G') cout << 'C' << endl;
  if (b == 'T') cout << 'A' << endl;
}

Submission #5129616 - AtCoder Beginner Contest 122

B

B - ATCoder

  • 各位置からACGTだけで書ける部分列の長さを求めて、その最大値
#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() {
  string S;
  cin >> S;
  int ans = 0;
  REP(i, S.size()) {
    int cnt = 0;
    FOR(j, i, S.size()) {
      if (S[j] == 'A' || S[j] == 'C' || S[j] == 'G' || S[j] == 'T')
        cnt++;
      else
        break;
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;
}

Submission #5129638 - AtCoder Beginner Contest 122

C

C - GeT AC

  • 一番左から数えたときにACがいくつあるかを持っておく
  • l番目とr番目の差が答え
#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 t[100001];
int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  int cnt = 0;
  FOR(i, 1, N) {
    if (S[i - 1] == 'A' && S[i] == 'C') cnt++;
    t[i] = cnt;
  }
  REP(i, Q) {
    int l, r;
    cin >> l >> r;
    cout << t[r - 1] - t[l - 1] << endl;
  }
}

Submission #5129691 - AtCoder Beginner Contest 122

D

D - We Like AGC

  • 自力では解けなかった
  • 「ABCのDはDPのD」という格言通りDPで解く
  • 最後の3文字を持っておいて、禁止文字列になる場合は遷移しないみたいな感じ(ここまでは分かったが正しく実装できなかった)
  • 解説に従ってメモ化再帰で実装
#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;
 
vector<map<string, int>> memo(101);
int N;
const int MOD = 1e9 + 7;
 
bool ok(string s) {
  if (s[0] == 'A' && s[2] == 'G' && s[3] == 'C') return false; // A?GC
  if (s[0] == 'A' && s[1] == 'G' && s[3] == 'C') return false; // AG?C
  if (s[0] == 'A' && s[1] == 'G' && s[2] == 'C') return false; // AGC?
  if (s[1] == 'A' && s[2] == 'G' && s[3] == 'C') return false; // ?AGC
  if (s[0] == 'G' && s[1] == 'A' && s[2] == 'C') return false; // GAC?
  if (s[1] == 'G' && s[2] == 'A' && s[3] == 'C') return false; // ?GAC
  if (s[0] == 'A' && s[1] == 'C' && s[2] == 'G') return false; // ACG?
  if (s[1] == 'A' && s[2] == 'C' && s[3] == 'G') return false; // ?ACG
  return true;
}
int dfs(int cur, string last3) {
  if (memo[cur].count(last3) == 1) {
    return memo[cur][last3];
  }
  if (cur == N) return 1;
  int ret = 0;
  char bases[] = {'A', 'C', 'G', 'T'};
  for (char c : bases) {
    if (ok(last3 + c)) {
      string s = last3.substr(1);
      s += c;
      ret = (ret + dfs(cur + 1, s)) % MOD;
    }
  }
  memo[cur][last3] = ret;
  return ret;
}
 
int main() {
  cin >> N;
  cout << dfs(0, "TTT") << endl;
}

Submission #5130760 - AtCoder Beginner Contest 122

DPによる解法はAtCoder ABC 122 D - We Like AGC (400 点) - けんちょんの競プロ精進記録が詳しい。

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を常に使うようにしたほうが安全だろう。

ABC 124

競技プログラミングは申請書からの逃避に役立つ。

A

A - Buttons

  • 1回目はABの大きい方の枚数のコインが手に入る
  • 2回目は縮小したボタンと押さなかった方のボタンの大きい方の枚数のコインが手に入る
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  int ans = max(A, B) + ((A > B) ? max(A-1, B) : max(A, B-1));
  cout << ans << endl;
}

Submission #5114332 - AtCoder Beginner Contest 124

B

B - Great Ocean View

  • i 番目までの旅館で最も高い旅館の高さを持っておき、それ以上の高さだったら眺められる旅館の数を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)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int N, H;
  cin >> N;
  int ans = 0;
  int highest = numeric_limits<int>::min();
  REP(i, N) {
    cin >> H;
    if(H >= highest) {
      highest = H;
      ans++;
    }
  }
  cout << ans << endl;
}

Submission #5114368 - AtCoder Beginner Contest 124

C

C - Coloring Colorfully

  • 0101010.... または 1010101... のどちらかにしかならないので、両方とのハミング距離を計算して小さい方
#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() {
  string S;
  cin >> S;
  int ans01 = 0;
  char c = '0';
  REP(i, S.size()) {
    if(S[i] != c) ans01++;
    c = (c == '0' ? '1' : '0');
  }
  c = '1';
  int ans10 = 0;
  REP(i, S.size()) {
    if(S[i] != c) ans10++;
    c = (c == '0' ? '1' : '0');
  }
  cout << min(ans01, ans10) << endl;
}

Submission #5114399 - AtCoder Beginner Contest 124

D

D - Handstand

  • 自力でやったらTLEだったので解説を見た
  • 01 が切り替わるところの位置を持っておいて、そこだけ調べる
  • その位置の文字が0なら2K個先の切り替わり位置、1なら2K+1個先の切り替わり位置との差を取ればその位置からスタートした最も長い連続逆立ち人数がO(1)で求まるからO(N)
  • これに気が付かなくていちいち数えていたのでO(N^2)になった
  • N <= 10^5 のときはO(N^2)だと間に合わないという認識をちゃんと持つ必要がある
  • 解説が1-indexedなので0-indexedにするために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)
typedef long long int ll;

using namespace std;

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  vector<int> I({1});
  FOR(i, 1, N) {
    if (S[i] != S[i - 1]) I.push_back(i + 1);
  }

  int ans = 0;
  int r = I.size();
  REP(k, r) {
    int cnt;
    if (S[I[k] - 1] == '0') {
      cnt = (k + 2 * K >= r ? N + 1 : I[k + 2 * K]) - I[k];
    } else {
      cnt = (k + 2 * K + 1 >= r ? N + 1 : I[k + 2 * K + 1]) - I[k];
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;
}

Submission #5115219 - AtCoder Beginner Contest 124

計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜 - Qiita によればループの回数を10^810^9回に抑えるようにする必要があるとのこと。以後意識する。