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

lp6m’s blog

いろいろかきます

ICPC2015国内予選に参加しました

ICPC2015国内予選に参加しました. 去年はKMC(京大マイコンクラブ)の競技プログラミング練習会に参加していたメンバーと参加したけどレベルが違うので今年は2回生の情報学科の人たちで出た.
記念にメモ.
※去年の参加記 2完: LP6m メモ ICPC予選に参加してきました

結果は3完、90位/316チーム.
ACM-ICPC 2015 国内予選順位表

A問題 開始11分

forループで試すだけ.焦って問題文の意味がとれなくて時間がかかった.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)a; i<(int)(b);i++)
#define ll long long
int m,nmin,nmax;
int data[200];
using namespace std;
int main(){
	while(1){
		cin >> m >> nmin >> nmax;
		if(m == 0) break;
		REP(i,m) cin >> data[i];
		
		int ans =0;
		int anss = nmin;
		FOR(i,nmin,nmax+1){
			if(ans<=abs(data[i-1]-data[i])){
				ans = abs(data[i-1]-data[i]);
				anss = i;
			}
		}
		cout << anss << endl;
	}
}

B問題 開始24分

これも試すだけ.一発でサンプルが通ったので嬉しかった.
実はこのとき29位くらいにいた気がする.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)a; i<(int)(b);i++)
#define ll long long
using namespace std;

int n;
int w[50];
int ans = 0;
int test[5] = {5,7,5,7,7};
bool solve(int gyo){
	int nowgyo = gyo;
	int testpos = 0;
	int nowac = 0;
	for(;;){
		if(nowac < test[testpos]){
			if(nowac+w[nowgyo] > test[testpos]){
				return false;
			}else{
				nowac += w[nowgyo];
				nowgyo++;
				if(nowac == test[testpos]){
					nowac = 0;
					testpos++;
				}
			}
		}
		if(testpos==5) return true;
	}
}

int main(){
  while(1){
	cin >> n;
	if(n==0) break;
	REP(i,n) {
		string tmp;
		cin >> tmp;
		w[i] = tmp.size();
	}
	
	REP(i,n){
		if(solve(i)) {
			ans = i;
			break;
		}
	}
	cout << ans+1 << endl;
  }
  

}

C問題 開始131分

逆ポーランド法みたいなやつだからスタックつかえばいけるとわかって実装したけどWA.
ドットの数が減るのは数字のあとしかないと考えていたがそうではなかったので訂正するもWA.

この辺で開始70分くらいでは???っていいながらダウンロードしたテストケースを手で解いていた。ほとんどあってて意味わからんっていってチームみんなで笑ってた。3問とかないと・・って思ってた。

デバッグしてたらとてつもないミスに気付いた. スタックに数字と記号を積んでいたのだが、+と*を10と100で代用していた(入力が0から9までしかないから大丈夫と思い込んでいた)計算途中で10,100になるケースで死んでいることに気付いた. -10, -100にしたら通った.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)a; i<(int)(b);i++)
using namespace std;

long long int n;
stack<long long int> st;

void mydebug(){
	return;
	stack<long long int> st2 = st;
	while(!st2.empty()){
	if(st2.top()==-10) cout <<'*' <<':';
	 else if(st2.top()==-100) cout <<"+ : ";
	 else cout << st2.top() << ":";
	st2.pop();
	}
	cout << endl;
}

void calcstack(){
	vector<long long int> array;
	long long int enzansi;
	mydebug();
	while(!st.empty()){
		long long int elem = st.top();
		st.pop();
		if(elem==-10||elem==-100){
			if(elem == -10) enzansi = 0;
			else enzansi = 1;
			break;
		}else{
			array.push_back(elem);
		}
	}
	long long int ans;
	if(array.size()!=0){
		if(enzansi==0){
			ans = 1;
			REP(i,array.size()) ans*=array[i];
		}else{
		  ans = 0;
		  REP(i,array.size()) ans+=array[i];
		}
		st.push(ans);
	}
	mydebug();
}

int main(){
	while(1){
	  long long int pcnt = 0;
	  long long int oldpcnt = 0;
	  while(!st.empty()) st.pop();
	  cin >> n;
	  if(n==0) break;
	  REP(i,n){
	  	string tmp;
		cin >> tmp;
		pcnt = 0;
		while(1){
			if(tmp[pcnt]!='.'){
				break;
			}else{
				pcnt++;
			}
		}
		long long int num;
		long long int a;
		if(tmp[pcnt]=='*'){
			a = -10;
		}else if(tmp[pcnt]=='+'){
			a = -100;
		}else{
		  num = tmp[pcnt]-'0';
			a = num;
		}
		if(oldpcnt > pcnt){
			REP(j,oldpcnt-pcnt)calcstack();			   
		}
		st.push(a);
		oldpcnt = pcnt;
		mydebug();
	  }
	while(st.size()!=1) calcstack();
	  cout << st.top() << endl;
	}
}

あとは適当に遊んでいた.

今年の問題はどうやら難しくて差がつきにくかったっぽい.予選突破したチームおめでとうです〜〜〜

来年は4問ときたいです!!!
1ヶ月後の試験 is 何って感じだ.