ABC408の振り返り

めっちゃ遅れました、すみません
理由はシンプルにモチベが低かっｔ(言い訳にはならない)

A問題(diff:38)

もう長老やめろ
簡単にするため $T_0 = 0$ とします。
$T_i + S < T_{i + 1}$ であるような $(0 \le i < N)$ が一つでも存在すればNo、なければYesです。
計算量は $O(N)$ です。
ACコード(1ms)

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

int main() {
  int N, S, t = 0;
  cin >> N >> S;
  for(int i = 0; i < N; i++) {
    int T;
    cin >> T;
    if(T > t + S) {
      cout << "No" << endl;
      return 0;
    }
    t = T;
  }
  cout << "Yes" << endl;
}

AC時間:8:40

B問題(diff:35)

やるだけ
ソートして重複削除ができればなんでもいいです。
erase関数とunique関数を合わせたものとsort関数を使いました。
計算量は $O(NlogN)$ です。
ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void pil(vector<T> a) {
  for(int i = 0; i < (int)a.size(); i++) {
    cout << a[i];
    if(i == (int)a.size() - 1) {
      cout << endl;
    }
    else {
      cout << ' ';
    }
  }
}
//library end

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int &o : A) {
    cin >> o;
  }
  sort(A.begin(), A.end()), A.erase(unique(A.begin(), A.end()), A.end());
  cout << A.size() << endl;
  pil(A);
}

AC時間:3:50

C問題(diff:223)

え？！簡単な1次元imos法は灰diffになったんですか？！
$S_i = \sum_{k = 1}^M f(i \in [L_k, R_k + 1))) (f(u)は命題uが真なら1,偽なら0)$ として、答えは $\min S$ です。
では、実装について考えてみましょう。
遅延セグメント木を使えば、$O(N + MlogN)$ で解くことができます。
imos法を使えば、$O(N + M)$ で解くことができます。
詳細はコードを見てください(解説放棄)
ACコード(140ms,79ms)

//遅延セグメント木(ACL)
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

using S = int;
S op(S a, S b) {
  return min(a, b);
}
S e() {
  return (S)1e6;
}
using F = int;
S mapping(F f, S x) {
  return x + (S)f;
}
F composition(F g, F f) {
  return f + g;
}
F id() {
  return 0;
}
//library end

int main() {
  int N, M;
  cin >> N >> M;
  atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> S(vector<int>(N, 0));
  while(M) {
    int L, R;
    cin >> L >> R, M--, S.apply(L - 1, R, 1);
  }
  cout << S.all_prod() << endl;
}

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

int main() {
  int N, M, ans = (int)2e9;
  cin >> N >> M;
  vector<int> cnt(N + 1, 0);
  while(M) {
    int L, R;
    cin >> L >> R, M--, cnt[L - 1]++, cnt[R]--;
  }
  for(int i = 0; i < N; i++) {
    cnt[i] += cnt[i - 1], ans = min(ans, cnt[i]);
  }
  cout << ans << endl;
}

AC時間:3:16

D問題(diff:950)

思いつかなかったー
耳dp解法を実装したので置いておきます。
ACコード(23ms)

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

int main() {
  int T;
  cin >> T;
  while(T) {
    int N;
    string S;
    cin >> N >> S, T--;
    vector<int> dp(3, (int)1e9);
    dp[0] = 0;
    for(char o : S) {
      for(int i = 2; i >= 0; i--) {
        dp[i] = min(dp[i], (i ? dp[i - 1] : (int)1e9)) + (o - '0' != i % 2);
      }
    }
    cout << min(dp[0], min(dp[1], dp[2])) << endl;
  }
}

感想

かなり落ちました(パフォ648,レート748)
始めて一年まであと3回、頑張ります