Codeforces Round #651 (Div. 2), problem: (D) Odd-Even Subsequence

解説ACしたメモです。

問題ページ：https://codeforces.com/contest/1370/problem/D

問題概要

長さNの数列Aが与えられる。長さKの部分列に対して、部分列の"cost"を次のように定義する。

・cost := 部分列の奇数番目の要素全体の最大値と、偶数番目の要素全体の最大値のうち小さい方の値

このcostを最小化せよ。2 <= K <= N <= 2e5

解法

答えを二分探索します。bool func(int x) を、「長さKの部分列であって、costをx以下に抑えられるか」の関数とします。costがx以下となるためには部分列の偶数項すべてまたは奇数項すべてのいずれかがx以下であれば良いことがわかります。

偶数項全てをx以下とするような部分列が構成可能であるかは、数列Aを順番に見ていきながら、部分列を貪欲に構成することで検証できます。現在、部分列の長さが奇数であるならば、次に部分列に追加する要素は、偶数項目になるので、その要素はx以下でなければなりません。逆に、現在の部分列の長さが偶数ならば、奇数項の数はなんでも良いので、そのまま今見ているAの値を追加すれば良いです。

こうしてできた部分列の長さがK以上であればtrueです。偶奇を反対にして同様のことをします。どっちにしても構成できないようであればfalseです。

#define REP(i,n) for(int i = 0;i < n;i++)
bool func(int mid,vector<int>& a,int k){
    
    int cnt = 0;
    REP(t,2){
        cnt = 0;
        REP(j,a.size()){
            if(cnt % 2 == t){
                cnt++;
            }else{
                if(a[j] <= mid) cnt++;
            }   
        }
        if(cnt >= k) return true;
    }
    return false;
}
void solve(){
    int n,k;cin >> n >> k;
 
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    
    int l = 0,r = 1e9 + 1;
    
    while(l + 1 != r){
        int mid = (l + r) / 2;
        
        if(func(mid,a,k)) r = mid;
        else l = mid;
        
    }
    cout << r << '\n';
}

言われてみるとこれが解けないのは不味いような気がしてきますが、二分探索と貪欲の組み合わせで解けるところに至りませんでした。反省です