競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 103 - Stacking Boxes

UVa第3回です。
今回は英語がパッと見理解不能だったので翻訳に英文丸ごと突っ込んだのですが
余計わけわからなくなったので結局自力で読みました。

- 問題概要

n個の数字が入った箱b_iがk個存在します。
二つの箱b_i(c_1,,,c_n),b_j(d_1,,,d_n)(c,dは整数)について、
b_i(c_1,,,c_n)を並び替えてできたb'_i(c'_1,,,c'_n)c'_1 < d_1,c'_2 < d_2,,,c'_n < d_nを満たすとき、b_ib_jの入れ子(nest)になる状態と定義します。
入れ子関係を< を使って表した時、b_x < b_y < b_zとなるx,y,zを入れ子列(nesting string)と定義します。
一番長い入れ子列の長さとその構成する箱番号を出力してくださいという問題です。

- 解法

二つの箱C,Dの入れ子関係について、C,D内をそれぞれソートした箱をC'(c_1,,,c_n),D'(d_1,,,d_n)
任意のiについてc_i < d_iが成り立つときCはDの入れ子となり、そうでないときはCはDの入れ子となりません。
したがって、C < Dの判別はあらかじめ各箱内の数字をソートしておけばO(n)で判別可能です。
また、全ての箱を各箱の最も小さい値を基準(値が等しいときは2番目の値)として降順にソートしておきます。この動作は比較にO(n)なのでO(kn\log k)
すると上記の方法でソートされた箱の群(b'_1,,,b'_n)について、
ソートされているためb_i > b_j(i < j)は必ず成り立たないことがわかります。
これで動的計画法が使えるようになります。
dp(i)を、b_iを最も内側の入れ子とする入れ子列の長さとすると、
dp(0)=0,dp(m)=max_{0\le i\lt m}(b_m < b_iが成り立つdp(i))という漸化式が成り立ちます。
これを求めるのに必要な繰り返し回数はO(n^2),入れ子かどうかの比較にO(n)なのでO(n^3)となります。
事前のソートの計算量がO(kn (\log n +\log k))ですので十分間に合います。

- ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define N 30
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define it(b) (b).begin(),(b).end()
struct box{
	int id;
	vector<int> num;
	bool operator<(const box& another)const{
		rep(i, 0u, num.size()){
			if (num[i] != another.num[i])
				return(num[i] > another.num[i]);
		}
		return(id > another.id);
	}
};

vector<box> boxes;

bool nest(int s, int l){
	bool flag = true;
	rep(i, 0u, boxes[s].num.size())
		if (boxes[s].num[i] >= boxes[l].num[i])
			flag = false;
	return(flag);
}

int dp[30];
int par[30];
int main(void){
	boxes.reserve(30);
	int n, k,tmp,p;
	while (cin >> k >> n){
		boxes.resize(k);
		rep(i, 0, k){
			boxes[i].num.clear();
			boxes[i].num.reserve(n);
			boxes[i].id = i + 1;
			rep(j, 0, n){
				cin >> tmp;
				boxes[i].num.push_back(tmp);
			}
			sort(it(boxes[i].num));
		}
		sort(it(boxes));
		rep(i, 0, k)par[i] = i,dp[i]=1;
		rep(i,1,k)
			rep(j, 0, i){
			if (nest(i, j))
				if (dp[i] < dp[j] + 1)dp[i] = dp[j] + 1, par[i] = j;
		}
		tmp = 0,p=0;
		rep(i, 0, k)if(tmp<dp[i])tmp=dp[i],p=i;
		cout << tmp << endl;
		while (true){
			cout << boxes[p].id;
			if (p == par[p])break;
			cout << " ";
			p = par[p];
		}
		cout << endl;
	}
}