AtCoder ABC 323 B - Round-Robin Tournament (灰色, 200 点)

ペアのソート。ソートの比較関数を作る系。

• 問題へのリンク

問題概要

人のプレイヤー によるリーグ戦の戦績表が下のように与えられる。

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

プレイヤーを勝ち星数が多い順に並び替えよ。ただし、タイの部分はプレイヤー番号が小さい順に並び替えよ。

コード

0-indexed で考えることにする。つまり、各プレイヤーの番号が 0, 1, ..., N-1 であると考えることにする。

最初に、各プレイヤーの勝ち星数を数える。

それが大きい順になるようにソートしよう。特殊なソートなので、比較関数を自分で作る必要がある。詳しくは次のコードにて。

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

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    
    // プレイヤー i = 0, 1, ..., N-1 の勝ち数を数える
    vector<int> wins(N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (S[i][j] == 'o') {
                ++wins[i];
            }
        }
    }
    
    // プレイヤー i とプレイヤー j を比較する関数を作る
    auto cmp = [&](int i, int j) -> bool {
        if (wins[i] != wins[j]) {
            // 勝ち星に差がある場合は、勝ち星が多い方が前に来る
            return wins[i] > wins[j];
        }
        else {
            // そうでない場合は、番号が小さい方が前に来る
            return i < j;
        }
    };
    
    // プレイヤー 0, 1, ..., N-1 をソートする
    vector<int> players(N);
    for (int i = 0; i < N; ++i) players[i] = i;
    sort(players.begin(), players.end(), cmp);
    
    // 出力
    for (auto player : players) cout << player + 1 << " ";
    cout << endl;
}