game大会-練習問題 | atcoder

N人がM試合する大会の試合結果を入力し、試合結果を表にして出力するという問題

1, 2, 3, ...N人目までの数字がそのまま人の番号になっている。

試合結果の入力は１試合毎に２列で書て改行する。

左側が勝ったひとの番号、右側が負けた人の番号を表している。

例えば、
番号１と番号２の２人が１試合して、番号１が勝って番号２が負けた場合は、下記のように入力する。

入力
2 1

この結果を表にして下記のように出力する。

出力
- o
x -

・試合をしていない番号のペアは" - "を出力。
・自分自身と重なる箇所は" - "を出力
・勝った箇所には" o "を出力
・負けた箇所には" x "を出力

練習問題なので下記のようにはじめからヒントのコードが与えられています。N, Mの入力と試合結果の入力を受け取るためのコードです。

#include <bits/stdc++.h>
using namespace std;
int main() {
 int N, M;
 cin >> N >> M;
 
 //勝った人の番号を配列A, 負けた人の番号を配列Bに保存する
 vector<int> A(M), B(M);
 for (int i = 0; i < M; i++) {
   cin >> A.at(i) >> B.at(i);
 }
 
 // "試合結果の表"の2次元配列を宣言
 
}

勝った人の配列と負けた人の配列を分けているところがポイント。
配列を分けることにメリットがあることが問題を解きはじめた時点では恐らくわからないので、自分だったらなかなか思いつかないだろうなと思いました。普通に一つの配列に保存しそうです。

続いて、受け取った入力をもとにして試合結果の表を出力するためのコードを書いていきます。

・試合結果の表を表す配列を作成する(2次元配列)
試合結果の表は下のように2次元配列になる(N=3, M=2の場合)

番号1の行は番号1と他の番号の試合結果を入れ、
番号2の行は番号2と他の番号の試合結果を入れ、
…
といった感じになっている。

2次元配列の添字で表現すると、下記のようになる。

(1, 1) (1, 2) (1, 3)
(2, 1) (2, 2) (2, 3)
(3, 1) (3, 2) (3, 3)

この添字(i, j)が試合に1対1に対応している。
例えば、番号1と番号2が試合して番号1が勝ちの場合は、(1, 2)の添字の要素
に“o”が入り、(2, 1)の添字の要素に”x”が入る。

まず試合結果の表を宣言するので、上記のような2次元配列を宣言する。

表はN*Nの表になるので、2次元配列の要素数はNとなる。
また、表で自分自身の番号と重なるところは”-”,
試合をやっていないところも”-”を入れるので、
2次元配列の初期値として”-”をはじめから入れておけばよさそう。

そして試合したところだけ結果を上書きする感じでいく。なので、試合結果表の配列は下記のように宣言する。

vector<vector<char>> vec(N, vector<char>(N, '-'));

上記配列でN=3の時は、下記のように表が初期化される。
- - -
- - -
- - -

次は、入力から受け取った試合結果を試合結果の配列に上書きする。

入力から受け取った試合結果は配列A、Bに入れたので、これを利用する。

A.at(i)とB.at(i)のペアが、行った試合を表しているので、
A.at(i)の値とB.at(i)の値が例えば
A.at(0) = 1, B.at(0) = 2の場合は、
試合結果の表の配列の添字(1, 2)の要素に”o”を代入し
試合結果の表の配列の添字(2, 1)の要素に”x”を代入すればいい。

ここで問題が発生する。

(1, 1) (1, 2) (1, 3)
(2, 1) (2, 2) (2, 3)
(3, 1) (3, 2) (3, 3)

上記の表のように添字がなっていればいいけど、実際は試合結果の表の添字は、

(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)

のように、添字は0から始まるので、(i, j)ともに1ずれているため、配列A、Bの結果を利用して試合結果の表の添字の要素に代入するときには、添字の値を補正しないといけない。

A.at(0) = 1, B.at(0) = 2を利用して、結果の表の配列の添字(1, 2)の要素に”o”を代入し、試合結果の表の配列の添字(2, 1)の要素に”x”を代入したい時は、
実際には(0, 1)に”o”を代入し(1, 0)に”x”を代入する。

A.at(i), B.at(i)の値が添字になるので、値をx、yと置いて、値を変数に保存。

後は、試合結果の表の添字に上記値を代入するときに、

X-1, y-1として補正を行うとちょうど意図した通りに表が出来上がる。

for(int i = 0; i < M; i++){
               int x = A.at(i);
               int y = B.at(i);
               vec.at(x-1).at(y-1) = 'o';
               vec.at(y-1).at(x-1) = 'x';
}

最後に、試合結果の表の配列を出力したら完成。

出力するとき、表の要素の間にスペースを入れないままコードを提出すると、

WA(wrong answer)になります。

行の末尾まで来たら改行を出力し、末尾じゃないならスペースを出力するように条件分岐する。ここはヒントをそのまま使いました。

for(int i = 0; i < N; i++){
       for(int j = 0; j < N; j++){
               cout << vec.at(i).at(j);
               if(j == N - 1) {
                               cout << endl;
                       }
                       else {
                               cout << " ";
                       }
               }
}

完成したコードは下記のようになりました。

#include <bits/stdc++.h>
using namespace std;
int main() {
 int N, M;
 cin >> N >> M;
 
 //勝った人の番号を配列A, 負けた人の番号を配列Bに保存する
 vector<int> A(M), B(M);
 for (int i = 0; i < M; i++) {
   cin >> A.at(i) >> B.at(i);
 }
 
 // "試合結果の表"の2次元配列を宣言 
 vector<vector<char>> vec(N, vector<char>(N, '-'));
 
 // 試合結果を試合結果の表に代入
 for(int i = 0; i < M; i++){
       int x = A.at(i);
       int y = B.at(i);
       vec.at(x-1).at(y-1) = 'o';
       vec.at(y-1).at(x-1) = 'x';
 }
  // 試合結果の表を出力
  for(int i = 0; i < N; i++){
       for(int j = 0; j < N; j++){
             cout << vec.at(i).at(j);
             if(j == N - 1) {
                   cout << endl;
             }
             else {
                   cout << " ";
             }
       }
  }
}

入力
1 2
3 1

出力
- o x
x - -
o - -