GCJ 2R & UAPC2011

GCJ

GCJなんて無かった。超低速1完2000位くらい。悲しかった。

UAPC2011

UAPC2011なんて無かった。2完で60位くらい。悲しかった。

とまあ、UAPCは5時間掛けたのに結局解けたのが2問だったわけですよ。

Bが復活していたのに気づけなかったのが痛かった。一応コンテストではA,Kしか解いていませんが、コンテスト終了後に２問解けたので４つソースのせときます。

問題文: AIZU ONLINE JUDGE

A

midnightの条件をうっかり誤っていた人も多いんじゃなかろうか。

サンプルが巧妙すぎて泣いた。

A,B,K,Hだけ(GとDは解けそうで解けなかった)

string get(int a,int b){
	if(a+b == 0) return "no guest";
	else return itos((double)a/(a+b)*100);
}
int main(){
	int n;
	while(cin >> n && n){
		int a,b,c;
		int q[3]={0},r[3]={0};
		for(int i=0;i<n;i++){
			scanf("%d%*c%d%d",&a, &b, &c);
			int t = -1;
			
			if(b<c)t = c-b;
			else t = (c+60)-b;
			
			if(t <= 8) {
				if(a >= 11 && a < 15){
					q[0]++;
				}else if(a >= 18 && a < 21){
					q[1]++;
				}else if(a >= 21 || a < 2){
					q[2]++;
				}
			}else{
				if(a >= 11 && a < 15){
					r[0]++;
				}else if(a >= 18 && a < 21){
					r[1]++;
				}else if(a >= 21 || a < 2){
					r[2]++;
				}
			}
		}
		cout << "lunch" << " " << get(q[0],r[0]) << endl;
		cout << "dinner" << " " << get(q[1],r[1]) << endl;
		cout << "midnight" << " " << get(q[2],r[2]) << endl;
	}
}

B

スケジューリング？の貪欲法。

アニメの終了でソートして取っていく。蟻本に載っている。

ただ、今回はアニメの放送時間は全て30分で統一されているので、始点ソートしても同じ結果が得られる。

vector< pair<int,int> > data;
map<string,int> wtime;
int main(){
	int n;
	while(cin >> n && n){
		data.clear();
		wtime.clear();
		rep(i,n){
			string a;
			int b,c;
			cin >> a >> c >> b;
			b = (b/100) * 60 + (b%100);
			if(b >= 60*24)b -= 60*24 , c++;
			wtime[a] = c*60*24 + b;
		}
		vector<int> fav;
		vector<int> normal;
		int p;cin >> p;
		rep(i,p){
			string s;
			cin >> s;
			fav.push_back(wtime[s]);
			wtime.erase(s);
		}
		EACH(it,wtime){
			normal.push_back(it->second);
		}
		bool ok = true;
		int ans = 0;
		bool bad[20000]={0};
		rep(i,fav.size()){
			bool f = true;
			int s = fav[i];
			rep(j,30)if(bad[s+j])f = false; 
			rep(j,30)bad[s+j] = true;
			if(!f) ok = false;
			ans++;
		}
		rep(i,normal.size()){
			int s = normal[i];
			bool f = true;
			rep(j,30)if(bad[s+j])f = false; 
			if(f){
				ans++;
				rep(j,30)bad[s+j] = true;
			}
		}
		if(ok)cout << ans << endl;
		else cout << -1 << endl;
	}
}

H

WA出しまくっていて、数列だけど順番で与えられないってことに気づくのに1時間くらい掛かった。

そしてよく分からないWA地獄。コンテスト終了後long doubleとsqrt使ったソースに書き直したら通ってしまった。

int main(){
	int n,w,h;
	
	while(cin >> n , n){
		vector<ll> o,e;
		
		rep(i,n*(n+1)/2){
			ll a;
			cin >> a;
			if(a%2 == 1)o.push_back(a);
			else 		e.push_back(a);
		}
		sort(all(e));
		sort(all(o));
		ll v = sqrt( (long double)e[0] / o[0] * e[1] ) + 0.001; // 誤差対策
		cout << v << endl;
		rep(i,e.size()){
			cout << (i?" ":"") << e[i]/v;
		}
		cout << endl;
		
	}
}

K

まあ色々考え方はありますが、一筆書き(要するにひとつずつずらす)できればok出来なければダメ。なノリ。よって、WかHが偶数かどうか判定するだけで良い。

int main(){
	int w,h;
	while(cin >> w >> h && (w||h)){
		cout << (w%2 == 0 || h%2 == 0 ? "yes" : "no") << endl; 
	}
}