ABC166 F - Three Variables Game

問題原文

atcoder.jp

解法

全部の数がある程度大きければ適当にやっていけばできそうなことがわかる。

ということでできるパターンのギリギリ、あるいは死ぬパターンを考える。

0 0 0 の場合

問答無用で死ぬ。

1 0 0 の場合

0 0 の部分を操作されると死ぬ。

1 1 0 の場合

1 1 を指定されると 0 0 がどこかに生まれ、その次に生まれた 0 0 を指定されると死ぬ

1 1 1 の場合

適当に少ない方を助けるように動いてけばよさそう。
例えば１回操作すると 2 1 0 とかになるけど、 1 1 がないので１つ前のパターンみたいに慎重になる必要はない。
なんとなく 0 1 2 の３種類のことだけ考えれば良さそうなことがわかる。

0 0 0 と 1 0 0 はどうしようもない時はどうしようもないので、 1 1 0 のパターンをいかに Yesにするかを考える。
2 0 0 を作って １手空くと 1 1 0, 1 0 1 のどちらかには戻れるので、死ぬとしたら直後のターンであることがわかる。
よって次のターンのことを考えて死なないように選ぶのが最適。

実装

頑張ってまとめてみたかったんです。。。

N, A, B, C = map(int, input().split())
S = [input() for _ in range(N)]

A, B, C = min(A, 2), min(B, 2), min(C, 2)
X = [0, A, B, C]  # 1-indexecの方が楽そう
F = {1: 'A', 2: 'B', 3: 'C'}

ans = []
for k, s in enumerate(S):
    if s == 'AB':
        i, j = 1, 2
    elif s == 'BC':
        i, j = 2, 3
    elif s == 'AC':
        i, j = 1, 3

    if X[i] > X[j]:
        X[i] -= 1
        X[j] += 1
        ans.append(j)

    elif X[i] < X[j]:
        X[i] += 1
        X[j] -= 1
        ans.append(i)

    else:
        if (X[i] == X[j] == 1) and (k < N - 1):
            if ((S[k + 1][0] == F[i]) and (S[k + 1][1] == F[i ^ j])) or ((S[k + 1][0] == F[i ^ j]) and (S[k + 1][1] == F[i])):
                X[i] += 1
                X[j] -= 1
                ans.append(i)
            else:
                X[j] += 1
                X[i] -= 1
                ans.append(j)
        else:
            X[i] -= 1
            X[j] += 1
            ans.append(j)

    if any([x < 0 for x in X]):
        print('No')
        exit()

print('Yes')
for a in ans:
    print(F[a])

感想

1 ^ 2 = 3, 1 ^ 3 = 2, 2 ^ 3 = 1、どこかで役に立つかもしれない。