AtCoder ARC #142 : F - Paired Wizards

こういうの、どこから手を付けるべきかわからないなぁ…。
https://atcoder.jp/contests/arc142/tasks/arc142_f

問題

X,Y2人の魔法使いがいる。それぞれ、魔力の初期値は0である。
2人とも、以下の魔法を利用できる。

• 自身の魔力を1増やす
• 自身の魔力と同じだけ、モンスターにダメージを与える。

ここで、Nターン分の行動の候補が与えられる。
各ターンは2つの候補があり、2人がそれぞれどちらの魔法を使うかを示す。
各ターンで好きな候補を選べるとき、モンスターに与える総ダメージの最大値を求めよ。

解法

Xが2つ目の魔法を使う回数をCX回、そのターンを並べた数列xとすると、SX=sum(x)としたとき、与えるダメージの総量はSX-CX(CX+1)/2となる。
Yも同様CY,y,SYを定義すると、合わせて(SX+SY)-(CX(CX+1)+CY(CY+1))/2が最大となるターン数列x,yを作る問題となる。

各ターンの候補の組み合わせを以下のように分類する。

• 2人の魔法が異なり、かつ両候補で内容が異なる:(1,2),(2,1)
• 2人の魔法が同じで、かつ両候補で内容が異なる:(1,1),(2,2)
• Xの魔法は同じで、Yの内容が異なる:(1,1),(1,2)または(2,1),(2,2)
• Yの魔法は同じで、Xの内容が異なる:(1,1),(2,1)または(1,2),(2,2)
• 両候補の内容が同じ

上4つのバリエーションについて、どちらの候補を取るかはO(N)通りなので、全部総当たりすればO(N^4)で解ける。
実際、後ろ2つの最適解をO(N^2)で前処理しておくと、それを用いて前2つの総当たりO(N^2)をそれぞれO(1)で解け、結果的にO(N^2)で全体を処理できる。

int N;
int A[8080],B[8080],C[8080],D[8080];
vector<int> p2,p3,p4;

int bestA[8080];
int bestB[8080];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int num1=0,psum=0;
	int cx=0,cy=0;
	
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		
		if(A[i]!=C[i]&&B[i]!=D[i]) {
			if(A[i]!=B[i]) {
				num1++;
				psum+=i+1;
			}
			else {
				p2.push_back(i+1);
			}
			
		}
		else {
			if(A[i]==C[i]) {
				if(A[i]==2) psum+=i+1, cx++;
			}
			else {
				p3.push_back(i+1);
			}
			if(B[i]==D[i]) {
				if(B[i]==2) psum+=i+1, cy++;
			}
			else {
				p4.push_back(i+1);
			}
		}
	}
	
	reverse(ALL(p2));
	reverse(ALL(p3));
	reverse(ALL(p4));
	FOR(i,N+1) {
		bestA[i]=-i*(i+1)/2;
		int sum=0;
		FOR(j,p3.size()) {
			sum+=p3[j];
			bestA[i]=max(bestA[i],sum-(i+j+1)*(i+j+2)/2);
		}
		bestB[i]=-i*(i+1)/2;
		sum=0;
		FOR(j,p4.size()) {
			sum+=p4[j];
			bestB[i]=max(bestB[i],sum-(i+j+1)*(i+j+2)/2);
		}
	}
	int ret=0;
	FOR(i,num1+1) {
		int sum=0;
		FOR(j,p2.size()+1) {
			x=i+j+cx;
			y=num1-i+j+cy;
			ret=max(ret,psum+sum+bestA[x]+bestB[y]);
			if(j<p2.size()) sum+=2*p2[j];
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

こういううまく独立なDPに分解するテク、どうやったらなじむんだろうな。