ABC393の振り返り

連日テストがあったり日本橋ハーフマラソン始まったりyukicodercontestあったりとめっちゃ忙しくて脳が働いていなかったです
あと絶対にNyaanさんを許してはいけないです(難しすぎ)

A問題(diff:10)

某リアクティブE問題ですか?
にしても高橋くんにはこれ以上毒入りの食べ物をあげないでほしいと思いました。
本題に戻ります。高橋くんがお腹を壊しているかいないか、青木くんがお腹を壊しているかいないかで全4パターンを考えれば良いです。
ACコード(pypy55ms, c++1ms)

S_1, S_2 = input().split()
if S_1 == "sick":
  if S_2 == "sick":
    print(1)
  else:
    print(2)
else:
  if S_2 == "sick":
    print(3)
  else:
    print(4)

AC時間:2:20

B問題(diff:44)

コーナーケースを考えてなかったです(というかシンプルに実装ミス)
$i < j < k$ であり、$S_i =$ Aであり、$S_j =$ Bであり、$S_k =$ Cであり、$i + k = 2j$ であれば答えを $1$ 増やします。計算量は $O(|S|^3)$ となります。
公式解説にBonusがあったのでその解法も考えます。Bonus1は $O(|S|^2)$ で解くと書いてありました。多分2重ループを回して、($i, j$ の2つ)あとは $O(1)$ で条件を満たす $k$ の個数を求めれればいいですね。これは $i < j$ であり、$S_i =$ Aであり、$S_j =$ Bであり、$S_{2j - i} =$ Cであれば、答えを $1$ 増やします。配列外参照には気をつけましょう。
ACコード(1ms)

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

int main() {
  string S;
  cin >> S;
  int s = S.size();
  vector<bool> f(s, 0);
  for(int i = 0; i < s; i++) {
    f[i] = (S[i] == 'C');
  }
  int ans = 0;
  for(int i = 0; i < s; i++) {
    for(int j = 0; j < s; j++) {
      if(i < j && S[i] == 'A' && S[j] == 'B' && 2 * j - i < s && f[2 * j - i]) {
        ans++;
      }
    }
  }
  cout << ans << endl;
}

AC時間:19:44

C問題(diff:188)

Bのペナルティを食らってBと一緒に解いてたのでなかなか難しかったです。
でも問題名のようにシンプルに考えればなんともなかったですね。
std::vectorやstd::mapを使えば、多重辺や自己ループも検出できます。
辺はいつも(小)→(大)となるように有効辺っぽくしておけば簡単にできます。
計算量はだいたい $O(M(logM - logN))$ くらいなんじゃないでしょうか。(確信してください)
ACコード

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<map<int, int>> G(N + 1);
  vector<set<int>> num(N + 1);
  for(int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    if(u < v) {
      G[u][v]++;
      num[u].insert(v);
    }
    else {
      G[v][u]++;
      num[v].insert(u);
    }
  }
  int ans = 0;
  for(int i = 1; i <= N; i++) {
    for(int o : num[i]) {
      if(o == i) {
        ans += G[i][o];
      }
      else if(G[i][o] > 1) {
        ans += G[i][o] - 1;
      }
    }
  }
  cout << ans << endl;
}

AC時間:6:09

D問題(diff:533)

3連続で4完しているという事実
お料理(列の何かの総和をとる問題)、得意なんです!
僕の解法は公式解説よりsounansyaさんの解説に近い感じです。$S$ に出てくる $1$ の全てのインデックスを管理した配列を $ind$ とします。この配列の長さを $L$ としておきます(配列 $ind$ が完成した時の長さを $L$ とする、という方が正しいかもしれません)。$ind$ の累積和も取って $sum$ としておきましょう。最初答えを適当に大きな数(僕は $5 \times 10^{15}$ としました)に初期化し、$i = 1, \dots L$ の順に、$sum_L - sum_i - sum_{i - 1} + ind_i(2i-L-1) - \frac{1}{2}(i(i - 1) + (L - i)(L - i + 1))$ を計算し、chminしていきます。
計算量は $O(N)$ になります。
ACコード(13ms)

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

int main() {
  int N;
  string S;
  cin >> N >> S;
  vector<ll> ind(0, 0);
  ind.push_back(0);
  for(ll i = 0; i < N; i++) {
    if(S[i] == '1') {
      ind.push_back(i + 1);
    }
  }
  ll L = ind.size();
  vector<ll> sum(L, 0);
  L--;
  for(int i = 1; i <= L; i++) {
    sum[i] = sum[i - 1] + ind[i];
  }
  ll ans = 5e15;
  for(ll i = 1; i <= L; i++) {
    ans = min(ans, sum[L] - sum[i] - sum[i - 1] + ind[i] * (2 * i - L - 1) - (i * (i - 1) + (L - i) * (L - i + 1)) / 2);
  }
  cout << ans << endl;
}

AC時間:34:01

E問題(diff:不明)

連続した $K$ 個の要素の $GCD$ ならsegment木ですぐ求めることができたんですけどね…
制約が微妙に大きいので愚直に約数列挙して $O(\sum_{i=1}^{N} \sqrt{A_i})$ では間に合いませんでした。
あと計算量は調和級数で $O(MlogM)$ になるらしいですね。
解説ACのコードを載せておきます。
ACコード(1366ms)

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N), s(1000100), t(1000100);
  for(int &o : A) {
    cin >> o;
    s[o]++;
  }
  for(int i = 1; i <= (int)1e6; i++) {
    for(int j = i; j <= (int)1e6; j += i) {
      t[i] += s[j];
    }
  }
  vector<int> ans(1000100);
  for(int i = 1; i <= (int)1e6; i++) {
    if(t[i] < K) {
      continue;
    }
    for(int j = i; j <= (int)1e6; j += i) {
      ans[j] = max(ans[j], i);
    }
  }
  for(int o : A) {
    cout << ans[o] << endl;
  }
}

感想

ギリギリ緑パフォいけませんでした(794)レートは700ジャストになりました。
まあでも頭が働いていない状態でこれはかなり頑張ったと思います。
ヒューリスティック頑張ります