C - Make It Good

cpcodeforcesdiv3greedybinary search

最終更新日

問題

https://codeforces.com/contest/1385/problem/C (新しいタブで開く)

問題文

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

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

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

制約

サンプル

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