AtCoder Beginner Contest 313

AtCoder Beginner Contest 313 - AtCoder

結果

A - To Be Saikyo : AC(2:55)
B - Who is Saikyo? : AC(12:23)
C - Approximate Equalization 2 : WA
D - Odd or Even : 提出無し

A - To Be Saikyo

$${N}$$までの番号が付けられた$${N}$$人のプログラミング力$${P_{i}}$$が与えられる
人$${1}$$が最強になるにはプログラミング力をいくつ伸ばす必要があるか求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  int ma = 0, p1;
  for(int i = 0; i < N; i++){
    int p;
    cin >> p;
    if(i == 0){
      p1 = p;
    }
    else{
      ma = max(ma, p);
    }
  }

  printf("%d\n", p1 > ma ? 0 : ma - p1 + 1);
}

そのまま
すでに最強の時0を出力するように注意

公式解説

省略

B - Who is Saikyo?

$${N}$$までの番号が付けられた競技プログラマーが$${N}$$人いる
$${M}$$個の「人$${A_{i}}$$は人$${B_{i}}$$より強い」という情報を元に最強のプログラマーを求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> G(N + 1);
  for(int i = 0; i < M; i++){
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
  }

  for(int i = 1; i <= N; i++){
    queue<int> bfs;
    vector<bool> seen(N + 1, false);
    bfs.push(i);
    seen[i] = true;
    int v = 1;
    while(!bfs.empty()){
      int now = bfs.front();
      bfs.pop();
      for(int go : G[now]){
        if(seen[go]){
          continue;
        }
        bfs.push(go);
        seen[go] = true;
        v++;
      }
    }

    if(v == N){
      printf("%d\n", i);
      return 0;
    }
  }
  printf("-1\n");
}

強い方から弱い方への有向グラフを作ってそれぞれの頂点から幅優先探索して全部に到達したらその人が最強

もっと楽で速い方法はある気がする

公式解説

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> deg(N);
  for (int _ = 0; _ < M; _++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    deg[b]++;
  }
  int ans = -1;
  for (int i = 0; i < N; i++) {
    if (deg[i] == 0) {
      if (ans != -1) {
        cout << -1 << endl;
        exit(0);
      } else {
        ans = i + 1;
      }
    }
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc313/editorial/6906より

それぞれに自分より弱い人が何人いるかを記録して、それが0な人が一人ならその人が答えか

なるほど

C - Approximate Equalization 2

整数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、その中から$${2}$$つ選んで片方を$${+1}$$、もう片方を$${-1}$$する操作を任意の回数して最小値と最大値の差が$${1}$$以下にするには最小何回操作する必要があるか求める問題

自分の回答

要は平均値を目指していくのはわかったけどそこからどうするかの調整ができなかった

公式解説

using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a.begin(), a.end());
    vector<int> b(n, sum / n);
    for (int i = 0; i < sum % n; i++) {
        b[n - 1 - i]++;
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(a[i] - b[i]);
    }
    cout << ans / 2 << endl;
}

https://atcoder.jp/contests/abc313/editorial/6901より

目標数列が平均+余りの数だけ項を+1か
それでAとの差の総和が操作回数の倍になる

なるほど

D - Odd or Even

整数$${N}$$と$${N}$$未満の奇数$${K}$$が与えられ、ジャッジシステムは$${0}$$か$${1}$$からなる長さ$${N}$$の数列$${A=(A_{1},A_{2},…,A_{N})}$$を持っている
ジャッジシステムに対して数列の相異なる任意の$${K}$$個の位置を渡すとその和が偶数か奇数かが帰ってくる
質問$${N}$$回以内で数列$${A}$$を求める問題

自分の回答

C問題に詰まってちょっと覗いた程度でパッとは思いつかなかったから戻った

公式解説

oid out(vector<int> v) {
  for (unsigned i = 0; i < v.size(); i++) {
    cout << v[i] << " \n"[i + 1 == v.size()];
  }
}

int main() {
  int N, K;
  cin >> N >> K;
  auto send = [&](vector<int> v) {
    for (auto& x : v) x++;
    cout << "? ", out(v);
    cout.flush();
    int x;
    cin >> x;
    return x;
  };
  vector<int> ans(N);
  {
    int r = 0;
    for (int i = 0; i < K + 1; i++) {
      vector<int> v;
      for (int j = 0; j < K + 1; j++)
        if (i != j) v.push_back(j);
      ans[i] = send(v);
      r ^= ans[i];
    }
    for (int i = 0; i < K + 1; i++) ans[i] ^= r;
  }
  {
    vector<int> v(K);
    int s = 0;
    for (int i = 0; i < K - 1; i++) v[i] = i, s ^= ans[i];
    for (int i = K + 1; i < N; i++) {
      v.back() = i;
      int t = send(v);
      ans[i] = s ^ t;
    }
  }
  cout << "! ", out(ans);
  cout.flush();
}

https://atcoder.jp/contests/abc313/editorial/6910より

やろうとしてることはわかるんだけどコードを理解しきれない…