ABC392の振り返り

コンテスト参加前の僕「今日Writer誰かな~」
physics0523, kyopro_friends, ynymxiaolongbao
僕「終わった…」

A問題(diff:11)

$A_1A_2=A_3$ もしくは $A_1A_3=A_2$ もしくは $A_2A_3=A_1$ のどれかを満たせば良いです。
pythonで書きました
ACコード(pypy57ms, c++1ms)

A = list(map(int, input().split()))
if A[0] * A[1] == A[2] or A[0] * A[2] == A[1] or A[1] * A[2] == A[0]:
  print("Yes")
else:
  print("No")

AC時間:1:25

B問題(diff:29)

所属判定はstd::setでできるのですぐできます
計算量は $O(N + M)$ です。
ACコード(1ms)

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

int main() {
  int N, M;
  cin >> N >> M;
  set<int> A;
  for(int i = 0; i < M; i++) {
    int a;
    cin >> a;
    A.insert(a);
  }
  vector<int> ans(0, 0);
  for(int i = 1; i <= N; i++) {
    if(!A.count(i)) {
      ans.push_back(i);
    }
  }
  cout << ans.size() << endl;
  for(int i = 0; i < (int)ans.size(); i++) {
    cout << ans.at(i);
    if(i == (int)ans.size() - 1) {
      cout << endl;
    }
    else {
      cout << ' ';
    }
  }
}

AC時間:4:06

C問題(diff:132)

問題自体は簡単だけど整理がつくのが少し遅かったです。しかも入力のところで $Q$ が先に与えられて $P$ が後に与えられると思ってました(なにしてんの)
人 $i$ のゼッケンの番号、人 $i$ が見ている人、ゼッケン $i$ をつけている人の3つを記録しておけばすぐ答えが出せます。計算量は $O(N)$ です。
ACコード(140ms)(0_indexed)

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

int main() {
  int N;
  cin >> N;
  vector<int> see(N);
  for(int &o : see) {
    cin >> o;
    o--;
  }
  vector<int> Bib(N);
  vector<int> hyu(N);
  for(int i = 0; i < N; i++) {
    cin >> Bib.at(i);
    Bib.at(i)--;
    hyu.at(Bib.at(i)) = i;
  }
  for(int i = 0; i < N; i++) {
    cout << Bib.at(see.at(hyu.at(i))) + 1;
    if(i == N - 1) {
      cout << endl;
    }
    else {
      cout << ' ';
    }
  }
}

AC時間:11:19

D問題(diff:579)

確率の基本
kyopro_friendsさんがWriterすると聞いて、誤差を恐れていましたが、大丈夫でした。
各サイコロに出てくる目の種類やカウントなどをstd::setやstd::mapで管理することで、簡単に確率が求められます。
原理として、6面サイコロ2つのゾロ目を出すことを考えます。1つ目のサイコロの出る目が $i$ である確率は $\frac{1}{6}$ であり、2つ目のサイコロの出る目も $i$ となる確率は $\frac{1}{36}$ となります。$i = 1,2, \dots ,6$ についてこの確率の総和を求めるため、ゾロ目が出る確率は $\frac{1}{6}$ になります。この問題も同じように考えることができます。
僕の方針では $O(\sum_{i=1}^{N-1} (N - i)K_ilogK_i) = O(N*\sum_{i=1}^{N-1} K_ilogK_i)$ くらいの計算量になると思います。$N \le 10^2, \sum_{i=1}^{N} K_i \le 10^5 → K_i \le 10^5$ となるので、制約上このような最大のケースはありませんが、これでも間に合うので、それより小さいケースでも間に合うことが分かります。
ACコード(898ms)

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

int main() {
  int N;
  cin >> N;
  vector<int> sz(N);
  vector<set<int>> num(N);
  vector<map<int, double>> dice(N);
  for(int i = 0; i < N; i++) {
    cin >> sz.at(i);
    for(int j = 0; j < sz.at(i); j++) {
      int A;
      cin >> A;
      dice.at(i)[A] += 1.0;
      num.at(i).insert(A);
    }
  }
  double ans = 0;
  for(int i = 0; i < N - 1; i++) {
    for(int j = i + 1; j < N; j++) {
      double tmp = 0;
      for(int o : num.at(i)) {
        if(!num.at(j).count(o)) {
          continue;
        }
        tmp += (dice.at(i)[o] / sz.at(i)) * (dice.at(j)[o] / sz.at(j));
      }
      ans = max(ans, tmp);
    }
  }
  cout << fixed << setprecision(8);
  cout << ans << endl;
}

AC時間:16:20

E問題(diff:不明)

解けませんでした
Eのグラフはちょっとまだ難しいですが頑張っていきたいです。

感想

30分くらいで4完できて良かったです。
パフォーマンスは1024(2の累乗?!)で、レート689になりました。
2年になるまでに入緑という目標の $\frac{3}{4}$ 程達成できてるのでこれからも継続していきたいです。