EX18 - ゲーム大会 / 2.03 /

Time Limit: 2 sec / Memory Limit: 256 MB

説明ページに戻る

問題文

あるゲーム大会にはN人が参加しM試合が行われました。各参加者には1からNの番号が割り当てられています。

試合に関する情報が与えられるので、M回の試合がすべて終了した時点での試合結果の表を作成し、出力してください。

ただし、同じ参加者のペアについて2回以上試合が行われることはないとします。


試合に関する情報は以下のような形式で与えられます。

試合に関する情報
試合1で勝った人の番号A_1 試合1で負けた人の番号B_1
試合2で勝った人の番号A_2 試合2で負けた人の番号B_2
\vdots \vdots
試合Mで勝った人の番号A_M 試合Mで負けた人の番号B_M

同じ参加者のペアについて2回以上試合が行われることはありません。
例えば、次のような情報が与えられることはありません。

1 2
2 1

試合結果の表とは、縦N行、横N列からなる次のような表Rです。

試合結果の表
R_{1, 1} R_{1, 2} R_{1, 3} \cdots R_{1, N}
R_{2, 1} R_{2, 2} R_{2, 3} \cdots R_{2, N}
R_{3, 1} R_{3, 2} R_{3, 3} \cdots R_{3, N}
\vdots  \vdots  \vdots  \vdots  \ddots  \vdots
R_{N, 1} R_{N, 2} R_{N, 3} \cdots R_{N, N}

R_{i, j}の値は以下のように決まります。

i番の参加者とj番の参加者が試合をして、

  • i番の参加者が勝ったならR_{i, j} = o
  • i番の負けたならR_{i, j} = x

i番の人とj番の人が試合を行っていない場合

  • R_{i, j} = -

以下に具体例を示します。

具体例

  • 3人が参加した
  • 2試合行われた
  • 試合に関する情報は次の通り
1 2
3 1

この場合の試合結果の表は次のようになります。

- o x
x - -
o - -
  • 1番の人と2番の人が試合を行い、1番の人が勝ったので、R_{1, 2} = oR_{2, 1} = x
  • 3番の人と1番の人が試合を行い、3番の人が勝ったので、R_{1, 3} = xR_{3, 1} = o

ただし、各行の行末に空白を含まないことに注意してください。


サンプルプログラム
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A.at(i) >> B.at(i);
  }

  // ここにプログラムを追記
  // (ここで"試合結果の表"の2次元配列を宣言)
}
行末に空白を含めない出力の仕方

以下は配列の要素を空白区切りで出力し末尾には空白を含めないようにする方法の1例です。

vector<int> a = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
  cout << a.at(i);
  if (i == 4) {
    cout << endl; // 末尾なら改行
  }
  else {
    cout << " ";  // それ以外なら空白
  }
}

制約

  • 1≦N≦100
  • 0≦M≦4950
  • 1≦A_i, B_i≦N (1 ≦ i ≦ M)
  • A_i \neq B_i (1 ≦ i ≦ M)
  • 同じ参加者のペアで2回以上試合が行われることはない
  • 入力はすべて整数

入力

入力は次の形式で標準入力から与えられます。

N M
A_1 B_1
A_2 B_2
A_3 B_3
: :
A_M B_M

出力

M試合が終了した時点での試合結果の表を出力してください。

ただし、各行の行末に空白を含まないことに注意してください。


ジャッジでは以下の入力例以外のケースに関してもテストされることに注意。

入力例1

3 2
1 2
3 1

出力例1

- o x
x - -
o - -
  • 1番の人と2番の人が試合を行い、1番の人が勝ったので、R_{1, 2} = oR_{2, 1} = x
  • 3番の人と1番の人が試合を行い、3番の人が勝ったので、R_{1, 3} = xR_{3, 1} = o

入力例2

7 12
1 5
5 4
6 2
1 7
2 4
6 3
1 3
6 4
3 7
5 7
4 3
6 1

出力例2

- - o - o x o
- - - o - x -
x - - x - x o
- x o - x x -
x - - o - - o
o o o o - - -
x - x - x - -

入力例3

1 0

出力例3

-

ヒント

クリックでヒントを開く まずは、試合結果の表をプログラムで管理するために、N×Nの2次元配列を用意しましょう。 この2次元配列の型は、表の要素となる-, o, xの型なので、char型にすれば良いです。

縦a行、横b列の2次元配列の宣言方法は次の通りでした。

vector<vector<要素の型>> 変数名(a, vector<要素の型>(b));


解答例

必ず自分で問題に挑戦してみてから見てください。

クリックで解答例を見る

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A.at(i) >> B.at(i);
  }

  // N×Nのchar型の2次元配列のすべての要素を'-'で初期化
  vector<vector<char>> table(N, vector<char>(N, '-'));

  for (int i = 0; i < M; i++) {
    // 1〜N → 0〜N-1 に変換
    A.at(i)--; B.at(i)--;
    table.at(A.at(i)).at(B.at(i)) = 'o';  // AはBに勝った
    table.at(B.at(i)).at(A.at(i)) = 'x';  // BはAに負けた
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << table.at(i).at(j);
      if (j == N - 1) {
        cout << endl;  // 行末なら改行
      }
      else {
        cout << " ";  // 行末でないなら空白を出力
      }
    }
  }
}