ABC391の振り返り

初4完!

A問題(diff:不明)

節分に関連して方角の逆を求めるみたいな感じですね。
競技プログラミング伝家の宝刀「ゴリ押し」を使うこともできますが、Dのある要素がNならS,EならWに変換する(逆の操作も)をすればすぐ答えが出ます。
計算量は言うまでもなく $O(1)$ です。
ACコード(1ms)

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

int main() {
  string D;
  cin >> D;
  for(char &o : D) {
    if(o == 'N') {
      o = 'S';
      continue;
    }
    if(o == 'S') {
      o = 'N';
      continue;
    }
    if(o == 'E') {
      o = 'W';
      continue;
    }
    if(o == 'W') {
      o = 'E';
      continue;
    }
  }
  cout << D << endl;
}

AC時間:4:11(ゴリ押ししたら重実装になるので仕方ない)

B問題(diff:不明)

こちらも重実装でした
時間計算量は $O((NM)^2+M^4)$ くらい、$N,M \le 50$ なら十分間に合います。
ACコード(1ms)

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<string> S(N);
  for(string &o : S) {
    cin >> o;
  }
  vector<string> T(M);
  for(string &o : T) {
    cin >> o;
  }
  for(int i = 0; i <= N - M; i++) {
    for(int j = 0; j <= N - M; j++) {
      bool ans = true;
      for(int k = i; k < i + M; k++) {
        for(int l = j; l < j + M; l++) {
          if(S.at(k).at(l) != T.at(k - i).at(l - j)) {
            ans = false;
          }
        }
      }
      if(ans) {
        cout << i + 1 << ' ' << j + 1 << endl;
        return 0;
      }
    }
  }
}

AC時間:11:48

C問題(diff:不明)

鳩の巣原理関係ないです
鳩が移動した時、複数羽いる巣の数にどのように影響があるかというと、ある巣から鳩が1羽出て、その巣にいる鳩の数が1羽になったら数が1減り、またある巣に鳩が1羽入って、その巣にいる鳩の数が2羽になったら数が1増えます。
これは、減る・増える前の鳩の数が2羽・1羽かによって先に判定することができます。全ての鳩がそれぞれどこにいるのかもしっかり配列で管理しておきましょう。最初は複数羽いる巣の数を0にしておきます(全ての巣に1羽ずつしか居ないから)
計算量は初期化 $O(N)$ 、クエリ処理 $O(Q)$ の合計で $O(N+Q)$ となり、高速に動作します。
ACコード(310ms)

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

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<int> cnt(N + 1, 0);
  vector<int> iti(N + 1, 0);
  for(int i = 1; i <= N; i++) {
    cnt.at(i)++, iti.at(i) = i;
  }
  int ans = 0;
  for(int i = 0; i < Q; i++) {
    int query;
    cin >> query;
    if(query - 1) {
      cout << ans << endl;
    }
    else {
      int P, H;
      cin >> P >> H;
      if(cnt.at(iti.at(P)) == 2) {
        ans--;
      }
      if(cnt.at(H) == 1) {
        ans++;
      }
      cnt.at(iti.at(P))--,cnt.at(H)++, iti.at(P) = H;
    }
  }
}

AC時間:7:36

D問題(diff:不明)

下1行しか消えない(こんなテトリスは嫌だ)
階層ごとに考えればいいです。$i(1 \le i \le N)$ 列目に存在して、下から $j$ 番目にあるブロックの番号を、$B_{i,j}$ とすると、全ての $i$ に対して、$B_{i,j}$ が存在するような最大の $j$ を $j_{max}$ と置きます。$1 \le k \le j_{max}$ にて、$B_{i,k}$ が消える時間は $Y_{B_{i,k}}$ の最大値となります。($k > j_{max}$ の時は $+∞$ とします)。あとはブロック $A$ の消える時刻が $T_i$ より遅ければYes、早ければNoとします。
前計算に $O(W+NlogN)$ 、クエリ処理に $O(Q)$ かかるので合計で $O(NlogN+W+Q)$ となり、高速に動作します。
ACコード(337ms)

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

int INF = (int)2e9;

int main() {
  int N, W;
  cin >> N >> W;
  vector<vector<pair<int, int>>> B(W + 1, vector<pair<int, int>>(0));
  for(int i = 1; i <= N; i++) {
    int X, Y;
    cin >> X >> Y;
    B.at(X).push_back(make_pair(Y, i));
  }
  int max_s = 0;
  for(int i = 1; i <= W; i++) {
    max_s = max(max_s, (int)B.at(i).size());
    sort(B.at(i).begin(), B.at(i).end());
  }
  vector<int> erase_time(N + 1, INF);
  for(int i = 0; i < max_s; i++) {
    bool f = true;
    int t = 0;
    for(int j = 1; j <= W; j++) {
      if((int)B.at(j).size() <= i) {
        f = false;
        break;
      }
      t = max(t, B.at(j).at(i).first);
    }
    if(!f) {
      break;
    }
    for(int j = 1; j <= W; j++) {
      erase_time.at(B.at(j).at(i).second) = t;
    }
  }
  int Q;
  cin >> Q;
  for(int i = 0; i < Q; i++) {
    int T, A;
    cin >> T >> A;
    if(erase_time.at(A) > T) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}

AC時間:35:35

E問題(diff:不明)

なるほど、DPですか…
最近EのDPが多いのでCのDPやDのDP増やしてほしいです。

感想

3回目の緑パフォを出し、レート644になりました。(やったね)
目標としては学年が上がるまでに入緑する、というものだったので、1月終わりの時点で $\frac{5}{8}$ くらい達成できてるのでかなり良い調子です。