Codeforces #310 Div1 A. Case of Matryoshkas

Cで散々手間取って散々な出来。
http://codeforces.com/contest/555/problem/A

問題

1～Nの大きさのマトリョーシカが１個ずつある。
各マトリョーシカは、自分より小さなマトリョーシカを１つ中に入れることはできる。
(ネストして複数入れることは可能だが、直接２つ以上入れることはできない)
初期状態でM個のマトリョーシカが見えており、それぞれどのマトリョーシカを中に含むかが与えられている。

１回の処理で以下のいずれかを行うことができる。

• あるマトリョーシカ(中に他のものを含んでいても良い)をより大きな(他に含まれていない)マトリョーシカの中に入れる。
• 逆に、他のマトリョーシカに含まれていないマトリョーシカについて、中身を取り出す。

1～Nを全部ネストさせて１個マトリョーシカにするには、最低何回処理をしなければならないか。

解法

1～Nを順にネストさせるには、小さい順にマトリョーシカを包んでいかなければならない。
逆にマトリョーシカの中身を取り出すのは大きな順でなければならない。

よって、一旦全部バラバラにして、順次組み立てればよい。
例外として、最初から1,2,3...と連番で包まれている部分はバラさなくてよい。

int N,K;
int M[101010];
vector<int> A[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>K;
	
	int ret=0,sp=K;
	FOR(i,K) {
		cin>>M[i];
		FOR(j,M[i]) cin>>x, A[i].push_back(x);
		if(A[i][0]==1) {
			FOR(j,M[i]-1) if(A[i][j]+1!=A[i][j+1]) {
				ret += M[i]-1-j;
				sp += M[i]-1-j;
				break;
			}
		}
		else {
			ret += M[i]-1;
			sp += M[i]-1;
		}
	}
	
	cout<<ret+(sp-1)<<endl;
}

まとめ

問題の理解に手間取ってWAしたのがもったいない。