VK Cup 2015 Qualification Round 2

こちらも練習のみ。
http://codeforces.com/contest/523

A. Rotate, Flip and Zoom

矩形状の文字列が与えられる。
それらを右に90度回転し、上下を反転し、上下左右２倍に拡大せよ。

指定通り変換すればよい。

int W,H;
string S[202],S2[202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) S2[x] += S[y][x];
	}
	FOR(y,W) {
		FOR(x,H) cout<<S2[y][x]<<S2[y][x];
		cout<<endl;
		FOR(x,H) cout<<S2[y][x]<<S2[y][x];
		cout<<endl;
	}
}

B. Mean Requests

N要素の整数列A[i]とTが与えられる。
ここでM個のクエリP[i]に答えよ。
各クエリでは、real(A[P[i]-T+1]～A[P[i]]個の平均値)、approx(問題文で指定された重み付平均値)、error(realとapproxの誤差)を出力せよ。

realもapproxも累積和の要領で計算していけばよい。

int N,T,M;
double C;
ll A[303000],S[303000];
double ap[303000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T>>C;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
		ap[i+1]=(ap[i]+A[i]/(double)T)/C;
	}
	
	
	cin>>M;
	while(M--) {
		cin>>x;
		double re=(S[x]-S[x-T])/(double)T;
		_P("%.6lf %.6lf %.6lf\n",re,ap[x],fabs(ap[x]-re)/re);
	}
}

C. Name Quest

２つの文字列S,Tが与えられる。
Tを前半と後半の２つに分けたとき、どちらも部分文字列としてSを含むような区切れ目を答えよ。

TのprefixでSを含む最小のindexであるLと、TのpostfixでSを含む最大のindexであるRを求め、R-Lを答えればよい。
L＞Rなら条件を満たす分け方はできない。

string S,T;
int L=-1,R=-1;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>S>>T;
	
	x=0;
	FOR(i,T.size()) {
		if(T[i]==S[x]) {
			x++;
			if(x==S.size()) {
				L=i;
				break;
			}
		}
	}
	x=S.size()-1;
	for(i=T.size()-1;i>=0;i--) {
		if(T[i]==S[x]) {
			x--;
			if(x==-1) {
				R=i;
				break;
			}
		}
	}
	if(L>=0 && R>=0 && L<=R) cout<<R-L<<endl;
	else cout<<0<<endl;
}

D. Statistics of Recompressing Videos

N個の動画をK個のサーバで処理する。
各動画は時刻S[i]に到着し、処理にM[i]だけかかる。
全サーバが処理中の場合、動画は到着順にキューイングされる。
各動画の処理が完了する時刻を求めよ。

処理終了時刻をmultisetで処理する。
S[i]までに処理が終わらないサーバがK個以上あるなら、残り(K-1)個になるまで待ったのち、S[i]+M[i]をmultisetに追加する。

int N,K;
ll S[506000],M[505000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	multiset<ll> SS;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>S[i]>>M[i];
		
		while(SS.size() && *SS.begin()<=S[i]) SS.erase(SS.begin());
		
		if(SS.size()<K) {
			cout<<S[i]+M[i]<<endl;
			SS.insert(S[i]+M[i]);
		}
		else {
			cout<<*SS.begin()+M[i]<<endl;
			SS.insert(*SS.begin()+M[i]);
			SS.erase(SS.begin());
		}
	}
}

まとめ

Qualification Round 1より若干簡単。