概要

順列 \({p_1,p_2,...p_{2N-1} } \)が与えられる
\(i\)段目の数列を\({q_n}\)として, \(i+1\)段目の数列の\(j\)項目は \( q_j, q{j+1}, q{j+2} \)の中央値である。(長さは2減る)
長さが1になったとき, その数は何?

考察

\(O(N²)\)解法の高速化は絶望的

そういえば、中央値と二分探索は相性が良かったような... (↓一例)

atcoder.jp

それゆえ「最上段が\(k\)以上となるか?」という二分探索をしたくなる。こうすると、先ほど挙げた問題のように順列の値がk以上ならば1, そうでなければ0と置き換えてよいことがわかる。

判定パートだが, 最初の0/1のみからなる順列をランレングス圧縮する。(おそらくこれも典型) 1回の操作で何が変わるか観察すると、次の性質が見つかる。

長さが2以上の部分は操作後も色は保たれる
長さが1の部分は操作後に色が反転する
上2つの変換を行った後、左右の区間の長さが1つずつ削られる

例えば、順列が\({1,1,0,1,0,1,1}\)だとするとその次は\({1,1,0,1,1}\)となるが、これをランレングスで見ると\({2,1,1,1,2}\)→\({3,1,3}\)→\({2,1,2}\)となる。

1番目の性質はそれはそう(なぜなら、ある項の直下とそのすぐ隣に同じ数字があるから)

2番目の性質は少し実験するとわかり、[1×たくさん][0][1]という配列では[0]が[1]に変換され、0と1を逆にしても同様である。

このとき、反転操作によって長さ1が連続する区間に関してその両端がその左右と同じ数字になり、吸収されるため長さ1が連続する区間の長さは1回の操作で2減少する。

最終的に長さ1が連続する区間がどう変化するかを考えると、次のようになる。

長さが奇数の時、すべて同じ
長さが偶数の時、半分ずつに分かれる

ただし、これは操作3を無視したものとする。

この操作を行った数列の\(N\)項目が求める答えである。そのような操作はstackを用いて\(O(N)\)で行うことができ、二分探索パートと合わせて\(O(NlogN)\)で解けた。

実装例

atcoder.jp

PAKENで実装したのでインデントがががが

#include"bits/stdc++.h"
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int> P;
int A[200006];
int a[200006];
signed main(){
    int N;cin>>N;
    int n=N*2-1;
    rep(i,n)cin>>A[i];
    
    int lb=1,ub=n;
    while(ub-lb>1){
        int mi=(ub+lb)/2;
        rep(i,n){
            if(A[i]>=mi)a[i]=1;
            else a[i]=0;
        }
        
            vector<P>V;
            int now=a[0],cnt=0;
            rep(i,n){
                if(now==a[i])cnt++;
                else{
                    V.push_back(P(now,cnt));
                    now=a[i];cnt=1;
                    }
                }
            V.push_back(P(now,cnt));
            
            stack<P>S;cnt=0;
            S.push(P(1^a[0],0));
            rep(i,V.size()){
                if(V[i].second==1)cnt++;
                else{
                    if(cnt&1){
                        P p=S.top();S.pop();
                        p.second+=cnt+V[i].second;
                        S.push(p);
                        cnt=0;
                        }
                    else{
                        P p=S.top();S.pop();
                        p.second+=cnt/2;
                        S.push(p);
                        P p2=V[i];
                        p2.second+=cnt/2;
                        S.push(p2);
                        cnt=0;
                        }   
                    }
                }
                
            if(cnt&1)S.push(P(a[n-1],cnt));
            else{
                S.push(P(a[n-1],cnt/2));
                S.push(P(1^a[n-1],cnt/2));
                }   
            int sum=0;
            int col=0;
            while(sum<N){
                P p3=S.top();S.pop();
                col=p3.first;
                sum+=p3.second;
                }   
            
            if(col)lb=mi;
            else ub=mi;   
        }
        cout<<lb<<endl;
    }

所感

こういう発想典型なのかな

ZenReKkyo Industry

🏭

AGC006-D Median Pyramid Hard (1300) 解説

概要

考察

実装例

所感