ABC 166 F - Three Variables Game

問題

長さ $3$ の配列とこのうちの $2$ つからなるペアが $n$ 個与えられる。それぞれのペアに対して片方を選んで $+1$ し、もう一方を $-1$ するという操作を、$3$ つの数字のいずれも負にならないようにしながら $n$ 回終えられることが可能か判定し、可能ならその手順を示せ。

atcoder.jp

解説

基本的には $2$ つの数字のうち小さい方を $-1$ していけばよいが、問題となるのは $A = [1,1,0]$ のような状態で $(0,1)$ が指定され、$A _ 0$ を $-1$ して $A = [0,2,0]$ となり、次に $(0,2)$ が指定されてしまうような状況のみである。この場合は、$(0,1)$ が指定されたときにその次に $(0,2)$ が指定されることを見越して $A _ 0$ を $+1$ しておけばよい。つまり、指定されたインデックスが $(x _ 0,y _ 0)$ で、$A _ {x _ 0} = A _ {y _ 0}$ の場合は次に指定されるインデックス $(x _ 1,y _ 1)$ に対して $x _ 0 = y _ 1$ ならば $A _ {x _ 0}$ を $+1$ する。
また、指定されたインデックス $(x ,y)$ に対して $A _ x = A _ y = 0$ となった時点で、不可能となる。

実装

各 $i$ について、$S _ {i + 1}$ を調べる可能性があるので、$S$ の末尾に番兵として AB を置いている。

n, a, b, c = map(int, input().split())
A = [a, b, c]
D = {'AB': 0, 'BC': 1, 'AC': 2}
S = [input() for i in range(n)]
S.append('AB')
X = []
for i in range(n):
    x, y = D[S[i]], (D[S[i]] + 1) % 3
    if A[x] == 0 and A[y] == 0:
        print('No')
        exit()
    if A[x] < A[y]:
        A[x], A[y] = A[x] + 1, A[y] - 1
        X.append('ABC'[x])
    elif A[x] > A[y]:
        A[x], A[y] = A[x] - 1, A[y] + 1
        X.append('ABC'[y])
    else:
        x1, y1 = D[S[i + 1]], (D[S[i + 1]] + 1) % 3
        if x == y1:
            A[x], A[y] = A[x] + 1, A[y] - 1
            X.append('ABC'[x])
        else:
            A[x], A[y] = A[x] - 1, A[y] + 1
            X.append('ABC'[y])
print('Yes')
print(*X, sep='\n')

atcoder.jp