AtCoder Beginner Contest 222 C - Swiss-System Tournament
問題の要約
1から2Nの番号がついた2N人でじゃんけん大会をする。
大会はMラウンドからなり,各ラウンドは,全ての人が1度ずつ参加するような1対1のN試合からなる。
i=1,...,Mについて,iラウンド目の終了時点での順位を次のように決める。
・iラウンド目までの勝数が多い方が上位
・iラウンド目までの勝数が同じときは,番号が小さい方が上位
また,i=1,...,Mについて,iラウンド目の各試合の組み合わせは次のように決める。
・各k=1,2,...,Nについて,i-1ラウンド目終了時点の順位が2k-1位の人と2k位の人が試合をする。
各試合では対戦する2人がそれぞれ1度だけ手を出し,勝ち・負け・引き分けのいずれかの結果が発生する。
人iがjラウンド目の試合で出す手はAi,jである。
Ai,jはG,C,Pのいずれかであり、それぞれグー,チョキ,パーを表す。
Mラウンド目終了時点の順位を求めよ。
制約
1<=N<=50
1<=M<=100
Ai,jはG,C,Pのいずれか
考え方
1,人の番号を1ずらす。
1から2N => 0から2N-1
2,ラウンドの番号を1ずらす。
1からM => 0からM-1
3,kを0からにする。
k=1,2...,N => k=0,1,...,N-1
4,順位を0位からにする。
よって,試合のする2人はi-1ラウンド目終了時点の順位が2kと2k+1の人になる。
5,問題文から順位は勝数と番号によって決まる。
勝数が多い方が上位なので,降順にソートする。
勝数が同じとき,番号は小さい方が上位になるようにNから番号を引いた数を仮番号としてつける。
6,素直にじゃんけんをして,勝った方の勝数を増やしていく。
7,1ラウンドN回のじゃんけんをしてMラウンドあるので,2重のfor文で解ける。
M*N=100*50=5000なので大丈夫そう。
8,番号を出力するときはN-仮番号+1と問題文どうりの番号に戻して出力する。
実際のプログラム
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
int main(){
int N,M;
cin >> N >> M;
vector<string> A(2*N);
for(int i = 0; i < 2*N; i++){
cin >> A[i];
}
vector<pair<int, int>> win_number(2*N);
for(int i = 0; i < 2*N; i++){
win_number[i] = make_pair(0, N-i);
}
for(int i = 0; i < M; i++){
sort(win_number.begin(), win_number.end(), greater<pair<int,int>>());
for(int k = 0; k < N; k++){
int p1_num = N-win_number[2*k].second;
string p1 = A[p1_num].substr(i,1);
int p2_num = N-win_number[2*k+1].second;
string p2 = A[p2_num].substr(i,1);
if(p1 == p2){
}else if( (p1=="G"&&p2=="C")||(p1=="C"&&p2=="P")||(p1=="P"&&p2=="G") ){
win_number[2*k].first++;
}else{
win_number[2*k+1].first++;
}
}
}
sort(win_number.begin(), win_number.end(), greater<pair<int,int>>());
for(int i = 0; i < 2*N; i++){
cout << N-win_number[i].second+1 << endl;
}
return 0;