誤ったアプローチです。記録に書いておきます。アプローチは悪くはなかったと思っていたんだけどそういう問題ではなかった...
題意
- $1e5$の以内の数字が$1e5$個、数列として与えられます。その中から$k$個以内の数字を消してよいです。同じ数字が続く連絡した部分列を良い部分列と呼びます。
- 作れる最大の部分列の長さを答えよ。
想定解法(TL, solution議論)
値ごとにリストを作り、ある$l$に対して、indexが欠けている数が$k$以下であるような$r$をスライディングウィンドウ。$O(N)$
こう考えた(誤回答): two-pointer + 二分探索
ある長さ$a$がつくれるかを判定する。$a$がつくれるとはあるiに対して$[i, i+a+k-1]$においてある文字がa個以上含まれていれば良い(これを判定と呼ぶ)。なぜなら、ある文字が最低$a$個含まれているなら他の文字を$k$個消せばある文字だけの長さ$a$の部分数列とできる。
0 1 2 3 4 5 6 7 8
例: [1, 2, 3, 3, 4, 4, 3 ,3, 1]
^^^^^^^^^^^^^^^^
k = 2の時、[2,7]でind=4,5を消して[3,3,3,3]の長さ4が答え
値域が$1e5$程度なので次のように考える。
最初にi = 0として、最初のウィンドウ$[i, i+a+k-1]$の各値の出現頻度を数えておく。判定成功なら達成できる。two-pointerの要領でシフトをずらしてく。
一点変更区間maxが出来れば良いのでセグメント木などで実装できる。この操作に必要な計算量は$O(N log N)$。
元の問題の答えは二分探索可能($a$が達成な時$a-1$は明らかに達成できる)なので二分探索する。
以上により$O(N (log N)^2)$...TLEしました。
実装(TLE)
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
using namespace std;
using namespace atcoder;
long long op(long long a, long long b) { return max(a, b); }
long long e() { return -1; }
class Solution {
public:
int longestEqualSubarray(vector<int>& nums, int k) {
int n = (int)nums.size();
int ans = -1;
auto func = [&](long long target) -> bool{
if(n < target) return false; // n以上というのはどう考えても無理
int flen = min(n, target+k); // 最初のウィンドウの長さ. max n.
int l = 0; // ここから取り込んでいる
int r = flen - 1; // ここまでは取り込んでいる
vector<long long> initseg(n+1);
REP(i, flen) { // 最初の読み込み
//cerr << "initload" << nums.at(i) << endl;
++initseg.at(nums.at(i));
}
segtree<long long, op, e> seg(initseg);
// 最初のトライで既にtarget以上の要素がいるならok
if(seg.all_prod() >= target) return true;
// シフトしていく
while((r+1) < n){
r++; // rに関しては入れていけばok
seg.set(nums.at(r), seg.get(nums.at(r)) + 1); // 更新する
// lは抜けていくので
seg.set(nums.at(l), seg.get(nums.at(l)) - 1); // 更新する
l++;
if(seg.all_prod() >= target) return true; // この状態でOKなら抜ける
}
return false;
};
// [ok, ng) for max value いける最大の値を求めたいとき
// (ng, ok] for min value 可能となる最小の値を出したいとき
// CATION: ok is result (NOT mid)
int ok = 0;
int ng = n+100;
int mid;
while(abs(ok - ng) > 1){
mid = (ok + ng) / 2;
if(func(mid)) ok = mid;
else ng = mid;
}
//assert(ans != -1);
return ok;
}
};