ABC388の振り返り

レート停滞期に入りそうな予感がしますね…

A問題(diff:8)

前回に続き簡単
またpythonで書きました。
ACコード(pypy59ms,c++1ms)

print(input()[0]+"UPC")

AC時間:1:13

B問題(diff:30)

$heavy$ という長さ $D$ の配列を作ります。
各 $i(1 \le i \le N)$ について、$heavy_j(1 \le j \le D) = max(heavy_j,T_i(L_i+j))$ としていけば、答えが出ます。計算量は $O(ND)$ です。
ACコード(1ms)

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

int main() {
  int N, D;
  cin >> N >> D;
  vector<int> heavy(D);
  for(int i = 0; i < N; i++) {
    int T, L;
    cin >> T >> L;
    for(int j = 0; j < D; j++) {
      heavy.at(j) = max(heavy.at(j), T * (L + j + 1));
    }
  }
  for(int o : heavy) {
    cout << o << endl;
  }
}

AC時間:5:00

C問題(diff:211)

寿司屋ぶりの二分探索!
$A$ は既にソートされているという制約($A_i < A_{i+1}(1 \le i < N)$)から、$A$ をそのまま使えることが分かります。
もし $2 \times A_i(1 \le i \le N) > A_N$ なら、それ以上探索しても鏡餅を作ることはできません。なので、for文を回している間、$2 \times A_i > A_N$ となったらbreakすれば良いです。(もしくはfor文の条件などを変えてもできます)
そうでなければ、$2 \times A_i \in (A_{r - 1},A_r]$ を満たす $r(1 < r \le N)$ を二分探索によって求め、$N - r + 1$ を答えに加算すればよいです。
ACコード(136ms)

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int &o : A) {
    cin >> o;
  }
  ll ans = 0;
  for(int i = 0; A.at(i) * 2 <= A.at(N - 1); i++) {
    int l = i;
    int r = N;
    int c = 0;
    while(r - l > 1) {
      c = (l + r) / 2;
      if(A.at(c) >= A.at(i) * 2) {
        r = c;
      }
      else {
        l = c;
      }
    }
    ans += N - r;
  }
  cout << ans << endl;
}

AC時間:11:01

D問題(diff:659)

終盤に公式解説の発想は思いつきましたが、実装できませんでした。
視点を変えることを積極的にやっていきたいです。

感想

パフォーマンスは602でレートが515になりました。
レート停滞はしないよう気をつけたいです