結構速度が厳しいね。
https://yukicoder.me/problems/no/1460
問題
整数列Aの先頭K要素と、K要素の整数列Bが与えられる。
K要素目以降は、
A[i] = max(min(A[i-K],B[0]),min(A[i-K+1],B[1]),...,min(A[i-1],B[K-1]))
で定義できるとき、N項目以降を求めよ。
解法
解vを二分探索することを考えると、A,Bの各要素はv以上かv未満の2値だけ考えればよくなる。
dp(x) := A[i]=v以上で、i mod K=xとなる最小のi
とすると、A[x+nK]はいずれもv以上となる。
そこで、ダイクストラ法の要領でdp(x)を埋めて行こう。
int K; ll N; ll A[1010],B[1010]; ll X[1010],Y[1010]; ll dp[1010]; ll ok(ll v) { int i; if(N<K) return A[N]>=v; vector<int> cand; FOR(i,K) if(B[K-1-i]>=v) cand.push_back(i+1); if(cand.empty()) return 0; int T=cand.back(); priority_queue<pair<ll,ll>> Q; FOR(i,T) dp[i]=1LL<<60; FOR(i,K) if(A[i]>=v) { FORR(c,cand) if(i+c>=K) dp[(i+c)%T]=min(dp[(i+c)%T],(ll)i+c); } FOR(i,T) Q.push({-dp[i],i}); while(Q.size()) { ll cur=-Q.top().first; int tar=Q.top().second; Q.pop(); if(dp[tar]!=cur) continue; if(cur>N) return 0; if(N%T==tar) return 1; FORR(c,cand) if(cur+c>=K&&dp[(cur+c)%T]>cur+c) { dp[(cur+c)%T]=cur+c; Q.push({-(cur+c),(cur+c)%T}); } } return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>K>>N; FOR(i,K) cin>>A[i]; FOR(i,K) cin>>B[i]; ll ret=-1LL<<60; for(i=60;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i; cout<<ret<<endl; }
まとめ
max/min/medianがからむ問題は、二分探索すると楽っての、すぐ忘れるんだよな。