yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

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;