Language: C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}

using piii = pair<int,pair<int,int>>;

bool issafe(const piii& a, const piii& b){
  if(a.first+b.first < 0) return false;
  if(a.second.first+b.second.first < 0) return false;
  if(a.second.second+b.second.second < 0) return false;
  return true;
}

piii pls(const piii& a, const piii& b){
  piii res;
  res.first = a.first+b.first;
  res.second.first = a.second.first + b.second.first;
  res.second.second = a.second.second + b.second.second;
  return res;
}

int main(){
  ll N,A,B,C; cin >> N >> A >> B >> C;
  vector<string> S(N);
  rep(i,N){
    cin >> S[i];
  }
  piii start = {A,{B,C}};
  vector<unordered_set<pair<piii,piii>>> dp(N+1);
  piii aa = {0,{0,0}};
  dp[0].insert(make_pair(aa,aa));
  rep(i,N){
    for(auto a: dp[i]){
      piii now = a.second;
      if(S[i] == "AB"){
        piii tmp1 = now;
        piii tmp2 = now;
        tmp1.first++; tmp1.second.first--;
        tmp2.first--; tmp2.second.first++;
        if(issafe(start,tmp1)) dp[i+1].insert(make_pair(now, tmp1));
        if(issafe(start,tmp2)) dp[i+1].insert(make_pair(now, tmp2));
      }
      else if(S[i] == "BC"){
          piii tmp1 = now;
          piii tmp2 = now;
          tmp1.second.first++; tmp1.second.second--;
          tmp2.second.first--; tmp2.second.second++;
          if(issafe(start,tmp1)) dp[i+1].insert(make_pair(now, tmp1));
          if(issafe(start,tmp2)) dp[i+1].insert(make_pair(now, tmp2));
      }
      else if(S[i] == "AC"){
          piii tmp1 = now;
          piii tmp2 = now;
          tmp1.first++; tmp1.second.second--;
          tmp2.first--; tmp2.second.second++;
          if(issafe(start,tmp1)) dp[i+1].insert(make_pair(now, tmp1));
          if(issafe(start,tmp2)) dp[i+1].insert(make_pair(now, tmp2));
      }
    }
  }
  if(sz(dp[0])==0){
    cout << "No" << endl;
    return 0;
  }


  vector<piii> sol;

  for(auto a: dp[N]){
    auto now = a;
    sol.pb(now.second);
    for(int i=1; N-1>=0; i++){
      piii past = now.first;
      piii pa, pb;
      if(S[N-i] == "AB"){
        pa = {1, {-1, 0}};
        pb = {-1, {1, 0}};
      }
      if(S[N-i] == "BC"){
        pa = {0, {1, -1}};
        pb = {0, {-1, 1}};
      }
      if(S[N-i] == "AC"){
        pa = {1, {0, -1}};
        pb = {-1, {0, 1}};
      }
      if(dp[N-1].find(make_pair(pls(past,pa), past)) != dp[N-1].end()){
        sol.pb(pls(past, pa));
        now = make_pair(pls(past,pa), past);
      }
      else {
        sol.pb(pls(past,pb));
        now = make_pair(pls(past,pb), past);
      }
    }
    break;
  }
  reverse(all(sol));
  rep(i,N){
    piii past = sol[i];
    piii now = sol[i+1];
    if(past.first+1==now.first) cout << 'A' << endl;
    else if(past.second.first+1==now.second.first) cout << 'B' << endl;
    else if(past.second.second+1==now.second.second) cout << 'C' << endl;
  }
  return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:54:17: warning: narrowing conversion of 'A' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   54 |   piii start = {A,{B,C}};
      |                 ^
In file included from /usr/include/c++/14/bits/hashtable.h:35,
                 from /usr/include/c++/14/bits/unordered_map.h:33,
                 from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/c++/14/functional:63,
                 from a.cc:5:
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) const [with _Key = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >; _Value = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >; _ExtractKey = std::__detail::_Identity; _Hash = std::hash<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]':
/usr/include/c++/14/bits/hashtable.h:1740:46:   required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::find(const key_type&) [with _Key = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >; _Value = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >; _Alloc = std::allocator<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _Hash = std::hash<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; iterator = std::__detail::_Insert_base<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >, std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >, std::allocator<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >, std::__detail::_Identity, std::equal_to<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >, std::hash<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; key_type = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >]'
 1740 |       __hash_code __code = this->_M_hash_code(__k);
      |                            ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/unordered_set.h:658:25:   required from 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::iterator std::unordered_set<_Value, _Hash, _Pred, _Alloc>::find(const key_type&) [with _Value = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >; _Hash = std::hash<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _Pred = std::equal_to<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _Alloc = std::allocator<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; iterator = std::__detail::_Insert_base<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >, std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >, std::allocator<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >, std::__detail::_Identity, std::equal_to<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >, std::hash<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; key_type = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >]'
  658 |       { return _M_h.find(__x); }
      |                ~~~~~~~~~^~~~~
a.cc:113:22:   required from here
  113 |       if(dp[N-1].find(make_pair(pls(past,pa), past)) != dp[N-1].end()){
      |          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: error: static assertion failed: hash function must be invocable with an argument of key type
 1335 |         static_assert(__is_invocable<const _Hash&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: note: 'std::__is_invocable<const std::hash<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >&, const std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >&>()' evaluates to false
/usr/include/c++/14/bits/hashtable_policy.h:1337:25: error: no match for call to '(const std::hash<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >) (const std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > >&)'
 1337 |         return _M_hash()(__k);
      |                ~~~~~~~~~^~~~~
In file included from /usr/include/c++/14/bits/alloc_traits.h:33,
                 from /usr/include/c++/14/ext/alloc_traits.h:34,
                 from /usr/include/c++/14/bits/basic_string.h:39,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_construct.h: In instantiation of 'void std::_Construct(_Tp*, _Args&& ...) [with _Tp = unordered_set<pair<pair<int, pair<int, int> >, pair<int, pair<int, int> > > >; _Args = {}]':
/usr/include/c++/14/bits/stl_uninitialized.h:643:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = std::unordered_set<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >*; _Size = long unsigned int; bool _TrivialValueType = false]'
  643 |                 std::_Construct(std::__addressof(*__cur));
      |                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:712:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = unordered_set<pair<pair<int, pair<int, int> >, pair<int, pair<int, int> > > >*; _Size = long unsigned int]'
  710 |       return __uninitialized_default_n_1<__is_trivial(_ValueType)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  711 |                                          && __can_fill>::
      |                                          ~~~~~~~~~~~~~~~~
  712 |         __uninit_default_n(__first, __n);
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:779:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, allocator<_Tp>&) [with _ForwardIterator = unordered_set<pair<pair<int, pair<int, int> >, pair<int, pair<int, int> > > >*; _Size = long unsigned int; _Tp = unordered_set<pair<pair<int, pair<int, int> >, pair<int, pair<int, int> > > >]'
  779 |     { return std::__uninitialized_default_n(__first, __n); }
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1720:36:   required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(size_type) [with _Tp = std::unordered_set<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _Alloc = std::allocator<std::unordered_set<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > > >; size_type = long unsigned int]'
 1720 |           std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1721 |                                            _M_get_Tp_allocator());
      |                                            ~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:558:9:   required from 'std::vector<_Tp, _Alloc>::vector(size_type, const allocator_type&) [with _Tp = std::unordered_set<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > >; _Alloc = std::allocator<std::unordered_set<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > > >; size_type = long unsigned int; allocator_type = std::allocator<std::unordered_set<std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, int> > > > >]'
  558 |       { _M_default_initialize(__n); }
      |         ^~~~~~~~~~~~~~~~~~~~~
a.cc:55:48:   required from here
   55 |   vector<unordered_set<pair<piii,piii>>> dp(N+1);
      |                                                ^
/usr/include/c++/14/bits/stl_construct.h:119:7: error: use of deleted function 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set() [with _Value = std::pair<std::pair<int, std::pair<int, int> >, std::pair<int, std::pair<int, i