マトリョーシカ的日常

ワクワクばらまく明日のブログ。

つみかさねるタイルのように(SRM 453 div2 level1)

トーナメントの勝ち点から導け!

 hello, world - 無料写真検索fotoq
photo by oskay

 正答率95%なので簡単かと思ったら、意外と難しかった。でも考え方が分かると、実装するまで時間はかからない。ひらめきが必要な問題なのかな。


 TopCoder Statistics - Problem Statement


 問題:各チーム一対一で対戦します。勝利すると2点、負けると0点、引き分けでは二チームにそれぞれ1点ずつ入ります。どのチームと何回するかという制限はありません。(一度も戦わないチームもあります。)

 各チームのゲーム終了時の勝ち点の合計が配列として二与えられたとき、そこから最小の対戦回数を返しなさい。

 

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;
 class TheTounamentDivTwo{
    public:
     int find(vector <int> A){
         int answer=0;
         
         vector <int> B;
         printf("\n");
         for(int i=0;i<A.size();i++){
             B.push_back(A[i]%2);
             answer+=A[i]/2;
             printf("%d ",B[i]);
         }
         
         int sum=accumulate(B.begin(),B.end(),0);
         printf("\n a=%d:sum=%d:return=%d\n",answer,sum,sum/2+answer);
         printf((sum%2==0)? "ok\n":"no\n");
         return ((sum%2==0)? (sum/2+answer):-1);
    }
};

int main(){
    TheTounamentDivTwo ob1;
    int a[]={2, 3, 7, 20};
    vector <int> b(a,a+4);
    
    for(int j=0;j<b.size();j++){
        printf("%d ",b[j]);
    }
    ob1.find(b);
    return 0;
}
  • まず、各チームの勝ち点を2で割ります。この商がそのチームが勝った試合の回数です。
  • そしてそのあまりを配列Bに入れます。
  • 商の合計を総試合数に足します。
  • 余りの配列は0か1の要素をもつ配列です。引き分けの場合は各チームに1点ずつ入るので、要素1をもつチームが偶数個ないといけません。
  • 偶数個ない場合は-1を返し、あるときは総試合数に配列B合計/2を足します。
  • sumはaccumulateを用います。numericをinclude。