Edit

【pythonでABC166を解説】F - Three Variables Game

問題概要

問題ページ

F - Three Variables Game
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()

-Edit
-