Google KickStart 2020H-C "Rugby"

これもやさし目なABC-Fって感じ　でも面白かった

codingcompetitions.withgoogle.com

問題概要

二次元グリッド上にN人の人がいる。N人をある格子点からX軸に平行に一列に並べたい。人が格子点から格子点に移動するためにかかるコストは2点のマンハッタン距離と等しい。終状態の列の位置と、人の並び順は任意とするとき、必要なコストの最小値は？ (N<=1e5 , 座標は絶対値1e9以下）

解法

「終状態の左端の人の座標」を考えましょう。X軸方向とY軸方向に分離して考えると、まず、Y座標は簡単に求められます。すなわち全員の座標をY軸昇順にソートして、その中央値にすればいいという有名なやつですね。

次に、X座標ですが、これはF(x) := 終状態の左端の人の座標がxの時、X軸平行成分のコストの総和 とした時、凸性がわかるので、3分探索をすれば求めることができます。実装は次の通りです。

editorialを見たらなんかO(NlogN)みたいなことが書いてあったので多分上と同じ方針だと思うんですがあまりに長いので読む気になっていません。"ternaly"みたいなワードがなかったので少し違うかも

追記 上手い解法を見つけた。Xの方をソートして、その後に添字分ずつ左にずらした時、終状態のX座標はずらした後のX座標の中央値にできる。なるほど...

youtu.be

// solution for KickStart 2020H-C
// author : lynmisakura
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 100010;

int N;
ll X[MAXN],Y[MAXN];

ll F(ll mid){
  ll res = 0;
  for (int i = 0; i < N; i++) {
    res += abs((mid + i) - X[i]);
  }
  return res;
}

ll get_x(){

  ll L = ll(-1e10);
  ll R = ll(1e10);
  
  while(R - L > 2){
    
    ll RR = (L + R * 2) / 3;
    ll LL = (L * 2 + R) / 3;
    
    if(F(LL) < F(RR)){
      R = RR;
    }else{
      L = LL;
    }

  }
  
  return F((R + L) / 2);

} 

ll get_y(){

  ll mid;

  if (N % 2 == 0) {
    mid = (Y[(N/2)] + Y[(N/2)-1]) / 2;
  } else {
    mid = Y[(N / 2)];
  }

  ll res = 0;
  for (int i = 0; i < N; i++) {
    res += abs(Y[i] - mid);
  }

  return res;
}

void main2(){

  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }

  sort(X,X+N);
  sort(Y,Y+N);

  cout << get_x() + get_y() << '\n';

}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(20);

  int tt;cin >> tt;
  for(int i=1;i<=tt;i++){
    cout << "Case #" << i << ": ";
    main2();
  }
}

Google KickStart 2020H-B "Boring Numbers"

ABC-Eぐらいでありそう

問題リンク：

codingcompetitions.withgoogle.com

問題概要

ある正整数Xが"boring"である、とは次のように定義される：「Xを文字列として見た時、左から数えてi(1-index)桁目の偶奇がiの偶奇と一致する」。L以上R以下の"boring"な数は何通りあるか？(1 <= L < R <= 1e18)

解法

func(X) := 「X以下の"boring"な数の個数」とします。桁DPをすれば良いですが、len := (Xの桁数）として1以上len未満桁の数については、必ずX以下になるので、これらの桁数については、あり得る"boring"な数全部を試せばよく、それは明らかに(5^{桁数})の1からlen-1までの和になります。以下、len桁の数のみ考えます。

dp[dig][num][less] := dig桁目をnumにするとき、この値がX未満になることが確定するか？ として、Xの大きい桁から順に決めていけば解くことができます。この手のDP遷移は典型ですね。

次のように実装することができます。

// solution for KickStart2020H-B
// author : lynmisakura
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int len;
string s;
ll dp[20][20][2];
ll func2(int len){
  ll res = 1;
  for (int i = 0; i < len; i++) {
    res *= 5;
  }
  return res;
}
ll func(ll X){

  memset(dp,0,sizeof(dp));

  s = to_string(X);
  len = int(s.size());

  dp[0][0][0] = 1;
  for (int i = 0; i < len; i++) {
    int x = (s[i] - '0');
    for (int from_dig = 0; from_dig < 10; from_dig++) {
      for (int to_dig = 0; to_dig < 10; to_dig++) {
        if((i + 1 - to_dig) % 2 == 0){
          for (int less = 0; less < 2; less++) {
            if(!less){
              if (to_dig < x) {
                dp[i+1][to_dig][1] += dp[i][from_dig][0];
              } else if(to_dig == x){
                dp[i+1][to_dig][0] += dp[i][from_dig][0];
              }else{
                continue;
              }
            }else{
              dp[i+1][to_dig][1] += dp[i][from_dig][1];
            }
          }
        }
      }
    }
  }

  ll res = 0;
  for (int i = 1; i < len; i++) {
    res += func2(i);
  }
  for (int dig = 0; dig < 10; dig++) {
    for (int less = 0; less < 2; less++) {
      res += dp[len][dig][less];
    }
  }

  return res;

}

/*=====================================================*/

void main2(){
  ll L,R;
  cin >> L >> R;
  cout << func(R) - func(L-1) << '\n';
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(20);

  int tt;cin >> tt;
  for(int i=1;i<=tt;i++){
    cout << "Case #" << i << ": ";
    main2();
  }
}

AtCoder Grand Contest 047-B First Second (Trie木解法）

B - First Second

Trie木を使った実装を説明します。

実装については

algo-logic.info

を参考にしています。Trie木全体の実装などはこちらを読むと良いと思います。ここでは、この問題を解くために必要な部分だけを記述します。

問題概要

文字列がN個与えられる。文字列に対して次の「操作」を繰り返し行うことで新たに文字列を生成することができる。二つの文字列のペアであって片方からもう片方を「操作」によって作ることができるものは何通りあるか？

「操作」：文字列の先頭2文字のうち一方を削除する。

N <= 1e5 , Σ|S| <= 1e6

解法

1. 何をすれば良いか

①　長さMの文字列Sについて、生成できる文字列は、ある i (0 <= i <= M )について、[0 ; i ) の範囲から取ってきた1文字と、Sの接尾辞[i ; M )を連結させたものです。文字列Sをreverseしておきましょう。すると、Sの接頭辞およびそれ以降のうちから0文字または1文字を取ってきてつなげたものが生成されると言い換えることができます。

②　明らかに、自分より短い文字列から自分を生成することはできません。

まずは文字列たちを長さでソートしましょう。ソートの比較関数はグローバルに書くか、ソートの第3引数にラムダ記法を用いて

sort(a.begin(),a.end(),[](string& s,string& t){
  return s.size() < t.size();
});

と書くことで実行できます。

文字列Sから文字列Tが生成できるかを考えます。 文字列Sから生成されうる文字列を効率的に全部列挙するにはどうすれば良いでしょうか？上で述べたように、操作によって生成される文字列はSの接頭辞 + alpha のような形をしています。接頭辞を、0文字、1文字、...と順番に生成して、接頭辞以降の文字列から取ってくることができる全ての文字を取ってくることで全部の生成文字列を列挙できます。

「接頭辞以降の文字列から取ってくることができる文字」はどうすればわかるでしょうか？アルファベットは26文字しかないので、26文字の小英文字全てについて、その文字を取ってくることができるかを試して良いです。つまり、ある文字cが、i文字目以降に出現するかどうかがわかれば良いです。これは、O(|S|)で前計算すれば簡単に求められます。(ABC-Cぐらいの水準？）ここでlogをつけると危ないんでしょうか...?

2.アルゴリズム

アルゴリズムは次の通りです。vector<string> A(N)に、文字列が長さの短い順に格納されています。

・string A[i]から生成される文字列を上に述べた方法で列挙する。ある生成文字列UがA[i-1],A[i-2],...,A[0]に存在するかをTrie木で判定。存在するなら答えに1加算。

・Trie木にA[i]を追加する。

上記をi = 0,1,...,N-1の順で繰り返す。

3.Trie木による文字列の存在判定

Trie木自体はいろいろと複雑な機能を搭載できますが、この問題を解くために必要な部分だけを記述します。まず、Trie木上の文字に対応するノードを次のように定義します。

struct Node{
    int c; //文字に対応した数字（'a'を引いた値）
    bool accept;  // ここで終わる文字列が存在（今回それは高々1つ）
    vector<int> nextid; // 自分から辺が張られる頂点番号(26文字に対応)
    Node(int c):c(c),accept(false){
      nextid.assign(26,-1);// -1 : 文字('a' + i)に対応する文字に辺がはられていない
    }
};

vector<Node> g; // グラフ

先に、文字列の挿入フェーズを記述しましょう。

void insert(string& s){
  int tmp = 0; // 現在の頂点番号
  for(int i = 0;i < s.size();i++){
    int& nid = g[tmp].nextid[s[i] - 'a']; //次に飛ぶべき頂点番号
    if(nid == -1){ // -1 : まだその頂点がグラフ上に存在しない
      nid = g.size(); // 新しく生成した頂点は、g[g.size()]になる
      g.emplace_back(s[i] - 'a');
    }
    tmp = nid; // 次の頂点に飛ぶ
  }
  g[tmp].accept = true; // 文字列の最後の文字はaccept（いわゆる受理状態）
}

文字列Sから生成される文字列たちが、Trie木上に存在するかを探索するパートをfunc(string s)として、次に記述します。

bool match(int tmp,int c){
    int nid = g[tmp].nextid[c]; // tmpから飛ぶ文字('a'+ c )に対応するノード番号
    return (nid != -1) && g[nid].accept; // nidで終わる文字列が存在するか
}
void func(string s){
    int sz = s.size();
    vector<int> last(26,-1);
    // 文字xが最後に登場する場所を前計算
    {
        for(int i = sz - 1;i >= 0;i--){
            if(last[s[i] - 'a'] == -1) last[s[i] - 'a'] - i;
        }
    }
    int tmp = 0; // 現在のノード番号
    for(int i = 0;i < sz;i++){
        // 接頭辞[0,i)に、[i,sz)のうち1文字を追加する
        for(int c = 0;c < 26;c++){
            if(j <= last[c] && match(tmp,c)){
                ans++;
            }
        }
        tmp = g[tmp].nextid[s[i] - 'a'];
　　　　　// [0,i+1)を接頭辞とする文字列が存在しないので、それ以上探索する必要がない
        if(tmp == -1) break; 
    }
    insert(s);
}

Trie木そのものの説明とか図とかは暇があったら描きたします、わかりにくいところなどありましたらご連絡お願いします。

提出： Submission #15813418 - AtCoder Grand Contest 047

コンテスト中に通せなかったのがとても心苦しいです。というかTrie木をちゃんと勉強していなかったので、脳裏には浮かんだけれどsetでぶん殴ろうとしてTLE...という悲しい結果でした。

AtCoder Regular Contest 056 駐車場

昔のARCもちゃんと埋めていこうと思います。

問題概要

無向グラフが与えられる。人i(1 <= i <= N)は始点Sから出発して、自分より小さい番号の頂点を通らずに頂点iまで到達できるだろうか？到達できる番号を全て列挙せよ。

頂点数、辺数共に2e5以下。

解法

解説PDFをなぞるような形になりますが、実装も示します。

頂点Sから頂点 i まで、iより大きい辺のみを通って行けるパスが存在することが、人iが頂点iに到達できることの必要十分条件です。グラフは木とは限らないので、パスは一通りではなく複数あり得ます。人iがあるパスを通って頂点iにたどり着けるかを決定するのは、そのパス中で最小の番号の頂点です。ここで、人iはSからiまでのパスのうち、最小の番号が最も大きいパスを選ぶことが最適であることがわかります。

cost[i] を、始点Sから頂点iまでのパス中の最小番号としてあり得るものの最大値、とします。

cost[s] = sに注意します。「人iが頂点iにたどり着ける」 ⇔ (cost[i] >= i)です。

さて、cost[i]は頂点Sから出発したDIjkstra法と同様のアルゴリズムで、cost[i]が大きい頂点から順番に決定することができます。現在未確定のcostのうち、最大のcostは他のcostによってより大きくなることがあり得ないからです。

実装は次の通りです。

// solution for ARC056B
// author : lynmisakura

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i,n) for(int (i) = 0;(i) < (n);(i)++)

const int maxn = 200020;

int n,m,s;
vector<int> g[maxn];

void read(){
  cin >> n >> m >> s;
  s--;
  REP(i,m){
    int u,v;cin >> u >> v;
    u--,v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
}

int cost[maxn];

int main(int argc, char const *argv[])
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  read();

  REP(i,n) cost[i] = -1;
  cost[s] = s;

  priority_queue<pair<int,int>> q; // {cost,index}  
  cost[s] = s;
  q.emplace(s,s);

  while(q.size()){
    
    int c = q.top().first;
    int v = q.top().second;
    q.pop();

    int newcost = min(cost[v] , v);

    for(int i : g[v]){
      if(newcost > cost[i]){
        cost[i] = newcost;
        q.emplace(newcost,i);
      }
    }

  }

  REP(i,n){
    if(cost[i] >= i)cout << i+1 << '\n';
  }

  return 0;
}

ABC174 参加記録

ググり力、灯台下暗しと言ったところでした。

レートは冷えたけど、学びもありました。Eまでは悪くないペースだったと思うけど...

A問題

こう言う問題で秒単位で時間を削るなら3項目演算子使うべきなんだろうけど素直にif文を書いてしまった。いや別にいいんだけど...

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i,n) for(int i = 0;i < n;i++)

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int x;cin >> x;
  if(x >= 30)cout << "Yes" << '\n';
  else cout << "No" << '\n';

}

B問題

最初入力が実数だと勘違いして(誤読1)誤差大丈夫かなEPS用意しないといけないやつかと思った

流石にB問題だし誤差大丈夫だろと思ってたらそもそも整数だった

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i,n) for(int i = 0;i < n;i++)

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int ans = 0;

  int n;cin >> n;
  ll d;cin >> d;
  REP(i,n){
    ll x,y;cin >> x >> y;
    if(x*x+y*y <= d*d)ans++;
  }

  cout << ans << '\n';
}

C問題

Mで割ったあまりの周期は高々Mとかになるやつ。最初M%2==0で-1とかやってたら案の定TLEした。うるうる

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  ll k;cin >> k;
 
  if(k % 2 == 0){
    cout << -1 << '\n';
    return 0;
  }
 
  ll ten = 1;
  ll tmp = 0;
  int cnt = 1;
  for(int i = 0;i < 1e7;i++){
    ll add = (7 * ten) % k; 
    tmp = (tmp + add) % k;
    ten = (ten * 10) % k;
    if(tmp == 0){
        cout << cnt << '\n';
        return 0;
    }
    cnt++;
  }
  cout << -1 << '\n';
 
}

D問題

隣接swapだと勘違いして(誤読2)時間を溶かしていた。 Rを全部左に詰めるから、最初の入力で（Rの個数をMとする）、[0,M)の範囲にあるRは動かさなくていいことに注意するとO(N)で計算できる

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  ll n;cin >> n;
  string s;cin >> s;
 
  ll ans = 0;
 
  ll cnt = 0;
  REP(i,n)cnt += (s[i] == 'R');
 
  REP(i,n){
    ans += (i >= cnt && s[i] == 'R');
  }
 
  cout << ans << '\n';
}

E問題

一目見て二分探索だと気づいたので書いて通す。これはすぐできた

ll n,k;
ll a[maxn];
void read(){
    cin >> n >> k;
    REP(i,n)cin >> a[i];
}
 
bool func(int x){
    ll cnt = 0;
    REP(i,n){
        cnt += ((a[i] + x - 1) / x) - 1;
    }
    return cnt <= k;
}
 
int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
  read();
  int l = 0,r = 1e9 + 1;
 
  while(l + 1 != r){
    int mid = (l + r)/2;
    // can all len <= mid ?
    if(func(mid))r = mid;
    else l = mid;
  }
 
  cout << r << '\n';
 
}

F問題

fastestが2分を切っているのを見て、データ構造かライブラリか超有名知識なんだろうと察しをつけ、色々とググろうとしたけどダメだった。と言うか、格好つけて英単語を並べて英語の記事を探そうとしてた。普通に日本語の記事に本質があった...（TODO：通したらリンクを貼る）

まとめ

青になって初めてのrated。レートはとかしてしまったけど、データ構造系の有名知識も身につけていかないといけないなと感じ、教訓になった。また頑張ります。 夏休みが近いので、夏休みになったらCFのばちゃとかをたくさんやりたい。1ヶ月しかないと言うか将来のこともやんなきゃいけないけど。

AtCoderで青になりました

2020/7/25 M-SOLUTIONSプロコンオープン2020で、AtCoder青色レートになりました！

実に一年近くを過ごした水色レートを卒業できてとても嬉しいです。

実は青色レートが現実的な視野に入ってきたのはごく最近です。6月の後半ぐらいで、1800〜2100程度のパフォーマンスが連続して出るようになり、この頃ようやく青に行けそうだという気持ちになってきました。それまで、2019年夏から今年の初夏ごろまでは1200 - 1400を上下する、いわゆる「停滞」期間に入っていました。なかなか思うようにAtCoderでいい成績が出せず、辛い気持ちになることも多かったです。

よく言われるように精進の結果が現れるには時間差があるのだと思います。ところが自分は言葉にできるような体系的な(?)精進をあまりしていないように思えます。

これを見るとわかるように、特に何かを「埋めた」というわけでもありません。強い競プロerや精進をたくさんしている人がABC-A,Bを全部埋めたとか、○色 を全部埋めたという話をしていますが、自分にはとてもその手の「達成」ができる体力や精神力が備わっていない（これは人生における大きな自分の欠点であるという自覚はあります）わけです。じゃあ才能があったのか？と言われると、もちろんそんなわけはないです。自分は極めていい加減な人間です。積み上げが苦手で、集中力が乏しく、物事に対する姿勢は怠惰で、粗雑な人間です。

僕はコンテスト中のアドレナリン、エクスタシーをモチベーションに競プロをやっていることに最近気がつきました。僕はratedコンテストが好きです。unratedになると結構本気で怒ります。...僕は結構根に持つタイプなのかもしれません。

でも、僕が水色から400レートを伸ばすことができた原因が一つあるとしたらコンテストに拘ることだったかもしれません。誰だってコンテストには本気で出ていると思います。辛い気持ちになってまで競プロを続けるべきではないというツイートをよく見ますし、それは人生という枠組みにおいて多分正しいですが、僕は辛い気持ちになったから青になれたと思っています。それは自分に数理的才能と教養が備わらず、人生においてきちんと自分を涵養できなかったことに他なりません。それならば辛いのは自業自得ではないか？と言われるとやっぱりそうかもしれません。

僕はAtCoderが伸び悩み辛い時期にcodeforcesでは比較的好成績を出すこともできたのでそれをモチベーションにしていました。こどふぉはこどふぉで勉強になります。

コンテストで冷えたり、現状維持に近いような成果しか出せなかった回には必ず実戦的な失敗があります。コーナーケースを見落として200点問題でWAを吐く、WAで焦って冷静さを欠き後ろの問題に特攻してほとんどの人がとけた400点をとうとう解けずにコンテスト終了、32bit整数型のオーバーフロー、多重ループで添字をミスってデバッグに時間を溶かす...実戦的な失敗は決して「高度なアルゴリズム・考察がコンテスト中に生えなかった」ことへの後悔ではありません（少なくとも水色→青色においては）。

（イラストに特に意味はありません。ちょっとした目の保養です。）

僕はあまり理性的な人間ではないのかもしれません。よく競プロは論理的思考力に強く依存すると言われますが、論理も大事ですが、より重要なのが理性だと思っています。適切に人生を進めることが競プロに時間を捻出するために重要な行為です。というかそもそも僕はあまり論理的思考というものの存在を信じていない節があります。僕がコンテスト中しばしば陥りがちな、感情と身体感覚だけに駆動されて振る舞いを決定するのは例えば性に溺れた猿的人間のそれとほとんど変わらないような気がしています。

それでも、毎回のコンテストに出ることで、多くの反省と、時々はちょっと成功したという喜びを胸に、より理性的で適切な振る舞いを身につけていくことが次のパフォーマンスにつながると信じています。

...ここまで書いて、それでもやっぱりここまで読んでくれた人のためにちょっとは競プロ的に役立つことも書いておかないと申し訳がない気がするので、ちょっとだけ競プロの話をします。

別に意図しているわけではないと思いますが、ABCでは必要とされるアルゴリズムや解法が連続して出題される傾向があるように思われます。ある時期には文字列アルゴが連続して出たり、またある時期には二分探索的手法、全方位木DPがABC->CF->ABCみたいな感じで立て続けで出題された時期もあって、それで自分含め全方位木DPを勉強した人は多かったと思います。最近は数え上げが多い気がします。得意分野と言えるものは特にありませんが強いて言えば数え上げが後ろの方にあった時はパフォーマンスが高めだったと思います。ABCに限らず、コンテストはそれぞれに独特の出題傾向があります。継続してコンテストに出続けることでそのコンテストに慣れていくことや傾向を掴んでいくことがレーティングの上ではある程度意味があると思います。

（イラストに特に意味はありません。ちょっとした目の保養です。）

コンテストに出て、復習する時に、二つのことに注意しています。一つは、先ほども述べたように、実戦的な反省、もう一つは、問題そのものの復習（新しい知見を獲得する）です。体に競プロを""わからせる""ことが重要です。

ライブラリの整備はほとんどしていません。日常的に使ってるライブラリはmodint（と二項係数）とUnionFindぐらいしかありません（特に抽象化とかもしてません）。ライブラリ整備はやろうやろうと言いつついつも先延ばしにしてしまいます。まあ二項係数、ダイクストラ、UnionFind、LCA、あとは線形文字列検索（Zアルゴとか）が一つあれば青に行くためには大抵十分だと思います。

競プロ界隈は結構ライブラリ整備とか知識増強を重視する傾向がありますが（茶色とか緑の人がツイッター経由でいろんなアルゴリズムの名前に触れていくのはいいけどなんか優先順位の判断が微妙そうな人をよく見ます、緑で遅延セグ木使う場面はないんじゃないかな...みたいな）、それよりもなんかもっと非言語的な部分で大事なことがあると僕は信じています。なんというか、いろいろなイメージ的知見が噛み合うと解ける問題の幅が広がり、また、コンテスト中で簡単な問題を落とさなくなると思います。特にABCが6問になってからABC-Fで結構知識が問われる問題が増えてきたことも影響していると思います。でも、知識やライブラリを固めてこれだけ知識とライブラリがあるんだからと安心して強い実装上のオプションを頭の中で思い浮かべられるようになるというのも大事なことだと思うので、今後は自分も知識増強を本格的に着手していこうと思います。

数学を鍛えたいので数学オリンピックの問題を最近は解いています。朝倉書店の『組み合わせ論の精選102問』『数論の精選104問』を解いています。難しいです。個人的にはこれが競プロに直接生きるという期待よりは、離散数学的な議論とかに慣れ親しむことが競プロの解説や議論についていく上で生きてくるかなぁと思ってやっています。（最近ちょっとサボり気味です）

（イラストに特に意味はありません。ちょっとした目の保養です。）

まとまりがなくなってきましたが長くなってもあれなのでこの辺で切り上げようと思います。ここまで読んでくださりありがとうございました。いつか黄色エントリが書けるように精進したいと思います。その頃にはまた色々と見方が変わっているのかなぁ...

（ユーフォ久美子3年生編が完成しますように、サクラノ刻が出ますように）

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';
}

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