ARC080 E : Young Maids(800)
作成日：2017.08.10
最終更新日：2017.08.10
問題概要
$(1,2,...,N)$の順列$\{p_i\}$($N$は偶数)から順列$\{q_i\}$を
操作「$p$の隣り合う2つの要素を$p$から取り除き、この順のまま$q$の先頭に追加する」を$p$が空になるまで繰り返すことで作る。
辞書順最小となる順列$\{q_i\}$を求めよ。
制約
$2 \leq N \leq 2 \times 10^5$
$N$は偶数
数列$\{p_i\}$は$(1,2,...,N)$の順列
考え方
順列$\{q_i\}$を先頭から辞書順最小となるように貪欲に決めることができれば、それが答えである。
そこで、最後の操作から逆向きに考える。
最後の操作の時に$p$に残っていた2つの要素を先頭から順に$a,b$とする。
その前の操作で$p$から取り除かれた2つの要素は隣り合っていたことから、それらはともに$a$より前、$a$と$b$の間、$b$より後ろのいずれかの位置にあったことが分かる。
2つ以上前の操作においても同様のことがいえるので、元の順列$\{p_i\}$において$a$より前、$a$と$b$の間、$b$より後ろのいずれにおいても偶数個の要素が存在する。
すなわち、0-indexedであるとすると先頭から数えて$a$は偶数番目、$b$は奇数番目である。
貪欲に選ぶ時にそれ以上の制約はないから、$a$として偶数番目の要素のうち最小のものを選び、$b$として$a$より後ろにある奇数番目の要素のうち最小のものを選べば良い。
またこの時$q$の次の2つの要素はともに$a$より前、$a$と$b$の間、$b$より後ろのいずれかであり、これらの区間は空でなければ先の考察をそのまま用いることができる。
以上より$a,b$を前述の通りにとることと区切られた区間たちから貪欲法として適切な区間を選ぶことを十分高速にできればこの問題は解ける。
前者は1つ飛ばしの要素の区間minが取れれば良いから、$p$の要素を偶数番目と奇数番目に分けてSegment TreeやSparse Tableを用いれば求められる。
また後者は各区間における$a$でソートし、それが最も小さいものから選ぶのが最善であるから、priority_queueを用いれば求められる。
これらの計算量は$O(N \: log \: N)$よりは良いので、十分高速である。
ソースコード
マクロ等はこちら
Sparse_Table<T>
void build(int n , int *p)
sparse tableを要素数$n$の配列$p$で初期化・構築
T get(int s , int f)
区間$[s,f)$における最小値を取得
const int MC = 200010;
int N;
Sparse_Table<int> spt[2];
int p[2][MC]; //p[x][y]は2y+x番目の要素
int r[MC]; //r[i]番目の要素がi
int b[MC];
int t[MC];
priority_queue<P2 , vector<P2> , greater<P2> > Q;
void solve(int s0 , int t0){
if(s0==t0) return;
t[s0] = t0;
int a = spt[s0%2].get(s0/2,t0/2);
b[a] = spt[(s0+1)%2].get((r[a]+1)/2,(t0+1)/2);
Q.push(MP(a,s0));
}
int main(){
scanf("%d" , &N);
repp(i,0,N){
scanf("%d" , p[i%2] + i/2);
r[p[i%2][i/2]] = i;
}
spt[0].build(N/2,p[0]);
spt[1].build(N/2,p[1]);
solve(0,N);
while(!Q.empty()){
int a = Q.top().first;
int s = Q.top().second;
Q.pop();
solve(r[b[a]]+1,t[s]);
solve(r[a]+1,r[b[a]]);
solve(s,r[a]);
printf("%d %d%c" , a , b[a] , Q.empty()?'\n':' ');
}
return 0;
}解法まとめ
区切られた区間において偶数番目の要素の最小値$a$が最も小さい区間$[s,t[s])$を選び、その区間を$a,b[a]$で区切ることを繰り返す。(10-16,27-35行)
用いるsptはどちらであるかとsptで取得する区間の境界がどこであるかに注意する。