ABC409の振り返り

プロセカの配信見てたらランクマ上位帯に @kazuppa さんがいて、改めてすごいなと思った

A問題(diff:22)

牡蠣ぶりのコンビかと思いきや押しボタンゲームぶりだった
if文とfor文ができれば解けます。
計算量は $O(N)$ です。
ACコード(CPython9ms,C++2ms)

N, T, A, f = int(input()), input(), input(), 0
for i in range(N):
  if T[i] == 'o' and A[i] == 'o':
    f = 1
    break
if f:
  print("Yes")
else:
  print("No")

AC時間:1:37

B問題(diff:126)

めっちゃ苦戦
$A$ は昇順ソートしておきます。
まず、$x > N$ の時は明らかに条件を満たさないので、$x$ は $0, \dots ,N$ の中のどれかであることが分かります。なので、$x$ を $N$ から $0$ へ降順に見ていき、最初に条件を満たした $x$ が答えです。
条件の判定を考えます。$x > A_i$ であるような最小の $i$ を求めた時、$x \le N - i + 1$ なら、その $x$ は条件を満たします。この $i$ は二分探索を用い $O(logN)$ で求めることができます。
そのような $i$ が存在しない場合、$A$ の全ての要素が $x$ 以上であるため、また $x \le N$ であることから、その $x$ は条件を満たします。
これを実装することで解けます。計算量は $O(NlogN)$ です。
ACコード(1ms)

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int &o : A) {
    cin >> o;
  }
  sort(A.begin(), A.end());
  for(int i = N; i >= 0; i--) {
    if(i <= A[0]) {
      cout << i << endl;
      return 0;
    }
    int l = 0, r = N, mid = 0;
    while(r - l > 1) {
      mid = (l + r) / 2;
      if(A[mid] < i) {
        l = mid;
      }
      else {
        r = mid;
      }
    }
    if(i <= N - r) {
      cout << i << endl;
      return 0;
    }
  }
}

AC時間:51:20

C問題(diff:421)

面白い問題!
まず、$L$ が $3$ の倍数でない時答えが必ず $0$ になることを証明します。
$L$ が $3$ の倍数でない時に答えが $0$ にならない場合があると仮定し、その場合について考えます。その円上にできる正三角形を一つ適当に選びます。その正三角形の各辺を弦としたときの、劣弧の長さを考えます。弦の長さが等しいとき、劣弧の長さが等しいので、三つの劣弧の長さが等しいことが分かり、その和は、3の倍数になります。また、選んだ正三角形が円に内接していることから、その和は、$L$ と等しいことが分かります。ここで、$L$ と $3$ の倍数が等しい→ $L$ は $3$ の倍数となり、仮定に反します。よって、仮定が間違っていることが分かり、題意が示されました。
では本題に入りましょう。$d$ から、全ての点の位置を計算し頻度表を作ります。($C$ とする)
$L' = \frac{L}{3}$ として、答えは $\sum_{i = 1}^{L'} C_i \times C_{i + L'} \times C_{i + 2L'}$ となります。終わり!
計算量は $O(L + N)$ です。
ACコード(58ms)

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

int main() {
  int N, L;
  cin >> N >> L;
  if(L % 3) {
    cout << 0 << endl;
    return 0;
  }
  int p = 0;
  vector<ll> cnt(L, 0);
  cnt[0]++;
  while(N - 1) {
    int d;
    cin >> d, N--, p += d, p %= L, cnt[p]++;
  }
  ll ans = 0;
  L /= 3;
  for(int i = 0; i < L; i++) {
    ans += cnt[i] * cnt[i + L] * cnt[i + 2 * L];
  }
  cout << ans << endl;
}

AC時間:28:14

D問題(diff:772)

「辞書順」の理解が結構鍵かも
まず $S$ の文字が辞書順に並んでいる場合(例:abc,z)、違う文字列に変える必要がありません(変わったら辞書順最小ではなくなります)。この時は、適当に整数 $l(1 \le l \le N)$ を選び、$r = l$ として操作すれば、$S$ は変わりません。
では、$S$ の文字が辞書順に並んでいない場合(例:arc,fed)、どうすればよいでしょうか。$S_i$ が $S_{i + 1}$ より辞書順で大きい $i(1 \le i < N)$ について考えます。そのような $i$ を $l$ として操作すると良さそうです。また、辞書順に大きく影響を与えるのは、文字列の前の方の変化なので、そのような $i$ の中で最小のものを $l$ とします。次に、$r$ について考えます。$S_l$ が $S_i$ より辞書順で小さい $i(i > l)$ の中で最小のものを $t$ とします(つまり、$i = l + 1$ から始めて $i$ を大きくし、初めて $S_l$ が $S_i$ より辞書順で小さくなる $i$ を $t$ とする、また存在しない場合は $N + 1$ とする)。$r = t - 1$ として操作するのが最善手です。
「$S_l$ より辞書順で以下である文字でできた文字列」が「$S_l$」の前に来ることによって、操作後の $S$ の中で辞書順最小になります。実際にサンプルケースで試してみると良いでしょう。
計算量は1テストケースにつき $O(N)$ です。全体で $O(\sum_{i = 1}^T N_i)$ 、制約より十分高速です。
ACコード(25ms)

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

int main() {
  int T;
  cin >> T;
  while(T) {
    int N, f = 0, p = -1, t = -1;
    string S;
    cin >> N >> S, T--;
    for(int i = 0; i < N - 1; i++) {
      if(S[i] > S[i + 1] && !f) {
        f = 1, p = i;
      }
    }
    if(!f) {
      cout << S << endl;
      continue;
    }
    t = p + 1;
    while(t < N && S[p] >= S[t]) {
      t++;
    }
    cout << S.substr(0, p) + S.substr(p + 1, t - p - 1) + S[p] + S.substr(t, N - t) << endl;
  }
}

AC時間:9:19

感想

750より上に戻った(パフォ831,レート757)
5完したい…