ABC401の振り返り

最近他の中学生勢が強くなってきていて自分ももっと頑張ろうと感じる
そしてCがどんどん簡単になってDが難しくなっていくのやめてください

A問題(diff:不明)

前回より簡単(出力する文字列が長いのが面倒)
$2 \times 10^2 \le S \cap S < 3 \times 10^2$ かを判定するだけです。
計算量は $O(1)$ となります。
ACコード(pypy55ms,C++1ms)

S, h = int(input()), 10 ** 2
if S >= 2 * h and S < 3 * h:
  print("Success")
else:
  print("Failure")

AC時間:1:27

B問題(diff:不明)

見掛け倒し!
最初、フラグ $f$ を $0$ としておき、loginが出たら $f = 1$ とし、logoutが出たら $f = 0$ とし、$f = 0$ かつ privateが出たら答えを一増やす、とすれば良いです。
計算量は $O(\sum_{i = 1}^N len(S_i))$ です。
ACコード(1ms)

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

int main() {
  int N, f = 0, ans = 0;
  cin >> N;
  for(int i = 0; i < N; i++) {
    string S;
    cin >> S, f = (S == "login" ? 1 : f), f = (S == "logout" ? 0 : f), ans += (1 - f) * (S == "private");
  }
  cout << ans << endl;
}

AC時間:4:29

C問題(diff:不明)

前回のCよりかは簡単だけど、典型問題ではあるので解くべき
スライド総和のようなことをすることが公式解説には載っていますが、累積和をとっても良いです。
まず、$N < K$ の時は明らかに $1$ です。それ以外の時について考えます。
$A_i = \sum_{j = i - K}^{i - 1}A_j$ です。ここで、累積和をとっておけば、$A_i$ を $O(1)$ で求めることができます。$A_i$ を求めたらそこまでの累積和もとっておくようにしましょう。
計算量は $O(N)$ です。実装上の注意として、例えばC++なら負の値を割ったときの余りが(数学的に)正しいとは限らないので、$10^9$ を足してから余りを求めれる必要があります。
ACコード(21ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//library end

ll inf = (ll)1e9;

int main() {
  int N, K;
  cin >> N >> K;
  vector<ll> A(N + 1, 0), sum(N + 1, 0);
  for(int i = 0; i < min(N + 1, K); i++) {
    A[i] = 1, sum[i] = ((i ? sum[i - 1] : 0) + 1) % inf;
  }
  for(int i = min(N + 1, K); i <= N; i++) {
    A[i] = (sum[i - 1] - (i > K ? sum[i - K - 1] : 0) + inf) % inf, sum[i] = (sum[i - 1] + A[i]) % inf;
  }
  cout << A[N] << endl;
}

AC時間:8:11

D問題(diff:不明)

場合分けはできましたが、そこから進みませんでした

E問題(diff:不明)

なんとなーく構想が立つこともなく、少しだけ考察ができただけでした

感想

悪くはない(パフォ941,レート746)
緑まであと54レートとなりました。多分水パフォが出せたら入れると思うので、得意系のE問題やらが来ることを願わんばかりです。