ABC406の振り返り

ランレングス↑圧縮↓

A問題(diff:不明)

条件分岐基本
$A$ と $C$ が等しいなら $B$ と $D$ の大小で考えるようにしましょう。
計算量は $O(1)$ です。
ACコード(CPython10ms,C++1ms)

A, B, C, D = map(int, input().split())
if A != C:
  if A > C:
    print("Yes")
  else:
    print("No")
else:
  if B > D:
    print("Yes")
  else:
    print("No")

AC時間:3:24

B問題(diff:不明)

面倒っぽかったので飛ばした
$A$ の要素を順にかけていって、途中で $10^K$ 以上になるかの判定は $\frac{10^K}{A_i} \le (現在の答え)$ でできます。
計算量は $O(N + logK)$ です。
少数誤差?知らない子ですね…
ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;
using ld = long double;

int main() {
  int N, K;
  cin >> N >> K;
  ld p = (ld)POW(10, K), ans = 1;
  while(N) {
    ld A;
    cin >> A, ans = (ans < p / A ? ans * A : 1), N--;
  }
  cout << (ll)ans << endl;
}

AC時間:8:28

C問題(diff:不明)

微分して極値が求まるやつに似てる
ちなみに前回の一文字C問題も記号
公式解説ではランレングス圧縮して上向きと下向きかの個数をかけて足し合わせる、というような感じのようです。
上向きと下向きが入れ替わる山/谷のところに注目しましたが解法が思いつかずACできませんでした。

D問題(diff:不明)

C問題ですか?
行/列ごとにゴミのある列/行を管理します。
1種類目のクエリと2種類目のクエリは逆のことをするだけなので1種類目だけ解説します。
$x$ に関して、$x$ 行目にあるゴミが、それぞれ $y_1, \dots , y_{|y|}$ 列目だとして、管理している「$x$ 行目にあるゴミの列」を全て削除し($y$ の要素に関して全て削除するということ)、「$y_i$ 列目にあるゴミの行」から $x$ を削除します。これはsetによって効率的に実現できます。
計算量は $O(NlogN + Q)$ で上から抑えられるのではないでしょうか?
ACコード(637ms)

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

int main() {
  int H, W, N, Q;
  cin >> H >> W >> N;
  vector<set<int>> xy(H + 1), yx(W + 1);
  while(N) {
    int X, Y;
    cin >> X >> Y, xy[X].insert(Y), yx[Y].insert(X), N--;
  }
  cin >> Q;
  while(Q) {
    int q;
    cin >> q, Q--;
    if(q - 1) {
      int y;
      cin >> y;
      cout << yx[y].size() << endl;
      for(int i = (int)yx[y].size(); i > 0; i--) {
        int x = *yx[y].begin();
        xy[x].erase(y), yx[y].erase(x);
      }
    }
    else {
      int x;
      cin >> x;
      cout << xy[x].size() << endl;
      for(int i = (int)xy[x].size(); i > 0; i--) {
        int y = *xy[x].begin();
        xy[x].erase(y), yx[y].erase(x);
      }
    }
  }
}

AC時間:40:22

感想(E飛ばさせてください、お願いします)

まあ(パフォ887,レート765)
緑まで@35ですね、緑パフォ上位出したら行けるでしょう