ABC394の振り返り

うわああああああああああああ(棒読み)

A問題(diff:12)

2があったら答えに追加するだけですね
計算量は $O(|S|)$ となります。
ACコード(pypy57ms, c++1ms)

S, ans = input(), ""
for o in S:
  if o == '2':
    ans += o
print(ans)

AC時間:1:32

B問題(diff:30)

猫の日ネタ
にしても焦りすぎて2ペナを食らってしまいました…
1回目…長さ順昇順ソートしないといけないのに辞書順ソートしてしまう
2回目…長さ順昇順ソートしないといけないのに長さ順降順ソートしてしまう
これのせいで10分無駄にしました。
あ、解説としては、c++ならラムダ式などを使って比較関数をソートするときに定義すると良いです。
計算量は $(NlogN)$ となります。十分高速です。
ACコード(1ms)

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

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  for(string &o : S) {
    cin >> o;
  }
  sort(S.begin(), S.end(), [](string a, string b) { return (int)a.size() < (int)b.size(); });
  string ans = "";
  for(string o : S) {
    ans += o;
  }
  cout << ans << endl;
}

AC時間:4:10

C問題(diff:161)

いい問題名
素直に左から見ていくのを繰り返していけば流石に間に合わないので、工夫する必要がありそうです。
「左にある方から」というルールは、「$S_iS_{i+1} = $ WA となる $i$ を小さい順から」というように言い換えられます。これはヒープによってできます。
では一応、操作回数の上界を求めておきましょう。WA を AC に変えられるだけ変えたときの操作回数は、操作をしたときにできる新たなCの数と等しくなります。操作によって $S$ の一番左の文字をCに変えることができないことは明らかだと思います。ただ、$i = 2, \dots , |S|$ に関しては変えられる可能性があるので、操作をしたときにできるCの個数の最大値は $|S| - 1$ 個となります。なので、操作回数の上界は $|S| - 1$ 回です。
計算量は $O(|S|log|S|)$ です。$O(S)$ でもできるらしいですが通ればいいんですよ(おい)
ACコード(22ms)

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

int main() {
  string S;
  cin >> S;
  priority_queue<int, vector<int>, greater<int>> WA;
  for(int i = 0; i < (int)S.size() - 1; i++) {
    if(S.substr(i, 2) == "WA") {
      WA.push(i);
    }
  }
  while(!WA.empty()) {
    int i = WA.top();
    WA.pop();
    S[i] = 'A', S[i + 1] = 'C';
    if(i > 0 && S.substr(i - 1, 2) == "WA") {
      WA.push(i - 1);
    }
  }
  cout << S << endl;
}

AC時間:8:04

D問題(diff:253)

stackを使った括弧列の問題の練習ですね
括弧が3種類ありますが、6面サイコロの平行な2面の目の和は必ず $7$ となることから、$2 \times 3$ パターンに分けて考えることができます。ですが、気をつけていないと、)(などもYesと間違えて判定してしまいます。これのせいで2ペナを食らいました…
計算量は $O(N)$ です。
類題
ACコード(5ms)

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

int to_int(char o) {
  if(o == '(') {
    return 1;
  }
  else if(o == ')') {
    return 6;
  }
  else if(o == '[') {
    return 2;
  }
  else if(o == ']') {
    return 5;
  }
  else if(o == '<') {
    return 3;
  }
  else {
    return 4;
  }
}

int main() {
  string S_;
  cin >> S_;
  stack<int> S;
  for(char o : S_) {
    int tmp = to_int(o);
    if(!S.empty() && S.top() + tmp == 7 && S.top() < tmp) {
      S.pop();
    }
    else {
      S.push(tmp);
    }
  }
  if(S.empty()) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

AC時間:28:22

E問題(diff:1403)

Eのグラフは無理ですって言ってるじゃないですか

F問題(diff:1549)

アルカンは化学物質なんですね、勉強になりました
Wikipedia

感想

入茶してから初のレート下げでした(-13)(パフォーマンスは567)
B問題を落ち着いて解きましょう、それだけ
あとそろそろ5完したいです
幸い3月からは忙しくないのでリラックスしてできそうです