Codeforces #542 Div1 B. Wrong Answer

面倒なConstructionゲー。
https://codeforces.com/contest/1129/problem/B

問題

数列の評価値を(要素数)*(要素の総和)とし、数列のスコアとは部分列のうち最大の評価値と定義する。
N要素の整数列Aに対し、スコアを計算する誤ったアルゴリズムを考案した。
それは先頭から累積和を取っていき、累積和が負になった時点で累積和をリセットしつつ、対象範囲の(要素数)*(累積和)の最大値をスコアとするものである。

ここで整数Kが与えられる。
真のスコアと誤ったアルゴリズムでのスコアの差がKとなる数列を構築せよ。

解法

先頭から見ると累積和が一時的に負となるが、その後正に盛り返すケースを考えよう。
誤ったアルゴリズムの方は累積和が負になった時点で一旦リセットされるので累積和は誤ったアルゴリズムの方が小さくなるが、真のスコアの計算式の方が要素数が大きくなるので結果真のスコアの方が大きくなるケースを考える。

以下のコードでは、リセットがかかる位置とその後の長さを総当たりしながら、差がKになるようなケースを微調整している。

ll K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	
	for(int a=2;a<=2000;a+=2) {
		for(int mi=-a/2;mi>=-a/2-10;mi--) {
			for(int b=1;a+b<=2000;b++) {
				ll hoge=K+(-mi)*(a+b);
				if(hoge%a) continue;
				hoge/=a;
				if(hoge<b || hoge>=b*1000000) continue;
				
				cout<<a+b<<endl;
				FOR(i,(a/2)-1) {
					cout<<0<<" "<<-1<<" ";
				}
				cout<<0<<" "<<(mi+(a/2-1))<<" ";
				FOR(i,b) {
					x=min(hoge,1000000LL);
					cout<<x<<" ";
					hoge-=x;
				}
				cout<<endl;
				return;
			}
		}
	}
}

まとめ

えらく苦労した。