B - Not Quite Latin Square / Codeforces Round 918 (Div. 4)

問題

A, B, C の3文字からなる 行列のうち、以下の条件を満たすものについて考える。

• それぞれの行について、 A, B, C が必ず1文字ずつ存在する
• それぞれの列について、 A, B, C が必ず1文字ずつ存在する

この条件を満たす行列として、例えば \begin{align} \begin{bmatrix} \mathrm{A} & \mathrm{B} & \mathrm{C} \\ \mathrm{C} & \mathrm{A} & \mathrm{B} \\ \mathrm{B} & \mathrm{C} & \mathrm{A} \end{bmatrix} \end{align} が挙げられる。

1要素が ? になっている 行列が与えられるとき、 ? がどの文字になれば上記の条件を満たす行列になるのか答えよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 が与えられる。

その後、 個のテストケースのそれぞれに対して、3行にわたり 行列の文字が与えられる。

条件

• 実行時間制限: 1s
• メモリ制限: 256MB
• 
• 行列として与えられる文字は A, B, C, ? のいずれかであり、 ? は1つのみ与えられる。
  • ? を A, B, C のいずれかの文字に変えたとき、必ず条件を満たすものが存在する。

解法

行列のうち ? が含まれる行に着目します。 問題の条件から、この着目している行の中に A, B, C のうちのいずれかの文字が出現しないことになります。

従って、この行にて出現していない文字が答えとなります。

ソースコード

各テストケースに対して、答えとなる文字を返す関数 solve() を以下のように実装しました。

char s[3][3]; // 文字で構成された 3 x 3 行列

char solve() {
  int row; // 着目する行番号を表す整数 row
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> s[i][j]; // 値の入力
      if (s[i][j] == '?') {
        row = i; // '?' が入力されたら、 row の値を決定する
      }
    }
  }

  bool visited[3] = {}; // 'A', 'B', 'C' の文字が現れたかを管理する配列 visited
  for (int j = 0; j < 3; j++) {
    if (s[row][j] == '?') {
      continue; // '?' は visited には関係ないので無視する
    }
    visited[s[row][j] - 'A'] = true; // (文字 - 'A') のインデックスを true にする
  }

  for (char i = 'A'; i <= 'C'; i++) {
    if (!visited[i - 'A']) { // visited のうち、false になっているものが答えとなる
      return i;
    }
  }

  return 0;
}

• 提出したコード: https://codeforces.com/contest/1915/submission/240080109
• GitHub

感想

問題自体の難易度は易しいと思いますが、その割には実装が少し面倒でした。