Problem:


Score : 600 points

Problem Statement

There is a game that involves three variables, denoted A, B, and C.

As the game progresses, there will be N events where you are asked to make a choice.
Each of these choices is represented by a string s_i. If s_i is AB, you must add 1 to A or B then subtract 1 from the other; if s_i is AC, you must add 1 to A or C then subtract 1 from the other; if s_i is BC, you must add 1 to B or C then subtract 1 from the other.

After each choice, none of A, B, and C should be negative.

Determine whether it is possible to make N choices under this condition. If it is possible, also give one such way to make the choices.

Constraints

1 \leq N \leq 10^5

0 \leq A,B,C \leq 10^9

N, A, B, C are integers.

s_i is AB, AC, or BC.

Input

Input is given from Standard Input in the following format:

N A B C
s_1
s_2
:
s_N

Output

If it is possible to make N choices under the condition, print Yes; otherwise, print No.

Also, in the former case, show one such way to make the choices in the subsequent N lines. The (i+1)-th line should contain the name of the variable (A, B, or C) to which you add 1 in the i-th choice.

Sample Input 1

2 1 3 0
AB
AC

Sample Output 1

Yes
A
C

You can successfully make two choices, as follows:

In the first choice, add 1 to A and subtract 1 from B. A becomes 2, and B becomes 2.

In the second choice, add 1 to C and subtract 1 from A. C becomes 1, and A becomes 1.

Sample Input 2

3 1 0 0
AB
BC
AB

Sample Output 2

No

Sample Input 3

1 0 9 0
AC

Sample Output 3

No

Sample Input 4

8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB

Sample Output 4

Yes
C
B
B
C
C
B
A
A



Sample input:
2 1 3 0
AB
AC


Sample output:
Yes
A
C

Submission status: Accepted

Solution code:
def main():
    #input
    N, A, B, C = map(int, input().split())
    s = [""] * (N+1)
    for i in range(N):
        s[i] = str(input())

    #i(0, 1, ..., N-1)回目の施行が始まる前のA, B, Cの個数を
    #a[i], b[i], c[i]とする。
    #i回目の施行で選ばれる変数をdp[i]とする。
    #output
    dp = [""] * N
    a, b, c = [0]*(N+1), [0]*(N+1), [0]*(N+1)
    a[0], b[0], c[0] = A, B, C

    #s[i]がABの時
    #   a[i] + b[i] == 0 の時続行不能
    #   a[i] == 1, b[i] == 0 の時 a[i+1] = a[i]-1, b[i+1] = b[i]+1
    #   a[i] == 0, b[i] == 1 の時 a[i+1] = a[i]+1, b[i+1] = b[i]-1
    #   a[i] == 1, b[i] == 1 の時
    #       最後のターンでなければs[i+1]を見て
    #           ABならばどちらでも良い
    #           BCならばa[i+1] = a[i]-1, b[i+1] = b[i]+1
    #           ACならばa[i+1] = a[i]+1, b[i+1] = b[i]-1
    #       最後のターンであればどちらでも良い
    #   a[i] > 1, b[i] > 1の時
    #       a[i] >= b[i]ならばa[i+1] = a[i]-1, b[i+1] = b[i]+1
    #       a[i] < b[i]ならばa[i+1] = a[i]+1, b[i+1] = b[i]-1

    for i in range(N):
        if s[i] == "AB":
            if a[i] + b[i] == 0:
                print("No")
                exit()
            elif a[i] == 1 and b[i] == 0:
                a[i+1] = a[i] - 1
                b[i+1] = b[i] + 1
                c[i+1] = c[i]
                dp[i] = "B"
            elif a[i] == 0 and b[i] == 1:
                a[i+1] = a[i] + 1
                b[i+1] = b[i] - 1
                c[i+1] = c[i]
                dp[i] = "A"
            elif a[i] == 0 and b[i] > 1:
                a[i+1] = a[i] + 1
                b[i+1] = b[i] - 1
                c[i+1] = c[i]
                dp[i] = "A"
            elif a[i] > 1 and b[i] == 0:
                a[i+1] = a[i] - 1
                b[i+1] = b[i] + 1
                c[i+1] = c[i]
                dp[i] = "B"
            elif a[i] == 1 and b[i] == 1:
                if s[i+1] == "":
                    a[i+1] = a[i] - 1
                    b[i+1] = b[i] + 1
                    c[i+1] = c[i]
                    dp[i] = "B"
                elif s[i+1] == "AB":
                    a[i+1] = a[i] + 1
                    b[i+1] = b[i] - 1
                    c[i+1] = c[i]
                    dp[i] = "A"
                elif s[i+1] == "BC":
                    a[i+1] = a[i] - 1
                    b[i+1] = b[i] + 1
                    c[i+1] = c[i]
                    dp[i] = "B"
                elif s[i+1] == "AC":
                    a[i+1] = a[i] + 1
                    b[i+1] = b[i] - 1
                    c[i+1] = c[i]
                    dp[i] = "A"
            elif a[i] == 1 and b[i] > 1:
                a[i+1] = a[i] + 1
                b[i+1] = b[i] - 1
                c[i+1] = c[i]
                dp[i] = "A"
            elif a[i] > 1 and b[i] == 1:
                a[i+1] = a[i] - 1
                b[i+1] = b[i] + 1
                c[i+1] = c[i]
                dp[i] = "B"
            elif a[i] > 1 and b[i] > 1:
                if a[i] >= b[i]:
                    a[i+1] = a[i] - 1
                    b[i+1] = b[i] + 1
                    c[i+1] = c[i]
                    dp[i] = "B"
                elif a[i] < b[i]:
                    a[i+1] = a[i] + 1
                    b[i+1] = b[i] - 1
                    c[i+1] = c[i]
                    dp[i] = "A"
    #ここまでで一段落。
        elif s[i] == "BC":
            if b[i] + c[i] == 0:
                print("No")
                exit()
            elif b[i] == 1 and c[i] == 0:
                b[i+1] = b[i] - 1
                c[i+1] = c[i] + 1
                a[i+1] = a[i]
                dp[i] = "C"
            elif b[i] == 0 and c[i] == 1:
                b[i+1] = b[i] + 1
                c[i+1] = c[i] - 1
                a[i+1] = a[i]
                dp[i] = "B"
            elif b[i] == 0 and c[i] > 1:
                b[i+1] = b[i] + 1
                c[i+1] = c[i] - 1
                a[i+1] = a[i]
                dp[i] = "B"
            elif b[i] > 1 and c[i] == 0:
                b[i+1] = b[i] - 1
                c[i+1] = c[i] + 1
                a[i+1] = a[i]
                dp[i] = "C"
            elif b[i] == 1 and c[i] == 1:
                if s[i+1] == "":
                    b[i+1] = b[i] - 1
                    c[i+1] = c[i] + 1
                    a[i+1] = a[i]
                    dp[i] = "C"
                elif s[i+1] == "BC":
                    b[i+1] = b[i] + 1
                    c[i+1] = c[i] - 1
                    a[i+1] = a[i]
                    dp[i] = "B"
                elif s[i+1] == "AC":
                    b[i+1] = b[i] - 1
                    c[i+1] = c[i] + 1
                    a[i+1] = a[i]
                    dp[i] = "C"
                elif s[i+1] == "AB":
                    b[i+1] = b[i] + 1
                    c[i+1] = c[i] - 1
                    a[i+1] = a[i]
                    dp[i] = "B"
            elif b[i] == 1 and c[i] > 1:
                b[i+1] = b[i] + 1
                c[i+1] = c[i] - 1
                a[i+1] = a[i]
                dp[i] = "B"
            elif b[i] > 1 and c[i] == 1:
                b[i+1] = b[i] - 1
                c[i+1] = c[i] + 1
                a[i+1] = a[i]
                dp[i] = "C"
            elif b[i] > 1 and c[i] > 1:
                if b[i] >= c[i]:
                    b[i+1] = b[i] - 1
                    c[i+1] = c[i] + 1
                    a[i+1] = a[i]
                    dp[i] = "C"
                elif b[i] < c[i]:
                    b[i+1] = b[i] + 1
                    c[i+1] = c[i] - 1
                    a[i+1] = a[i]
                    dp[i] = "B"
    #ここまででもう一段落。
        elif s[i] == "AC":
            if c[i] + a[i] == 0:
                print("No")
                exit()
            elif c[i] == 1 and a[i] == 0:
                c[i+1] = c[i] - 1
                a[i+1] = a[i] + 1
                b[i+1] = b[i]
                dp[i] = "A"
            elif c[i] == 0 and a[i] == 1:
                c[i+1] = c[i] + 1
                a[i+1] = a[i] - 1
                b[i+1] = b[i]
                dp[i] = "C"
            elif c[i] == 0 and a[i] > 1:
                c[i+1] = c[i] + 1
                a[i+1] = a[i] - 1
                b[i+1] = b[i]
                dp[i] = "C"
            elif c[i] > 1 and a[i] == 0:
                c[i+1] = c[i] - 1
                a[i+1] = a[i] + 1
                b[i+1] = b[i]
                dp[i] = "A"
            elif c[i] == 1 and a[i] == 1:
                if s[i+1] == "":
                    c[i+1] = c[i] - 1
                    a[i+1] = a[i] + 1
                    b[i+1] = b[i]
                    dp[i] = "A"
                elif s[i+1] == "AC":
                    c[i+1] = c[i] + 1
                    a[i+1] = a[i] - 1
                    b[i+1] = b[i]
                    dp[i] = "C"
                elif s[i+1] == "AB":
                    c[i+1] = c[i] - 1
                    a[i+1] = a[i] + 1
                    b[i+1] = b[i]
                    dp[i] = "A"
                elif s[i+1] == "BC":
                    c[i+1] = c[i] + 1
                    a[i+1] = a[i] - 1
                    b[i+1] = b[i]
                    dp[i] = "C"
            elif c[i] == 1 and a[i] > 1:
                c[i+1] = c[i] + 1
                a[i+1] = a[i] - 1
                b[i+1] = b[i]
                dp[i] = "C"
            elif c[i] > 1 and a[i] == 1:
                c[i+1] = c[i] - 1
                a[i+1] = a[i] + 1
                b[i+1] = b[i]
                dp[i] = "A"
            elif c[i] > 1 and a[i] > 1:
                if c[i] >= a[i]:
                    c[i+1] = c[i] - 1
                    a[i+1] = a[i] + 1
                    b[i+1] = b[i]
                    dp[i] = "A"
                elif c[i] < a[i]:
                    c[i+1] = c[i] + 1
                    a[i+1] = a[i] - 1
                    b[i+1] = b[i]
                    dp[i] = "C"

    print("Yes")
    for v in dp:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque
import itertools 
import bisect
from sys import stdin, stdout
from itertools import repeat
import sys


# sys.stdin = open('input')
# sys.stdout = open('/mnt/d/Gg/output', 'w')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())




def main():
    n, a, b, c = map(int, raw_input().split())
    da = [a, b, c]
    ans = []
    query = []
    for i in range(n):
        query.append(raw_input().strip())
    
    def get(idx, x, y):
        if da[x]+da[y]==0:
            return
        if da[x]==1 and da[y]==1 and idx < n-1:
            if query[idx][0] not in query[idx+1]:
                ans.append(query[idx][1])
                da[x] -= 1
                da[y] += 1
            else:
                ans.append(query[idx][0])
                da[y] -= 1
                da[x] += 1
            return
        if da[x]>da[y]:
            ans.append(query[idx][1])
            da[y] += 1
            da[x] -= 1 
        else:
            ans.append(query[idx][0])
            da[y] -= 1
            da[x] += 1 

    for i in range(n):
        if query[i] == 'AB':
            get(i, 0, 1)
        elif query[i] == 'AC':
            get(i, 0, 2)
        else:
            get(i, 1, 2)
    if len(ans) < n:
        print "No"
    else:
        print "Yes"
        print '\n'.join(ans)

    
# import time
# pre = time.time()
main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque
import itertools 
import bisect
from sys import stdin, stdout
from itertools import repeat
import sys


# sys.stdin = open('input')
# sys.stdout = open('/mnt/d/Gg/output', 'w')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())




def main():
    n, a, b, c = map(int, raw_input().split())
    da = [a, b, c]
    ans = []
    query = []
    for i in range(n):
        query.append(raw_input().strip())
    
    def get(idx, x, y):
        if da[x]+da[y]==0:
            return
        if da[x]+da[y]==1:
            if da[x]==1:
                ans.append(query[idx][1])
                da[x] -= 1
                da[y] += 1
            else:
                ans.append(query[idx][0])
                da[y] -= 1
                da[x] += 1
            return 
        if da[x]==1 and da[y]==1 and idx < n-1:
            if query[idx][0] not in query[idx+1]:
                ans.append(query[idx][1])
                da[x] -= 1
                da[y] += 1
            else:
                ans.append(query[idx][0])
                da[y] -= 1
                da[x] += 1
            return
        if da[x]>da[y]:
            ans.append(query[idx][1])
            da[y] += 1
            da[x] -= 1 
        else:
            ans.append(query[idx][0])
            da[y] -= 1
            da[x] += 1 

    for i in range(n):
        if query[i] == 'AB':
            get(i, 0, 1)
        elif query[i] == 'AC':
            get(i, 0, 2)
        else:
            get(i, 1, 2)
    if len(ans) < n:
        print "No"
    else:
        print "Yes"
        print '\n'.join(ans)

    
# import time
# pre = time.time()
main()

Submission status: Accepted

Solution code:
#F
import sys
from collections import Counter as cc

N,A,B,C = list(map(int, input().split()))
abc = []
ans = []

for i in range(N):
    abc.append(input())
abc.append("")

a = abc.count("AB")+abc.count("AC")
b = abc.count("AB")+abc.count("BC")
c = abc.count("AC")+abc.count("BC")


for i, (s, ns) in enumerate(zip(abc,abc[1:])):
    if s == "AB":
        if A > B or (A == B and i != N-1 and ("AB" in ns or "BC" in ns)):
            A -= 1
            B += 1
            ans.append("B")
        else:
            A += 1
            B -= 1
            ans.append("A")
    elif s == "AC":
        a -= 1
        c -= 1
        if A > C or (A == C and i != N-1 and ("AC" in ns or "BC" in ns)):
            A -= 1
            C += 1
            ans.append("C")
        else:
            A += 1
            C -= 1
            ans.append("A")
    else:
        c -= 1
        b -= 1
        if B > C or (B == C and i != N-1 and ("AC" in ns or "BC" in ns)):
            C += 1
            B -= 1
            ans.append("C")
        else:
            C -= 1
            B += 1
            ans.append("B")
    if A < 0 or B < 0 or C < 0:
        print("No")
        sys.exit()

print("Yes")
for i in range(N):
    print(str(ans[i]))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,a,b,c = LI()
    t = [a,b,c]
    q = [S() for _ in range(n)] + ["ABC"]
    r = []
    for qi in range(n):
        s = q[qi]
        if s == "AB":
            i = 0
            j = 1
        elif s == "AC":
            i = 0
            j = 2
        else:
            i = 1
            j = 2

        if t[i] < t[j]:
            r.append(i)
            t[i] += 1
            t[j] -= 1
        elif t[i] > t[j]:
            r.append(j)
            t[i] -= 1
            t[j] += 1
        else:
            if t[i] < 1:
                return "No"
            if chr(ord("A") + i) in q[qi+1]:
                r.append(i)
                t[i] += 1
                t[j] -= 1
            else:
                r.append(j)
                t[i] -= 1
                t[j] += 1

    return JA(["Yes"] + list(map(lambda x: chr(ord("A") + x), r)), "\n")

print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,A,B,C = inputMap()
	ans = []
	flg = False
	if 2 == A+B+C:
		flg = True

	inp = []
	for i in range(N):
		tmp = inputStr()
		inp.append(tmp)

	if flg == False:
		for i,val in enumerate(inp):
			if val == "AB":
				if A < B:
					A += 1
					B -= 1
					ans.append("A")
				else:
					A -= 1
					B += 1
					ans.append("B")
			elif val == "AC":
				if A < C:
					A += 1
					C -= 1
					ans.append("A")
				else:
					A -= 1
					C += 1
					ans.append("C")
			else:
				if B < C:
					B += 1
					C -= 1
					ans.append("B")
				else:
					B -= 1
					C += 1
					ans.append("C")

			if A < 0 or B < 0 or C < 0:
				print("No")
				sys.exit()

	else:
		for i,val in enumerate(inp):
			if val == "AB":
				if A == 1 and B == 1 and i+1 < len(inp):
					nextInp = inp[i+1]
					if nextInp == "AB":
						A += 1
						B -= 1
						ans.append("A")
					elif nextInp == "AC":
						A += 1
						B -= 1
						ans.append("A")
					else:
						A -= 1
						B += 1
						ans.append("B")
				else:
					if A < B:
						A += 1
						B -= 1
						ans.append("A")
					else:
						A -= 1
						B += 1
						ans.append("B")
			elif val == "AC":
				if A == 1 and C == 1 and i+1 < len(inp):
					nextInp = inp[i+1]
					if nextInp == "AB":
						A += 1
						C -= 1
						ans.append("A")
					elif nextInp == "AC":
						A += 1
						C -= 1
						ans.append("A")
					else:
						C += 1
						A -= 1
						ans.append("C")
				else:
					if A < C:
						A += 1
						C -= 1
						ans.append("A")
					else:
						A -= 1
						C += 1
						ans.append("C")
			else:
				if B == 1 and C == 1 and i+1 < len(inp):
					nextInp = inp[i+1]
					if nextInp == "AB":
						B += 1
						C -= 1
						ans.append("B")
					elif nextInp == "AC":
						C += 1
						B -= 1
						ans.append("C")
					else:
						C += 1
						B -= 1
						ans.append("C")
				else:
					if B < C:
						B += 1
						C -= 1
						ans.append("B")
					else:
						B -= 1
						C += 1
						ans.append("C")

			if A < 0 or B < 0 or C < 0:
				print("No")
				sys.exit()

	print("Yes")
	for i in ans:
		print(i)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
    N,A,B,C=map(int,input().split())
    d={'AB':(0,1),'AC':(0,2),'BC':(1,2)}
    s=[d[input()] for _ in range(N)]
    abc=[A,B,C]
    ABC='ABC'
    ans=[]
    for i in range(N):
        x,y=s[i]
        # 強制終了
        if abc[x] == abc[y] == 0:
            print('No')
            exit()
        if abc[x] == abc[y] == 1:
            # 最後の要素 or 次に今回選ぶ可能性があるものがあるかどうか
            if (i == N-1) or (x in s[i+1]):
                ans.append(ABC[x])
                abc[x]+=1
                abc[y]-=1
            else:
                ans.append(ABC[y])
                abc[x]-=1
                abc[y]+=1
        # 2数の和が1 or 3以上の場合は大きい方をインクリメント, 小さい方をデクリメントする.
        # 2数が同じ場合には 後半の文字に対応する番号を優先する.
        else:
            if abc[x] > abc[y]:
                ans.append(ABC[y])
                abc[x]-=1
                abc[y]+=1
            else:
                ans.append(ABC[x])
                abc[x]+=1
                abc[y]-=1
    print('Yes')
    for a in ans:
        print(a)

main()

Submission status: Accepted

Solution code:
n,a,b,c=map(int,input().split())
l=[]
for i in range(0,n):
    s=input()
    l.append(s)
final=[]
for i in range(0,len(l)):
    if l[i]=='AB':
        if a>b:
            b+=1
            a-=1
            final.append('B')
        elif a<b:
            b-=1
            a+=1
            final.append('A')
        else:
            if a==0:
                print('No')
                break
            else:
                if i!=len(l)-1:
                    if l[i+1]=='AB':
                        a+=1
                        b-=1
                        final.append('A')
                    elif l[i+1]=='AC':
                        a+=1
                        b-=1
                        final.append('A')
                    else:
                        a-=1
                        b+=1
                        final.append('B')
                else:
                    a-=1
                    b+=1
                    final.append('B')
    elif l[i]=='AC':
        if a>c:
            c+=1
            a-=1
            final.append('C')
        elif a<c:
            c-=1
            a+=1
            final.append('A')
        else:
            if a==0:
                print('No')
                break
            else:
                if i!=len(l)-1:
                    if l[i+1]=='AB':
                        a+=1
                        c-=1
                        final.append('A')
                    elif l[i+1]=='AC':
                        a+=1
                        c-=1
                        final.append('A')
                    else:
                        a-=1
                        c+=1
                        final.append('C')
                else:
                    a-=1
                    c+=1
                    final.append('C')
    else:
        if b>c:
            c+=1
            b-=1
            final.append('C')
        elif b<c:
            c-=1
            b+=1
            final.append('B')
        else:
            if b==0:
                print('No')
                break
            else:
                if i!=len(l)-1:
                    if l[i+1]=='AB':
                        b+=1
                        c-=1
                        final.append('B')
                    elif l[i+1]=='BC':
                        b+=1
                        c-=1
                        final.append('B')
                    else:
                        b-=1
                        c+=1
                        final.append('C')
                else:
                    b-=1
                    c+=1
                    final.append('C')
else:
    print('Yes')
    for i in range(0,len(final)):
        print(final[i])

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())

S=['']*N
for i in range(N):
    S[i]=input()

result=[]
kekka=True


for i in range(N):
    if (A==0 and B==0 and S[i]=='AB') or (C==0 and B==0 and S[i]=='BC') or (A==0 and C==0 and S[i]=='AC'):
        kekka=False
        break
    else:
        if S[i]=='AB':
            if A==0:
                A += 1
                B -= 1
                result.append('A')
            elif B==0:
                A -=1
                B +=1
                result.append('B')
            elif A==1 and B==1 and C==0 and i !=N-1:
                if S[i+1]=='AC':
                    A += 1
                    B -= 1
                    result.append('A')
                else:
                    A -=1
                    B +=1
                    result.append('B')
            elif A>B:
                A -=1
                B +=1
                result.append('B')
            else:
                A +=1
                B -=1
                result.append('A')
        elif S[i]=='AC':
            if A==0:
                A += 1
                C -= 1
                result.append('A')
            elif C==0:
                A -=1
                C +=1
                result.append('C')
            elif A==1 and C==1 and B==0 and i != N-1:
                if S[i+1]=='AB':
                    A += 1
                    C -= 1
                    result.append('A')
                else:
                    A -=1
                    C +=1
                    result.append('C')
            elif A>C:
                A -=1
                C +=1
                result.append('C')
            else:
                A +=1
                C -=1
                result.append('A') 
        else:
            if B==0:
                B += 1
                C -= 1
                result.append('B')
            elif C==0:
                B -=1
                C +=1
                result.append('C')
            elif B==1 and C==1 and A==0 and i != N-1:
                if S[i+1]=='AB':
                    B += 1
                    C -= 1
                    result.append('B')
                else:
                    B -=1
                    C +=1
                    result.append('C')
            elif B>C:
                B -=1
                C +=1
                result.append('C')
            else:
                B +=1
                C -=1
                result.append('B')

if kekka ==False:
    print('No')
else:
    print('Yes')
    for i in range(N):
        print(result[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

n, a, b, c = map(int, input().split())
S = []
for _ in range(n):
    S.append(input())

ans = []
for i in range(n):
    if S[i] == "AB":
        if a == b == 0:
            print("No")
            exit(0)
        elif a < b or (a == b and i != n - 1 and "A" in S[i+1]):
            ans.append("A")
            a += 1
            b -= 1
        else:
            ans.append("B")
            a -= 1
            b += 1
    elif S[i] == "BC":
        if b == c == 0:
            print("No")
            exit(0)
        elif c < b or (c == b and i != n - 1 and "C" in S[i+1]):
            ans.append("C")
            c += 1
            b -= 1
        else:
            ans.append("B")
            c -= 1
            b += 1
    else:
        if c == a == 0:
            print("No")
            exit(0)
        elif c < a or (c == a and i != n - 1 and "C" in S[i+1]):
            ans.append("C")
            c += 1
            a -= 1
        else:
            ans.append("A")
            c -= 1
            a += 1
print("Yes")
print("\n".join(ans))
exit(0)

Submission status: Accepted

Solution code:
n, a, b, c = map(int, input().split())
L = [a, b, c]
X = [0]*n
for i in range(n):
    s = str(input())
    if s == 'AB':
        x, y = 0, 1
    elif s == 'AC':
        x, y = 0, 2
    else:
        x, y = 1, 2
    X[i] = (x, y)

ans = []
for i in range(n):
    x, y = X[i]
    if i != n-1:
        if L[x] == 0 and L[y] == 0:
            print('No')
            exit()
        else:
            if L[x] == 0:
                L[x] += 1
                L[y] -= 1
                ans.append(x)
            elif L[y] == 0:
                L[x] -= 1
                L[y] += 1
                ans.append(y)
            else:
                nx, ny = X[i+1]
                if x in {nx, ny}:
                    L[x] += 1
                    L[y] -= 1
                    ans.append(x)
                else:
                    L[x] -= 1
                    L[y] += 1
                    ans.append(y)
    else:
        if L[x] == 0 and L[y] == 0:
            print('No')
            exit()
        else:
            if L[x] == 0:
                L[x] += 1
                L[y] -= 1
                ans.append(x)
            elif L[y] == 0:
                L[x] -= 1
                L[y] += 1
                ans.append(y)
            else:
                L[x] += 1
                L[y] -= 1
                ans.append(x)

print('Yes')
d = {0:'A', 1:'B', 2:'C'}
for i in range(n):
    print(d[ans[i]])