Asa's Blog

ABC210

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.07.17. Last Modified on 2021.07.17.

今回は 3 完でした。そしてかなり時間を使ってしまいました。

問題概要

A

キャベツ 1 個$X$円。ただし$A+1$個目以降は 1 個$Y$円($X \gt Y$)。$N$個買うために必要な金額は?

B

$N$ 枚のカードの山札が文字列 $S$ として、上から順に与えられる。$S[i] = 0$なら「良いカード」で、$S[i] = 1$なら「悪いカード」。
2 人で交互に一番上のカードを引くと、どちらが最初に「悪いカード」を引く?

C

$N$ 個のキャンディが 1 列に並んでいる。$i$番目のキャンディには色$c_i$がついている($1 \le c_i \le 10^9$)。
連続して並んだ$K$個のキャンディをもらうとき、もらうキャンディに含まれる色の種類数の最大値は?

提出

全体の提出:a01sa01to の提出 - AtCoder Beginner Contest 210

A

提出 #24282806 - AtCoder Beginner Contest 210

まず、$ans = X \cdot N$にします。そして、$N \gt A$なら、割引額である (1 個あたりの差額)×(割引対象個数) の $(X-Y)(N-A)$を引きました。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, a, x, y;
  cin >> n >> a >> x >> y;
  int ans = x * n;
  if (n > a) { ans -= (x - y) * (n - a); }
  cout << ans << endl;
  return 0;
}

いろいろな方法を試してみた結果、サンプルでずれました。
この解法になったとき、一応不安だったのでコンパイル&テストしたので、かなり時間を食ってしまい、提出時刻は 21:04:17。これはまずい。

B

B - Bouzu Mekuri

$N \le 10^5$なので、そのまま順番に試していって、初めて1となった時の$i$が奇数か偶数かで判定すれば OK です。
前回の B 問題でもやりましたが、問題文中では商品は 1-indexed ですがプログラム中では 0-indexed なので、「偶数番目」を「i が奇数の時」とする必要があるので注意。

#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << fixed << setprecision(15);
  int n;
  string s;
  cin >> n >> s;
  loop(i, n) {
    if (s[i] == '1') {
      cout << (i % 2 ? "Aoki" : "Takahashi") << endl;
      return 0;
    }
  }
}

A 問題の影響で、提出時刻は 21:06:42。

C

提出 #24323800 - AtCoder Beginner Contest 210

これはいろいろと試行錯誤しました。「vectorだとuniqueとるとおかしくなるよなー」とか、「setだと要素が全部消えちゃった!」とか、「毎回チェックしたらTLEした」とかしました。

結果たどり着いた解法は、以下の通りです。

  • $c_i$を multiset と set の両方に保存する
  • $i \ge K$なら、multiset から$c_{i-k}$を消す。
  • 消した後、$c_{i-k}$の個数が 0 なら set からも消す。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> ll1d;

int main() {
  ll n, k;
  ll ans = 0;
  cin >> n >> k;
  ll1d c(n, 0);
  multiset<ll> cont;
  set<ll> con;
  loop(i, n) {
    cin >> c[i];
  }
  loop(i, n) {
    if (i >= k) {
      auto itr = cont.find(c[i - k]);
      cont.erase(itr);
      if (cont.count(c[i - k]) == 0) {
        con.erase(c[i - k]);
      }
    }
    cont.insert(c[i]);
    con.insert(c[i]);
    ans = max(ans, (ll) con.size());
  }
  cout << ans << endl;
  return 0;
}

かなり効率が悪いです。
実は map の仕様についてあまり知らず、「map[10000]とか初期化せずにやったらエラー起きそう」とか、「map[3] = 0にしたのにmap.size()したら消えてない!?」とか言ってました。

AC 解法提出時刻は 22:25:51 です。D 問題は当然 15 分では解けず終いでした。

結果

はい、逆ボーダーからのダウンです。
全体的にもっと早く解けていれば D 問題も解けて、入緑したかもしれない。(結果論)

レート計算機で計算してみた結果、次回で入緑するにはパフォが 1000 くらい必要だとわかったので、今回はフラグ建てないことにします。
爆速で C まで解ければいけるかもしれない(フラグ建築)。

今回なんか難しかった気が...。

keyboard_arrow_up