AtCoderでじゃんけんを

• AtCoderでじゃんけんを

考察

• 愚直に解いたら$O(N^2)$になってしまう。

• 勝ち負けのパターンを整理すると以下の３つになる。勝ち数とドロー数がわかれば負け数がわかるので、勝ち数とドロー数のみを考える。

  1. 相手よりレートが高かったら勝ち
  2. 相手とレートが同じで、手が勝ってたら勝ち
  3. 相手とレートが同じで、手が同じならドロー。

• とりあえず愚直に書いてみることにした。何か見えてくるかもしれないので

• 書いてみたけど、二分探索とかしゃくとり法にできそうではない。なので他の方法を考える

• 勝ち数は「レート勝ち数」＋「レートが同じで、手が勝ってる」である。「レート勝ち数」は累積和を使えば$O(1)$で求められる。「レートが同じで、手が勝ってる」のは、連想配列を使えば$O(logN)$で求められる（C++のmapの計算量）。連想配列にはmap[<レート, 手>] = そのレートでその手の人数って感じで値を管理する。こんな感じで勝ち数は求められそう。

• 引き分け数は、「同じレートで同じ手のやつ」である。これは、先ほどの連想配列を使えば求められる。

• 考察終了

解法

1. レートごとの人数を配列に保存。その配列累積和をとって、あるレート以下の人数を$O(1)$で求められるようにしておく
2. map[<レート, 手>] = そのレートでその手の人数という連想配列を作る。
3. 「勝ち数」と「引き分け数」を求めて、「人数 - (勝ち数+勝ち数)」で「負け数」を求める方針で行く。
4. ある人の勝ち数を「レート勝ち数」＋「レート同じで手が勝ってる数」で求める。レート勝ち数は、先ほど累積和をとった配列を使えば求められる。レート同じで手が勝ってる場合は、先ほど作った連想配列をつかって条件分岐頑張って書けば求められる
5. ある人の引き分け数を「レート同じで手が同じ」で求める。これは先ほど作った連想配列を使えば求めることができる。ただし、mp[<その人のレート, その人の手>]で取り出した人数に自分が含まれることに注意する。なので、ドロー数は-1して出力する。

コード

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

# define int long long

using pii = pair<int, int>;

int N;
int R[111111];
int H[111111];
int rui[111111]; // rui[i]: レートi以下の人数
map<pii, int> mp; // map[<rate, hand>]: そのレートでその手の人数

void solve(int n) {
  int win = 0, lose = 0, draw = 0;

  /* 自分より低レート*/
  win += rui[R[n]-1];

  /* 同レート*/
  int gu = mp[{R[n], 1}];
  int ch = mp[{R[n], 2}];
  int pa = mp[{R[n], 3}];
  // 同レートで勝利
  if (H[n] == 1) {
    win += ch;
  } else if (H[n] == 2) {
    win += pa;
  } else {
    win += gu;
  }
  // 同レートで引き分け
  if (H[n] == 1) {
    draw += gu;
  } else if (H[n] == 2) {
    draw += ch;
  } else {
    draw += pa;
  }

  // この時点でwin確定, draw確定してるので「人数 - (勝ち数 + 引き分け数)」で負け数が求められる
  lose = N - (win + draw);

  printf("%lld %lld %lld\n", win, lose, draw-1); // drawには自分も含まれているので1引いておく
}

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> R[i] >> H[i];
    rui[R[i]]++;
    mp[{R[i], H[i]}]++;
  }

  for (int i = 1; i < 111111; i++) {
    rui[i] += rui[i-1];
  }

  for (int i = 0; i < N; i++) {
    solve(i);
  }

  return 0;
}

感想

• AtCoderじゃんけん、散々ネタにしてたのに解いてなかったので解いた。思ったより難しかった（愚直解で解ける問題だと思ってた）
• 公式解説と解き方違う。公式解説よくわからない。