Rockethon 2015 : B2. Permutations

意外にBから難易度高いぞ…？
http://codeforces.com/contest/513/problem/B2

問題

1～Nのpermutationである数列Pを考える。
F(P)とは、N*(N-1)/2通りの全パターンの連続部分列における最小値の和である。

NとKが与えられる。
N要素のPermutation Pのうち、F(P)が同着最大値となるもので、辞書順K番目のものを答えよ。

解法

数列中真ん中に近い数値は多くの部分列に含まれる。
よって全体を最大値にするためには、小さい数値をできるだけ外側に配置する必要がある。

その際、たとえばP中(x+1)～Pの並び順が決まっているとき、xは最初か最後に配置することになる。
xを先頭に配置した場合、(x+1)～NはNを除いた*1要素は前に置くか後ろに置くかで2^*2分辞書順の順番がずれる。

そこで、以下のようにする。
まずKはデクリメントして0-indexとして扱う。

Dequeで数列を管理し、初期状態でNだけを放り込む。
以後(N-1)から1を降順で定める。
xの位置を決めるときは、(K & (2^(N-1-x)))が正なら前、0なら後ろに追加していけばよい。

ll N,M;
deque<int> Q;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	M--;
	Q.push_back(N);
	for(i=N-2;i>=0;i--) {
		if(M&(1LL<<(N-2-i))) Q.push_back(i+1);
		else Q.push_front(i+1);
	}
	FOR(i,N) _P("%d ",Q[i]);
	_P("\n");
}

まとめ

コードは単純だけど、考察に時間のかかる問題。
自分は最初中央に最大値を置いて徐々に外側に広がると思ったので、正答にたどり着くまで時間がかかってしまった。

*1:N-1)-(x+1

*2:N-1)-(x+1