ABC402の振り返り

歯茎痛い

A問題(diff:10)

やるだけ
大文字かの判定はisupper関数でできます。小文字の場合はislower。
計算量は $O(|S|)$ です。
ACコード(2ms)

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

int main() {
  string S, ans = "";
  cin >> S;
  for(char o : S) {
    if(isupper(o)) {
      ans += o;
    }
  }
  cout << ans << endl;
}

AC時間:1:18

B問題(diff:27)

問題名に従い、queueで殴る!
1種類目のクエリに関しては、キューに $X$ を入れ、2種類目のクエリに関しては、キューから取り出し、出力します。
計算量は $O(Q)$ です。
ACコード(1ms)

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

int main() {
  int Q;
  cin >> Q;
  queue<int> que;
  for(int i = 0; i < Q; i++) {
    int query;
    cin >> query;
    if(query - 1) {
      cout << que.front() << endl;
      que.pop();
    }
    else {
      int X;
      cin >> X, que.push(X);
    }
  }
}

AC時間:5:07

C問題(diff:337)

ABCではすぬけくん久々に見る…かも?
$\sum_{i = 1}^M K_i \le 3 \times 10^5$ から、各料理を順にみていくのでは間に合いませんが、すぬけくんが克服できた食材を含む料理を順にみていけばその回数の総和が $\sum_{i = 1}^M K_i$ になるため間に合います。
$A_{i,1}, \dots , A_{i,K_i}$ をsetなどで管理することで解くこともできますし、$K_i$ を管理して解くこともできます。
後者の場合 $O(N + M + $\sum_{i = 1}^M K_i$)$ です。
ACコード(544ms)

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> K(M);
  vector<vector<int>> pos(N + 1, vector<int>(0, 0));
  for(int i = 0; i < M; i++) {
    cin >> K[i];
    for(int j = 0; j < K[i]; j++) {
      int a;
      cin >> a, pos[a].push_back(i);
    }
  }
  int cnt = 0;
  for(int i = 0; i < N; i++) {
    int B;
    cin >> B;
    for(int o : pos[B]) {
      K[o]--, cnt += (!K[o]);
    }
    cout << cnt << endl;
  }
}

AC時間:9:31

D問題(diff:827)

平行になるようなものを列挙する…のような構想はできましたが、そこからうまくいきませんでした
傾きを考える、という案をもうちょっと考えていれれば良かったです。

感想

微下がり(パフォ713、レート743)
Dが難しくなっていってるので追いつけるよう頑張りたいです。