TopCoderOpen 2022 Round2A : Hard ThreeWaySplit

しょうもないミスばかり。
https://community.topcoder.com/stat?c=problem_statement&pm=17592&rd=19223

問題

N要素の整数列が与えられる。
この要素をA,B,Cの3人で分ける。
その際、AとBの選んだ要素の総和が、一致するようにしたい。
AとBが選んだ総和の最大値と、それを満たす分け方を答えよ。

解法

Nの上限は24なので、全体では3^24通りの分け方が考えられる。
これはつらいので、半分全列挙しよう。

数列の前半と後半それぞれにて、AとBの得られる総和の差に対し、Aの得られる値の総和の最大値と、それを満たす分け方を求めよう。
これはそれぞれ高々3^12通りである。

あとは前後半において、AとBの得られる総和の差が正負反対のものを突き合わせて、Aの得られる値の総和の最大値の候補を総当たりしよう。

map<ll,pair<ll,ll>> A,B;
ll p3[25];
vector<int> V;
class ThreeWaySplit {
	public:
	void dfs1(int cur,ll mask,ll sa,ll sb) {
		if(cur==12) {
			ll d=sa-sb;
			if(A.count(d)==0||sa>A[d].first) {
				A[d]={sa,mask};
			}
			return;
		}
		dfs1(cur+1,mask+p3[cur]*0,sa+V[cur],sb);
		dfs1(cur+1,mask+p3[cur]*1,sa,sb+V[cur]);
		dfs1(cur+1,mask+p3[cur]*2,sa,sb);
		
	}
	void dfs2(int cur,ll mask,ll sa,ll sb) {
		if(cur==24) {
			ll d=sa-sb;
			if(B.count(d)==0||sa>B[d].first) {
				B[d]={sa,mask};
			}
			return;
		}
		dfs2(cur+1,mask+p3[cur]*0,sa+V[cur],sb);
		dfs2(cur+1,mask+p3[cur]*1,sa,sb+V[cur]);
		dfs2(cur+1,mask+p3[cur]*2,sa,sb);
		
		
	}
	
	string split(vector <int> L) {
		int O=L.size();
		while(L.size()<24) L.push_back(0);
		V=L;
		
		int i;
		p3[0]=1;
		FOR(i,24) p3[i+1]=p3[i]*3;
		
		A.clear();
		B.clear();
		dfs1(0,0,0,0);
		dfs2(12,0,0,0);
		ll ma=0;
		ll tm=p3[24]-1;
		FORR(a,A) {
			ll d=a.first;
			ll sa=a.second.first;
			ll mask=a.second.second;
			if(B.count(-d)) {
				sa+=B[-d].first;
				mask+=B[-d].second;
				if(sa>ma) {
					cout<<sa<<endl;
					ma=sa, tm=mask;
				}
			}
		}
		string S;
		FOR(i,24) S+='A'+tm/p3[i]%3;
		S.resize(O);
		return S;
		
		
	}

まとめ

こっちも割とすぐ思いついたのにしょうもないミスしてもったいない。