kmjp's blog

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

HackerRank 101 Hack 50 : E. Boxes for Toys

2時間ちょっとはみ出て解けた。
https://www.hackerrank.com/contests/101hack50/challenges/boxes-for-toys

問題

N個の直方体形状の箱が1列に並んでおり、それぞれの3辺の長さが与えられる。

このうち、連続した箱の部分列[L,R]を選ぶとする。
ここで、別の運送用の直方体の箱をもちいてこれらを梱包することを考える。

各運送用の箱は同じ大きさで、運送用箱1つに対し選んだ箱を1つずつ入れていく。
当然ながら、入れる箱の3辺はそれぞれ運送用の箱の辺より短くなければならない。
ただし、各箱は自由に向きを回転してよい。

運送用の箱としては、条件を満たす大きさのうち体積が最小のものを選ぶとする。
部分列[L,R]としてあり得るすべての組み合わせにおいて、運送用の箱の体積の総和を求めよ。

解法

[L,R]が決まっているときの運送用の箱のサイズを考える。
まず、各箱iは長さが短い順にソートし、X[i]≦Y[i]≦Z[i]とする。
すると運送用の箱の3辺はぞれぞれmax(X[L..R])、max(Y[L..R])、max(Z[L..R])となる。

この事実をもとに考えていこう。
今、箱Rが部分列の右端であるようなケースを考える。

範囲に対し整数を掛けること、および範囲の総和を取れるSegTreeを考えよう。
SegTreeのi要素目にはmax(X[i..R])×max(Y[i..R])×max(Z[i..R])が入るようにできれば、このSegTreeの[0,R]の範囲の総和を取れば、箱Rが部分列の右端であるケースの体積の総和を取れる。

ここでRをR+1にすることを考える。
Lを左端とする部分列に対応する辺の大きさはmax(X[L..R])→max(X[L..(R+1)])となる。残り2辺も同様。
ここでmax(X[L..R])≧X[R+1]であれば体積は変化しないが、max(X[L..R])<X[R+1]の場合、運送用の箱の辺はX[R+1]となる。
よってそのようなLに対しては、体積がX[R+1]/max(X[L..R])倍になる。

あとは、スライド最小値の応用でmax(X[L..R])が変化するようなL周辺の区間にX[R+1]/max(X[L..R])倍することを3辺それぞれに行っていけば、何次元でも解くことができる。

int N;
ll mo=1000000007;
int A[303030][3];

template<class V,int NV> class SegTree {
public:
	vector<V> mult,sum;
	SegTree(){mult.resize(NV*2,1); sum.resize(NV*2,0);}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			(mult[k]*=v)%=mo;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			sum[k]=(mult[2*k]*sum[2*k]+mult[2*k+1]*sum[2*k+1])%mo;
		}
	}
	void add(int x,int v) {
		x+=NV;
		while(x>0) {
			sum[x]+=v;
			x/=2;
		}
	}
	
};
ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

SegTree<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i][0]>>A[i][1]>>A[i][2];
		sort(A[i],A[i]+3);
	}
	
	vector<pair<int,int>> V[3];
	V[0].push_back({1<<30,-1});
	V[1].push_back({1<<30,-1});
	V[2].push_back({1<<30,-1});
	
	ll P=0;
	FOR(i,N) {
		st.add(i,1);
		FOR(j,3) {
			st.update(i,i+1,A[i][j]);
			while(V[j].size()>=2 && V[j].back().first<=A[i][j]) {
				ll mul=A[i][j]*modpow(V[j].back().first)%mo;
				x=V[j].back().second;
				V[j].pop_back();
				y=V[j].back().second;
				st.update(y+1,x+1,mul);
			}
			V[j].push_back({A[i][j],i});
		}
		(P+=st.mult[1]*st.sum[1])%=mo;
	}
	
	cout<<P*modpow(1LL*N*(N+1)/2%mo)%mo<<endl;
	
}

まとめ

ちょうど直前のCF#419のDiv1Dで直方体について考える問題が出てたので、すんなり思いつけた。