Codeforces #215 Div1. C. Sereja and the Arrangement of Numbers

こちらも凡ミスで2WA…。
HackしてくれたおかげでResubmitできて助かった。
http://codeforces.com/contest/367/problem/C

問題

数列Aが美しいとは、以下のことを言う。

• A中に含まれる全ての２つの異なる数の対(x,y)について、xとyが隣接しているA[j]=x,A[j+1]=yまたはA[j]=y,A[j+1]=xのどちらかを満たしている。

ここで、N要素の美しい数列を作りたい。
この時、コストW[i]を払うと数Q[i]が数列中に好きなだけ使う権利を得られる。
N,Q,Wが与えられたとき、数列を作るのにかかる最大コストはいくらか。

解法

この問題、数Q[i]は全く関係ない。
N要素の美しい数列に含めることができる数がP通りの場合、コストW[i]のうち高い順にP個選んで加算すればよい。
よって、やることはNに対応するPを求めることである。

逆に、P個の異なる数を含む数列が美しくなるには、何要素が必要かを考える。
美しさの条件をよく考えると、これはP要素の完全グラフにおいて、各辺を１回以上たどる最短パスの長さ+1であることがわかる。
よって：

• Pが奇数なら、各点から出る辺の数は偶数なので各辺は重複なくたどれるためP*(P-1)/2+1要素
• Pが偶数なら、各点から出る辺の数は奇数なので辺が4以上なら各辺を重複なくたどりきることはできない。各点から出る辺を１本ずつ残すように移動して元の位置に戻るするのがP*(P-2)/2+1要素で、あと各点に１辺ずつ残っているのでそれを順にP-1要素かけてたどると計P*P/2要素

あとはPを増やしながらNを超えないか調べるだけ。

ll N,M;
ll W[200010];

void solve() {
	int f,i,j,k,l,x,y;
	ll r=0;
	cin>>N>>M;
	FOR(i,M) cin>>x>>W[i];
	sort(W,W+M);
	r=0;
	for(i=1;i<=M;i++) {
		if(i%2==0 && i*(i-2)/2+i>N) break;
		if(i%2==1 && i*(i-1)/2+1>N) break;
		r+=W[M-i];
	}
	cout << r << endl;
}

まとめ

偶数点の完全グラフの辺をたどりきるステップ数って既知なのかな？
自分はこの問題で初めて知った。