読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

天下一プログラマーコンテスト2013 予選B : A - 天下一人力比較、B - 天下一後入れ先出しデータ構造

その他コンテスト

予選Bにも参加。A,Bは完答、C・Eが部分点だけど、Eが満点取れずTシャツゲットならず…。
Eの比重が高すぎる気がするが、まぁしょうがない…。
今回まだCは解ききってないけど、Cが一番面白かったかな。
http://tenka1-2013-qualb.contest.atcoder.jp/tasks/tenka1_2013_qualB_a
http://tenka1-2013-qualb.contest.atcoder.jp/tasks/tenka1_2013_qualB_b

A - 天下一人力比較

文字列がいくつか与えられるので、辞書順ソートして7番目の文字列を返せ。
テスト項目は1つだけなので、コードを書かず秀丸上でソートして回答しちゃった。

B - 天下一後入れ先出しデータ構造

最大長Lのスタックに対し、以下のクエリをQを投げる。

  • 整数MをN個スタックにpush。
  • スタックからN個pop。
  • スタックの最上位の整数値を返す。
  • スタック長を返す。

スタックに律儀にN個入れるとメモリも時間も溢れるので、整数値と要素数の組をvectorに放り込んで増減させればよい。

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty,aa[5];
	ll Q,L;
	vector<pair<ll,ll> > V;
	
	cin>>Q>>L;
	ll tt=0;
	FOR(i,Q) {
		string S;
		ll N,M;
		cin>>S;
		if(S=="Push") {
			cin>>N>>M;
			if(tt+N>L) return (void)_P("FULL\n");
			V.push_back(make_pair(M,N));
			tt+=N;
		}
		else if(S=="Pop") {
			cin>>N;
			if(tt<N) return (void)_P("EMPTY\n");
			tt-=N;
			while(N>0) {
				ll hoge=min((ll)N,(ll)V[V.size()-1].second);
				N-=hoge;
				V[V.size()-1].second-=hoge;
				if(V[V.size()-1].second==0) V.resize(V.size()-1);
			}
		}
		else if(S=="Top") {
			if(tt==0) return (void) _P("EMPTY\n");
			_P("%lld\n",V[V.size()-1].first);
		}
		else if(S=="Size") {
			_P("%lld\n",tt);
		}
	}
	_P("SAFE\n");
	
	return;
}

まとめ

なんかBとかEとかCodeForcesに出そうな問題だな…。

広告を非表示にする