ABC403の振り返り

少し前のABCのC問題:二分探索・bit全探索・重実装が主流
現在のABCのC問題:圧倒的set・map時代

A問題(diff:9)

C++ならfor・ifだけで行ける、Pythonは配列も必要かも
普通にシュミレーションして $O(N)$ で解けます。
ACコード(pypy57ms,C++1ms)

N, ans = int(input()), 0
A = list(map(int, input().split()))
for i in range(N):
  if 1 - i % 2:
    ans += A[i]
print(ans)

AC時間:1:27

B問題(diff:74)

これは250点適正
$T$ から長さ $|U|$ の連続部分文字列を取り出して(これを $t$ とします)、$t_i \neq $ ?である全ての $i$ について、$t_i = U_i$ であれば元の $S$ に $U$ が含まれます。
これを実装すると $O((|T| - |U|)|U|)$ となります。
ACコード(2ms)

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

int main() {
  string T, U;
  cin >> T >> U;
  for(int i = 0; i <= (int)(T.size() - U.size()); i++) {
    bool f = true;
    for(int j = 0; j < (int)U.size(); j++) {
      f = f && (T[i + j] == '?' || T[i + j] == U[j]);
    }
    if(f) {
      cout << "Yes" << endl;
      return 0; 
    }
  }
  cout << "No" << endl;
}

AC時間:10:00

C問題(diff:208)

最近setとmapしか使ってないので久々に二分探索お願いします(あとWAtCoderで笑った)
まず、管理するデータとして、$ok_i =$ ユーザ $i$ が閲覧権限を持っているコンテストページの集合($1 \le i \le N$)、$allok_i =$ ユーザ $i$ が全てのコンテストページの閲覧権限を持っているかのフラグを持ちます。
クエリ1は、$ok_X$ に $Y$ を追加します。
クエリ2は、$allok_X$ を $true$ にします。
クエリ3は、$allok_X$ または $ok_X$ に $Y$ が含まれるならばYes、そうでなければNoを出力します。
クエリの種類ごとに計算量は変わりますが合計して上から $O(QlogN)$ でおさえられると思います。
実装では、$ok_i$ をsetで持ち、$allok_i$ をbool等で持てば良いです。
ACコード(227ms)

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

int main() {
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<set<int>> ok(N + 1);
  vector<bool> all_ok(N + 1, false);
  while(Q) {
    int query, X;
    cin >> query >> X;
    if(query != 2) {
      int Y;
      cin >> Y;
      if(query - 1) {
        cout << (all_ok[X] || ok[X].count(Y) ? "Yes" : "No") << endl;
      }
      else {
        ok[X].insert(Y);
      }
    }
    else {
      all_ok[X] = true;
    }
    Q--;
  }
}

AC時間:5:24

D問題(diff:1052)

$i = 0, \dots , N - 1$ で独立に解くことまでは行きましたが久々のDPで解けませんでした
edpcのA~E復習します…

感想

多少上がりました(パフォ884,レート758)
Dが難しすぎる…
もっといろんなテクニック・アルゴリズム・データ構造を学んでいきたいです。