CF Round #656 C - Make It Good


Tags:cpcodeforcesdiv3greedybinary_search

問題

https://codeforces.com/contest/1385/problem/C

問題文

長さ nn の数列 aa の先頭からいくつかの要素を削除して、 いい配列 にしたい。
削除する必要がある要素の最小値は?

数列 bbいい配列 であるとは、bb が空になるまで以下の操作を繰り返して、最初は空の配列 cc を広義単調増加にできることをいう。

bb の先頭か末尾のどちらかから要素を選ぶ。
選んだ要素を bb から削除し、 cc の末尾に加える。

制約

  • 1t2×1041 \le t \le 2 \times 10^4
  • 1n2×1051 \le n \le 2 \times 10^5
  • 1ai2×1051 \le a_i \le 2 \times 10^5
  • nn の総和は 2×1052 \times 10^5 を超えない

サンプル

5
4
1 2 3 4
7
4 3 3 8 4 5 2
3
1 1 1
7
1 3 1 4 5 3 2
5
5 4 3 2 3
0
4
0
2
3

考察

決め打ち二分探索 + 貪欲法した。解説は全然そんなことしてなかった

具体的には、 kk を決め打ちして、 aa の先頭 kk 個を削除してから、貪欲に いい配列 にできるか判定する。
先頭/末尾の要素のうち、小さいほうから順番に cc に加えていくのが最適。

コード

https://codeforces.com/contest/1385/submission/126231155

bool chk(deque<int> dq, int start) {
  int prev = 0;
  if (start >= dq.size()) return false;
  while (start--) dq.pop_front();
  while (!dq.empty()) {
    int fr = dq.front();
    int ba = dq.back();
    if (fr >= prev && fr <= ba) {
      prev = fr;
      dq.pop_front();
    }
    else if (ba >= prev && ba <= fr) {
      prev = ba;
      dq.pop_back();
    }
    else if (fr >= prev) {
      prev = fr;
      dq.pop_front();
    }
    else if (ba >= prev) {
      prev = ba;
      dq.pop_back();
    }
    else {
      break;
    }
  }
  return dq.empty();
}

void solve() {
  int n;
  cin >> n;
  deque<int> dq;
  rep(i, n) {
    int a;
    cin >> a;
    dq.push_back(a);
  }
  int ok = n - 1, ng = -1;
  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    if (chk(dq, mid)) {
      ok = mid;
    }
    else {
      ng = mid;
    }
  }
  cout << ok << endl;
}