kmjp's blog

競技プログラミング参加記です

Codeforces #291 Div2 D. R2D2 and Droid Army

問題文の解読が難しい。
http://codeforces.com/contest/514/problem/D

問題

N個のドローンがある。
各ドローンにはM種類の構成部品があり、i番のドローンにはj番目の部品がA[i][j]個使われている。

ここでM種類の武器がある。
j番の武器を1回放つと、各ドローンのj番目の部品が1個ずつ破壊される。
全構成部品を破壊したドローンは破壊される。

武器を全部でK回使い、出来るだけ連続したドローンを破壊したい。
連続したドローン破壊数が最大となる、各武器の発射回数を求めよ。

解法

L~R番のドローンを破壊するには、 \displaystyle \sum_{1 \le j \le M} \left( \max_{L \le i \le R} A_{ij}  \right) \le Kであればよい。

後は各Lについて上記条件を満たす最大のRを求めればよい。
この手段はいくつかあって、

  • 尺取法でRを検索していく
  • A[i][j]のSegTreeを作ると \left( \max_{L \le i \le R} A_{ij}  \right)が簡単に求められるので二分探索でRを求める
  • 平方分割で一定区間の \left( \max_{L \le i \le R} A_{ij}  \right)を求めていくことで、RをO(√N)で求める。

自分は最後の平方分割解だったけど、SegTree解が一番スマートかな?
速度は尺取法が一番速そうだね。

int N,M,K;
int D=400;
ll A[101000][7];
ll MM[400][7];

int co=0;
int res[7];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) FOR(j,M) cin>>A[i][j], MM[i/D][j]=max(MM[i/D][j],A[i][j]);
	
	FOR(i,N) {
		ll ma[6]={};
		if(N-i<=co) continue;
		for(x=i;x<N;) {
			ll tma[6];
			ll tot=0;
			if(x%D==0 && x+D<N) {
				FOR(j,M) tot+=tma[j]=max(MM[x/D][j],ma[j]);
				if(tot<=K) {
					x+=D;
					FOR(j,M) ma[j]=tma[j];
					continue;
				}
			}
			tot=0;
			FOR(j,M) tot+=tma[j]=max(A[x][j],ma[j]);
			if(tot>K) break;
			FOR(j,M) ma[j]=tma[j];
			x++;
		}
		if(x-i>co) {
			co=x-i;
			FOR(j,M) res[j]=ma[j];
		}
		
	}
	
	FOR(j,M) _P("%d ",res[j]);
	_P("\n");
}

まとめ

まさかの平方分割2連発。