Asa's Blog

ABC212

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.07.31. Last Modified on 2021.07.31.

8 問体制になっても、相変わらず 3 完ですよ。はい。
D も解けたけど、謎の TLE(解決済)したので間に合わなかった…。

問題概要

A

$A$グラムの純金と$B$グラムの純銀。$A \gt 0 \And B = 0$ならGold、$A = 0 \And B \gt 0$ならSilver、$A \gt 0 \And B \gt 0$ならAlloyと出力。

B

4 桁の暗証番号 $X_1 X_2 X_3 X_4$。4 桁が同じ数字か、すべての$i (1,2,3)$について$X_{i+1}$が$X_i$の次の数字なら、Weak。そうでなければStrong

C

2 つの数列から 1 つずつ要素を選んだときの 2 つの値の差の最小値($\displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert$) を求める

D

$Q$個のクエリ $P_i, X_i$。

  • $P_i=1$: 袋に整数$X_i$を追加
  • $P_i=2$: 袋に入っているすべての数字について、$X_i$を足す
  • $P_i=3$: 袋に入っている最小の数を取り出し、その数字を出力して捨てる

提出

A

提出 #24644697 - AtCoder Beginner Contest 212

そのまま if 文で場合分けすれば OK。

#include <bits/stdc++.h>
using namespace std;
int main() {
  cout << fixed << setprecision(15);
  int a, b;
  cin >> a >> b;
  if (a > 0 && b == 0) {
    cout << "Gold" << endl;
  }
  else if (a == 0 && b > 0) {
    cout << "Silver" << endl;
  }
  else {
    cout << "Alloy" << endl;
  }
  return 0;
}

提出時刻は 21:01:11。これまでと変わらずって感じ。

B

提出 #24656788 - AtCoder Beginner Contest 212

問題文を言い換えると、 「i=0 ~ 2 で、$X_{i+1}=(X_i+1) \mathrm{mod} 10$か、$X_{i+1}=X_i$のどちらか一方になっていれば Weak」になります。
私は vector<int>を用いて計算しました。

#include <bits/stdc++.h>
using namespace std;
#define loop(i, n) for (ll i = 0; i < n; i++)

int main() {
  cout << fixed << setprecision(15);
  string s;
  cin >> s;
  vector<int> v(3, 0);
  loop(i, 3) {
    if (s[i + 1] - '0' == (s[i] - '0' + 1) % 10) {
      v[i] = 1;
    }
    else if (s[i] == s[i + 1]) {
      v[i] = 2;
    }
  }
  bool isStrong = true;
  if (v[0] == v[1] && v[2] == v[0] && v[0] != 0) {
    isStrong = false;
  }
  cout << (isStrong ? "Strong" : "Weak") << endl;
  return 0;
}

もっと簡潔な方法として、解説にあった「i=0 ~ 2 のいずれかで、$X_{i+1}=(X_i+1) \mathrm{mod} 10$か、$X_{i+1}=X_i$の両方になっていなければ Strong」(私の対偶?)とすることで、「どちらか一方」を無視できるので、かなり場合分けが簡単になっていました。

提出時刻は 21:11:41。最初ちょっと悩んだので遅れてしまった…。

C

提出 #24664712 - AtCoder Beginner Contest 212

それぞれをソートすれば、かなり計算量を減らせました。私の解説より、公式解説がめちゃくちゃわかりやすいと思うので、解説 - AtCoder Beginner Contest 212 をご覧いただければ…。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> ll1d;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define all(vec) vec.begin(), vec.end()

int main() {
  cout << fixed << setprecision(15);
  ll n, m;
  cin >> n >> m;
  ll1d a(n), b(m);
  loop(i, n) { cin >> a[i]; }
  loop(i, m) { cin >> b[i]; }
  sort(all(a));
  sort(all(b));
  ll minim = 1e9;
  ll i = 0, j = 0;
  while (i < n && j < m) {
    if (a[i] - b[j] >= 0) {
      minim = min(minim, a[i] - b[j]);
      j++;
    }
    else {
      minim = min(minim, b[j] - a[i]);
      i++;
    }
  }
  cout << minim << endl;
  return 0;
}

最初$A_i - B_j \ge 0$ではないときに、minim を更新しないコードを提出してしまい、1 ペナ。
提出時刻は 21:23:01 ですが、ペナルティにより+5 分…。

D

提出 #24691944 - AtCoder Beginner Contest 212

袋にいれていちいちソートしても間に合わないので、priority_queueを使いました。また、いちいちすべてに「$X_i$を足す」ことはできないので、これまで足された数を$Add$に記録しておき、「$X_i$を追加」を「$X_i - Add$を追加」にしておくことで、計算量は大幅に減ります。

#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

typedef long long ll;

#define loop(i, n) for (ll i = 0; i < n; i++)
#define all(vec) vec.begin(), vec.end()

int main() {
  cout << fixed << setprecision(15);
  ll q;
  cin >> q;
  priority_queue<ll, ll1d, greater<ll>> pq;
  ll add = 0;
  loop(_, q) {
    ll a, b;
    cin >> a;
    if (a == 3) {
      ll v = pq.top();
      pq.pop();
      cout << v + add << endl;
      continue;
    }
    cin >> b;
    if (a == 1) {
      pq.push(b - add);
    }
    else {
      add += b;
    }
  }
  return 0;
}

しかし、コンテスト中に提出したコードでは TLE が出ました。
何がまずかったのか。提出 #24669623のファイル先頭にある、「#define _GLIBCXX_DEBUG」です。
一応デバッグ用に追加したものなんですが、ファイルをそのままコピペして提出しているため、要は「デバッグ用のコードをそのまま提出している」という状況でした。
これまでまったく問題がなかったのですが、今回、この 1 行があることで大幅に実行時間を食ってしまっていたようです。
これを消した結果(提出 #24691944)、実行時間は 193ms と、大幅に減りました。

結果と感想

はい、下がりました。
ツイートの通り、#define _GLIBCXX_DEBUGのせいで下がったといっても過言ではありません。
(1 回ミスりましたが)実質正解のコードを 21:32:24 に提出しており、コンテスト全体のペナルティ加算の提出時間は「42:24」になっていたはずだったためです。
このとき Perf は 1146 になっていたため、まじで#define _GLIBCXX_DEBUGは許しません。

とはいっても自分の無知のせいなので、今後のコンパイルでは、ソースコードではなくコンパイルオプションとして-D_GLIBCXX_DEBUGを追加することにします…。

次は 5 完を目指します…。

Hello, 8問体制のABC...!

keyboard_arrow_up