蟻本のアルゴリズムを写経したら通ってしまった…
5304/6000msなのでどう考えても嘘解法
しかもテストケースが甘いからっぽい…N=10^6 MAX_B=200 T=199みたいなので簡単に落とせるハズ
O(K*N*MAX_B*log(N))のはず
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <queue> #include <stack> using namespace std; typedef long long ll; typedef pair<int, int> P; const int INT_INF = (1U<<31)-10; const int MAX_B = 100010, MAX_N = 100010; int b[MAX_N]; int dp[MAX_N]; set<int> s; int main(int argc, char *argv[]) { int K, N, maxb, T; cin >> K >> N >> maxb >> T; for (int k = 0; k < K; k++) { s.clear(); for (int i = 0; i < N; i++) { scanf("%d", &(b[i])); s.insert(b[i]); } if (T >= s.size()) { printf("%ld\n", s.size()); continue; } fill(dp, dp+MAX_N, INT_INF); for (int i = 0; i < T; i++) { for (int j = 0; j < N; j++) { if (b[j] < i) continue; *lower_bound(dp, dp+N, b[j]) = b[j]; } } printf("%ld\n", lower_bound(dp, dp+N, INT_INF) - dp); } return 0; }
O(K*N*MAX_B*log(MAX_B))のアルゴリズムがRMQで書けるのでNとMAX_Bを比べて使い分ければいいのかな〜〜と思って書いたけど、定数倍が重すぎて死
サンプル見ながら調整したら3650msになったけどなんだかな〜〜〜と
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <queue> #include <stack> using namespace std; typedef long long ll; typedef pair<int, int> P; const int INT_INF = (1U<<31)-10000; const int MAX_N = 100010; int K, N, MAX_B, T; int b[MAX_N], b_num; int dp[MAX_N]; set<int> s; int solve_smallN() { fill(dp, dp+MAX_N, INT_INF); for (int i = 0; i < T; i++) { for (int j = 0; j < N; j++) { if (b[j] < i) continue; *lower_bound(dp, dp+N, b[j]) = b[j]; } } return (lower_bound(dp, dp+N, INT_INF) - dp); } const int SEG_SIZE_MAX = 100010*4; int SEG_SIZE; int seg[SEG_SIZE_MAX]; void seg_init() { SEG_SIZE = 1; while (SEG_SIZE < MAX_B) SEG_SIZE *= 2; SEG_SIZE *= 2; fill(seg, seg+SEG_SIZE, INT_INF); } void seg_set(int i, int x) { i += SEG_SIZE/2 - 1; seg[i] = x; while (i) { i = (i - 1) / 2; int s1 = seg[i*2+1], s2 = seg[i*2+2]; seg[i] = min(s1, s2); } } int seg_get(int a, int b, int k = 0, int l = 0, int r = SEG_SIZE/2) { if (a <= l && r <= b) return seg[k]; if (r <= a || b <= l) return INT_INF; int vl = seg_get(a, b, k*2+1, l, (l+r)/2); int vr = seg_get(a, b, k*2+2, (l+r)/2, r); return min(vl, vr); } int solve_smallB() { seg_init(); int min_d = 0; for (int i = 0; i < T; i++) { for (int j = 0; j < N; j++) { int d = b[j]; if (d < min_d) continue; int r = seg_get(0, d) - 1; if (INT_INF - r == d+1) min_d = max(min_d, d); seg_set(d, r); } } return INT_INF - seg_get(0, MAX_B); } int main(int argc, char *argv[]) { cin >> K >> N >> MAX_B >> T; for (int k = 0; k < K; k++) { s.clear(); for (int i = 0; i < N; i++) { scanf("%d", &(b[i])); b[i]--; s.insert(b[i]); } b_num = s.size(); if (T >= b_num) { printf("%d\n", b_num); continue; } int result; if (MAX_B*2 > N) { result = solve_smallN(); } else { result = solve_smallB(); } printf("%d\n", result); } return 0; }
追記
他人のソースを読んだところ二部探索のするべき範囲をキャッシュして云々すると早くなります