Three Variables Game - abc 166 f

.#構築 #ゲーム

問題
https://atcoder.jp/contests/abc166/tasks/abc166_f

正解

具体例で Yes にし続ける方法を考える

例 1
100 100 100
常に, 少ない方に +1 するようにすればよさそう
同じ値の場合でも, 99 未満にはならないし, どっちでもいい

99 未満にならないこと
最初の状態 100 100 100 (1).
AB で 99 101 100 (2) になったとする.
BC が来たら, 99 100 101 で (2) と同様の状態
BC でなく AB だとすると, 100 100 100 で (1) と同様の状態
どちらとも違って AC だとすると, 100 101 99 で, (2).

例 2
0 1 0 (1)
AC なら終わり

AB とする.
1 0 1 で, (1).
AB でなく, BC とすると, 0 1 0 から 0 0 1 で, (1).

要は, 常に 1 つ終わりの選択肢があり, 2 つは生き残れる.

例 3
0 2 0 (1)
AB
1 1 0 (2)
実は, もう No にならないことが確定した

2 つを 0 にするため, AB が次に来るのを考える
どっちを 0 にするかは, 次 C と組で出る文字次第.

1 1 0 から, AB, AC とする
2 0 0
1 0 1
これは (2) と同様の状態であり, 後は繰り返し

間違いの考え

AB, AC, BC に対して各々最初に操作を決めれば, 以降 1 つ前の同じ文字列のときと逆の操作をする
そうすれば, だいたいもとの A, B, C の値に落ち着きそう

ケース
4 1 0 1
AB
AC
AB
BC

Yes

AB で 0 1 1 になるしかない (A -1, B +1)
AC で 1 1 0 になるしかない
もとの A, B, C に近づけようと, 前の AB の逆をやる (A +1, B -1)
2 0 0
(ここで, 0 2 0 ともできた)
次, BC がきて, 2 0 0 から負の数が出る