kmjp's blog

競技プログラミング参加記です

Manthan Codefest'18 : F. Maximum Reduction

普段の2000ptよりは簡単かも。
http://codeforces.com/contest/1037/problem/F

問題

N要素の整数列Aと、パラメータKが与えられる。
整数列に対し以下を繰り返し行う。

  • 長さがK以上であれば、長さKの連続部分列を総当たりし、その順で連続部分列の最大値を並べた数列に置き換える。

処理を行うたびに生成される数列の値の総和を求めよ。

解法

処理を行うたびに数列の値がどうなるかを考えよう。
B(n,m) := Aにm回処理を行ったものの第n要素(0-origin) とする。
するとB(n,m) = max(A[n..(n+m*(K-1))]) となる。
ここで、B(n,m) = max(B(n+(K-1),m-1),max(A[n...(n+K-1)]) となる。また、B(n,*)は単調増加となる。

よって、B(n+(K-1),*)がわかっている場合、max(A[n...(n+K-1)])>B(n+(K-1),m)となる範囲でB(n+(K-1),m)を置き換えれば、そのままB(n,m)の列が求められる。
よって、nをmod (K-1)の値で分類し、それぞれB(n+(K-1),*)からB(n,*)およびその総和を求めるということを順次行っていけばよい。
B(n+(K-1),*)は同じ値を複数持つので、map等で持っておけばmax(A[n...(n+K-1)])>B(n+(K-1),m)の場合の値の置き換え回数も均しでO(N)回に押さえられる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll,1<<21> st;

int N,K;
int A[1010101];
vector<int> C[1010101];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&K);
	FOR(i,N) {
		scanf("%d",&A[i]);
		st.update(i,A[i]);
		if(i+K<=N) C[i%(K-1)].push_back(i);
	}
	ll ret=0;
	FOR(i,K) {
		reverse(ALL(C[i]));
		map<ll,ll> M;
		ll tot=0;
		FORR(c,C[i]) {
			ll ma=st.getval(c,c+K);
			(tot+=ma)%=mo;
			M[ma]++;
			while(M.begin()->first<ma) {
				(tot+=(ma-M.begin()->first)*M.begin()->second)%=mo;
				M[ma]+=M.begin()->second;
				M.erase(M.begin());
			}
			(ret+=tot)%=mo;
		}
	}
	cout<<ret<<endl;
}

まとめ

A[i]が何回答えに加算されるか、を考える解法もあるようだ。