AtCoder ARC #067 : F - Yakiniku Restaurants

こちらもバグを時間内に見つけられずじまい。方針はあってたのに。
http://arc067.contest.atcoder.jp/tasks/arc067_d

問題

N個の焼肉屋が一直線上に並んでおり、その座標A[i]が与えられる。
ここでM個のチケットがある。i番目の焼肉屋でj番目のチケットを使うと、おいしさB[i][j]の肉を食べられる。
各チケットは１回ずつしか使えないが、１つの焼肉屋で複数チケットを使ってもよい。

任意の焼肉屋をスタートし、任意の焼肉屋で終了するとき、最適にチケットを使う場合、食べた肉のおいしさの総和-移動距離の最大値を求めよ。

解法

L～R番の焼肉屋で焼肉を食べる場合、(食べた肉のおいしさの総和-移動距離)の最大値f(L,R)はである。
Lを総当たりし、Lに対してRを増やしながらf(L,R)を求めその最大値を求めることを考える。
f(L,R-1)からf(L,R)を愚直に求めるとO(M)かかるので、全体ではO(N^2*M)かかる。

なんとこの問題はそれでもコンパイラの最適化の力で通ってしまうらしいが…。
一応ここではもう少しスマートに解くことを考える。

各チケットjに対し、Rが1増えたときにがどう変化するかを考えてみる。
Rがあるkに到達したときB[k][j]＞max(B[L...(k-1)][j])であれば、そのRに対し始めてが増加する。
B[k][i]の手前でB[j][i]の最大となるjをlとすると、新たに(Rをインクリメント後)R番目の焼肉屋まで食べる範囲に含める場合、肉のおいしさの総和はB[k][i]-B[l][i]だけ増加する。
この情報を事前に各iについて計算しておけば、Rが増えたときO(M)掛けることなく肉のおいしさの増分を求めることができる。
あとはimos法の容量でf(L,R)を求めていけばよい。

また、仮にL=lだった場合、Lをインクリメントする場合を考える。
今までl～(k-1)番の焼肉屋ではチケットjに関しl番の店で食べるのがベストだった。
しかしL=lの状態でLをインクリメントすると、l番の店で食べることができない。その場合、(l+1)～(k-1)の店に関し、B[*][j]が増加するタイミングを求めて増分管理すればよい。
各B[i][j]に関し、B[x][j] (xはB[x][j]＞B[i][j]となるi以上で最小の値)を最初に求めておけば、この処理は高々O(NM)回しか生じない。

int N,M;
ll A[5050];
int B[5050][202];
ll ret;

int more[5050][202];
ll add[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N-1) {
		scanf("%d",&x);
		A[i+1]=A[i]+x;
	}
	
	FOR(y,N) FOR(x,M) scanf("%d",&B[y][x]);
	FOR(x,M) {
		stack<pair<int,int>> S;
		B[N][x]=1<<30;
		S.push({1<<30,N});
		more[N][x]=N;
		for(y=N-1;y>=0;y--) {
			while(S.top().first<B[y][x]) S.pop();
			more[y][x]=S.top().second;
			S.push({B[y][x],y});
		}
		
		y=0;
		while(y<N) {
			add[more[y][x]]+=B[more[y][x]][x]-B[y][x];
			y=more[y][x];
		}
	}
	
	FOR(y,N) {
		ll cur=0;
		FOR(x,M) cur+=B[y][x];
		ret=max(ret,cur);
		for(int z=y+1;z<N;z++) {
			cur+=add[z];
			ret=max(ret,cur-(A[z]-A[y]));
		}
		
		FOR(x,M) {
			j=more[y][x];
			add[j]-=B[j][x]-B[y][x];
			i=y+1;
			while(i<j) {
				add[more[i][x]]+=B[more[i][x]][x]-B[i][x];
				i=more[i][x];
			}
		}
		
	}
	
	cout<<ret<<endl;
	
}

まとめ

この説明は図で書くと簡単だけど文章で説明するのつらい。