問題概要
問題ページ
-
-
F - Three Variables Game
問題ページへ移動する
問題文
あるゲームでは \(3\) つの変数があり、それぞれ \(A,B,C\) で表されます。
ゲームの進行と共に、あなたは \(N\) 回の選択に迫られます。
それぞれの選択は文字列 \(s_i\) によって示され、
\(s_i\) が AB のとき、\(A\) と \(B\) のどちらかに \(1\) を足しもう一方から \(1\) を引くこと、
AC のとき、\(A\) と \(C\) のどちらかに \(1\) を足しもう一方から \(1\) を引くこと、
BC のとき、\(B\) と \(C\) のどちらかに \(1\) を足しもう一方から \(1\) を引くことを意味します。
いずれの選択の後にも、\(A,B,C\) のいずれも負の値になってはいけません。
この条件を満たしつつ \(N\) 回すべての選択を終えることが可能であるか判定し、可能であるならそのような選択方法をひとつ示してください。
制約
- \(1 \leq N \leq 10^5\)
- \(0 \leq A,B,C \leq 10^9\)
- \(N, A, B, C\) は整数である。
- \(s_i\) は
AB,AC,BCのいずれか
問題の考察
ACコード
import sys
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, a, b, c = list(map(int, input().rstrip('\n').split()))
abc = [a, b, c]
d = {"A": 0, "B": 1, "C": 2}
s = []
for _ in range(n):
s1, s2 = list(str(input().rstrip('\n')))
s1 = d[s1]
s2 = d[s2]
s.append([s1, s2])
t = a + b + c
if t == 0:
print("No")
exit()
else:
ans = []
for i in range(n):
s1, s2 = s[i]
if abc[s1] + abc[s2] == 0:
print("No")
exit()
else:
if abc[s1] > abc[s2]:
abc[s1] -= 1
abc[s2] += 1
ans.append(s2)
elif abc[s1] < abc[s2]:
abc[s1] += 1
abc[s2] -= 1
ans.append(s1)
else:
if i + 1 < n:
cl = s[i] + s[i + 1]
pos = [cl.count(0), cl.count(1), cl.count(2)]
abc[pos.index(2)] += 1
abc[s1 ^ s2 ^ pos.index(2)] -= 1
ans.append(pos.index(2))
else:
abc[s1] += 1
abc[s2] -= 1
ans.append(s1)
print("Yes")
d = {0: "A", 1: "B", 2: "C"}
for v in ans:
print(d[v])
if __name__ == '__main__':
solve()