問題

数字 $1, 2, 3$ がそれぞれ $a$ 個、 $b$ 個、 $c$ 個黒板にかかれている。この状況下で、以下の操作を行う。

2つの異なる数字を1個ずつ選び黒板から消し、それらとは異なる数字を黒板に1個追加する。

例えば、黒板に $1, 1, 1, 2, 3, 3$ と書かれていた場合、 $1, 3$ を消して $2$ を追加することにより、黒板には $1, 1, 2, 3, 2$ と書かれることになる。

この操作を繰り返し行い、黒板に書かれている数字を1種類にするとき、どの数字にすることが可能なのか判定せよ。

入力

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

その後、 $t$ 個のテストケースのそれぞれに対して、整数 $a, b, c$ が与えられる。

条件

$1 \leq t \leq {10}^{5}$
$1 \leq a, b, c \leq 100$

出力

1つのテストケースにつき、1行に3つの数字を次の順に出力すること。

1つ目: 最終的に数字を $1$ のみにできるならば $1$ を、できないならば $0$ を出力する。
2つ目: 最終的に数字を $2$ のみにできるならば $1$ を、できないならば $0$ を出力する。
3つ目: 最終的に数字を $3$ のみにできるならば $1$ を、できないならば $0$ を出力する。

解法

最終的に数字を1種類にできるかどうかを判定する問題なので、 $\mathrm{dp[a][b][c][num]}$ を、「黒板に $1, 2, 3$ がそれぞれ $a, b, c$ 個あるときに、最終的に数字 $\mathrm{num}$ のみにすることができるかどうか」を表す bool 値として定義します。（ true ならば可能で、 false ならば不可能とします。また、 $\mathrm{num} = 1, 2, 3$ とします。）

$a, b, c \geq 1$ とするとき、手元に $1, 2, 3$ がそれぞれ $a, b, c$ 個残っているとするならば、次の遷移として考えられるのは

$2, 3$ を消して $1$ を追加する: $(a, b, c) \rightarrow (a + 1, b - 1, c - 1)$
$3, 1$ を消して $2$ を追加する: $(a, b, c) \rightarrow (a - 1, b + 1, c - 1)$
$1, 2$ を消して $3$ を追加する: $(a, b, c) \rightarrow (a - 1, b - 1, c + 1)$

の3通りです。

従って、この3通りのうちのいずれかが遷移を繰り返して、最終的に $\mathrm{num}$ のみという状況を作れば目標を達成できるので、 \begin{align} \mathrm{dp[a][b][c][num]} = & \ \mathrm{dp[a + 1][b - 1][c - 1][num]} \\ & | \ \mathrm{dp[a - 1][b + 1][c - 1][num]} \\ & | \ \mathrm{dp[a - 1][b - 1][c - 1][num]} \end{align} であると言えます。

また $a, b, c$ のうちいずれか1つのみ $0$ のときは、遷移内の要素の値が $-1$ になるものを除けば計算ができます。その上で、

$a \gt 0$ かつ $b = c = 0$ のとき: $\mathrm{num} = 1$ ならば true 、そうでないならば false
$b \gt 0$ かつ $c = a = 0$ のとき: $\mathrm{num} = 2$ ならば true 、そうでないならば false
$c \gt 0$ かつ $a = b = 0$ のとき: $\mathrm{num} = 3$ ならば true 、そうでないならば false

がそれぞれ言えます。

以上から、この $\mathrm{dp}$ について、与えられた $a, b, c$ をもとに $\mathrm{num} = 1, 2, 3$ のそれぞれについて再帰的に求めることで、答えを出すことができます。

ここで再帰について、同じ $a, b, c$ の値であれば答えが変わることはないので、「一度計算したことがあるかどうかを記録し、計算したことがあるのならばその答えを返す」ということを行うことで、重複して計算されることを防ぐことができます。

$1 \leq a, b, c \leq 100$ であることから、最大で同じ整数が $200$ 個黒板に並べられます。すなわち、最大で ${200}^{3} \times {3}$ 個程度の計算を行うことが考えられますが、1つについては $O(1)$ で算出されると言えるので、これは実行時間制限に十分間に合うと考えられます。

ソースコード

整数 $a, b, c$ が与えられた状態で、黒板に書かれた数字をすべて $\mathrm{num}$ にできるかどうかを判定する関数 solve() を以下のように実装しました。なお、 $\mathrm{num}$ については解法中では $\mathrm{num} = 1, 2, 3$ としましたが、インデックスの関係からコード上では $\mathrm{num} = 0, 1, 2$ として扱っています。

bool dp[205][205][205][3]; // a, b, c は最大で200になりえるので、それを想定した配列の要素数にする
bool visited[205][205][205][3]; // (a, b, c, num) の組について計算したことがあるかどうかを記録する

bool solve(int a, int b, int c, int num) {
  if (visited[a][b][c][num]) {
    return dp[a][b][c][num]; // もし計算したことがあるのならば、そのまま dp の値を返す
  }

  visited[a][b][c][num] = true; // 与えられた (a, b, c, num) について計算したことにする

  // a, b, c のうち2つが0であるときについて
  if (b == 0 && c == 0) {
    return dp[a][b][c][num] = (num == 0);
  }
  if (c == 0 && a == 0) {
    return dp[a][b][c][num] = (num == 1);
  }
  if (a == 0 && b == 0) {
    return dp[a][b][c][num] = (num == 2);
  }

  bool ans = false; // 答えとなる bool 値
  if (b >= 1 && c >= 1) {
    ans |= solve(a + 1, b - 1, c - 1, num); // 次に遷移するところを調べて、 OR を取る
  }
  if (c >= 1 && a >= 1) {
    ans |= solve(a - 1, b + 1, c - 1, num);
  }
  if (a >= 1 && b >= 1) {
    ans |= solve(a - 1, b - 1, c + 1, num);
  }

  return dp[a][b][c][num] = ans; // dp[a][b][c][num] に得られた値を記録して返す
}

提出したコード: https://codeforces.com/contest/1900/submission/237690329
GitHub

感想

多分再帰を使わなくてもこの問題は解けるんじゃないかなと思います。ですが、この方法が真っ先に思いついてしまったので、今回はこのような解法を記しています。

yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

B - Laura and Operations / Codeforces Round 911 (Div. 2)

問題

入力

条件

出力

解法

ソースコード

感想