yukicoder : No.497 入れ子の箱

割とサクサク解けたのだが、参加が遅れたので順位が落ちました。
http://yukicoder.me/problems/no/497

問題

直方体の箱がN個あり、３辺の長さはX[i],Y[i],Z[i]である。
箱の向きを変えることができるとき、マトリョーシカ状に箱を入れ子にすると、最大何個まで入れ子にできるか。

解法

２つの箱を入れ子にするとき、片方の長い辺と片方の短い辺を合わせる意味はなく、それぞれ長い辺同士を合わせた方が入れ子にできる可能性がある。
よって、箱の向きをX[i]≦Y[i]≦Z[i]となるように回転させよう。

あとは(X[i],Y[i],Z[i])のtupleを昇順にソートしよう。
その場合、ソート順で手前の箱があとの箱を内包することはあり得ないので、箱iが箱j(j＜i)を包めるかを順次判定しつつ入れ子の最大数を求めればよい。

int N;
vector<vector<int>> V;

int num[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y>>j;
		vector<int> R = {x,y,j};
		sort(ALL(R));
		V.push_back(R);
		num[i]=1;
	}
	sort(ALL(V));
	
	int ma=1;
	FOR(i,N) {
		ma=max(ma,num[i]);
		for(j=i+1;j<N;j++) {
			if(V[i][0]<V[j][0] && V[i][1]<V[j][1] && V[i][2]<V[j][2]) {
				num[j]=max(num[j],num[i]+1);
			}
		}
	}
	cout<<ma<<endl;
}

まとめ

今回は★３とはいえ実装も難易度も軽め。