UAPC2011参戦記

とりあえず結果

rank	AC	time	A	B	C	D	E	F	G	H	I	J	K	L
85	2	216	73/3	-	-	0/1	-	-	0/1	0/41	-	-	82/0	-

あんまこのACM/ICPC方式の得点のつけ方よくわからないけどHを41回ほどSubmitしていることに注目ｗｗｗ

A

伝票の発行時間と商品の提供時間が与えられます。
で、そのタイムラグが8分であるようなものが"ok"な伝票とします。
各時間帯での"ok"な伝票の割合を求めなさい…という問題。
詳しい制約については省略。注意したいのは出力。結構工夫しないと、小数点以下が四捨五入された結果になっていたり、全部0になったりする。

正解コード

#include <cstdio>
#include <iostream>
using namespace std;
/*
昼は11:00 ~ 14:59,
夕は18:00~20:59,
深夜は21:00~翌01:59
*/
int main() {
	int n;
	while (scanf("%d",&n)&&n!=0) {
		int lcnt=0,dcnt=0,mcnt=0,lok=0,dok=0,mok=0;
		for (int i=0; i<n; i++) {
			int h,t,e; scanf("%d%*c%d%d",&h,&t,&e);
			int lag = e-t;
			if (lag<0) lag += 60;
			if (11<=h&&h<=14) {
				if (lag <= 8) lok++;
				lcnt++;
			} else if (18<=h&&h<=20) {
				if (lag <= 8) dok++;
				dcnt++;
			} else if (21<=h||h<=1) {
				if (lag <= 8) mok++;
				mcnt++;
			}
		}
		if (lcnt==0) {
			cout << "lunch no guest" << endl;
		} else {
			double res = (double)lok*100/(double)lcnt;
			printf("lunch %d\n",(int)res);
		}
		if (dcnt==0) {
			cout << "dinner no guest" << endl;
		} else {
			double res = (double)dok*100/(double)dcnt;
			printf("dinner %d\n",(int)res);
		}
		if (mcnt==0) {
			cout << "midnight no guest" << endl;
		} else {
			double res = (double)mok*100/(double)mcnt;
			printf("midnight %d\n",(int)res);
		}
	}
}

B

アニメをなるたけ多く見れるように、しかも好きな物は必ず観るようにしたとき見ることができるアニメの数の最大数を求める問題。
最初制約が意味不明なことになっててコンテスト途中で改正されました。
とりあえずコンパイルエラーでたし解説できないので省略。

C

なんかマンガの読み方？みたいなやつ。
よくわかんないから飛ばし。

D

家を二分化する最小のコストを求める問題。
サンプルみてたらサンプルだけ通すコードみつけたので書いたけどハズイから省略。

E

なんかよくわかんないから却下

F

わがままな二人のためにチョコレートをわけよう！
即諦め

G

結局ひたすら計算量減らしましょう！ってやつ。
多分メモ化で減らせる。
小細工しないTLEコードを一応添付

/*tle*/
#include <cstdio>
#include <vector>
using namespace std;
int main() {
	int r,c,q;
	while (scanf("%d%d%d",&r,&c,&q)&&r!=0&&c!=0&&q!=0) {
		vector<int> m(c);
		vector<vector<int> > maps(r,m);
		for (int i=0; i<r; i++) for (int j=0; j<c; j++) scanf("%d",&maps[i][j]);
		for (int i=0; i<q; i++) {
			int r1,c1,r2,c2; scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
			int min=2147483647;
			for (int y=r1; y<=r2; y++) {
				for (int x=c1; x<=c2; x++) {
					if (min>maps[y][x]) min = maps[y][x];
					if (min==0) break;
				}
				if (min==0) break;
			}
			printf("%d\n",min);
		}
	}
}

メモ化の方法とかは偉い人が考えます←

H

41回の無念。
とある数列を求めるのだけど、法則が分かっていても何故か通らない。
要解説・・・いや求解説

/*wa*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
typedef vector<ll> vl;
ll gcd(ll a, ll b) {
	if(a%b==0) return b;
	return gcd(b,a%b);
}
int main() {
	int n;
	while (cin>>n&&n!=0) {
		int s = n*(n+1)/2;
		vl num(s);
		int cnt=0, cnt2=n;
		for (int i=0; i<s; i++) {
			int tmp; cin>>tmp;
			if (tmp%2==0) {
				num[cnt]=tmp;
				cnt++;
			} else {
				num[cnt2]=tmp;
				cnt2++;
			}
		}
		/*bの偶数要素は必ずa0×aiのはず⇒偶数要素の最大公約数がaの偶数になる？*/
		ll g=gcd(num[0],num[1]);
		int c=2;
		while (c<n) {
			g = gcd(g,num[c]);
			c++;
		}
		/* ただし奇数間に別の公約数があるとき最大公約数がa0*公約数となるのでそれを除く。 */
		if (c+1<num.size()) {
			ll odd=gcd(num[c],num[c+1]);
			c += 2;
			while (c<num.size()){
				odd = gcd(odd,num[c]);
				c++;
			}
			g /= sqrt(odd);	// 奇数のかけ合わせなのでoddは奇数間の最大公約数の二乗になる。
		} else if (n==2) {
			ll a=num[0]/g, b=num[1]/g, tmp=a*b;
			if (tmp!=num[2]) {
				ll d = num[2]/tmp;
				if (g>d) g/=d;
			}
		}
		vl res(n);
		for (int i=0; i<n; i++) {
			res[i] = num[i]/g;
		}
		sort(res.begin(),res.end());
		cout<<g<<endl;
		for (int i=0; i<n; i++) {
			if (i!=0) cout << " ";
			cout << res[i]%2147483648;
		}
		cout << endl;
	}
}

I

なぞ数学

J

Bの主人公再来

K

クソ簡単な問題。
隣接した所にしか移動できなくて縦と横のマス数が与えられたときにだれも同じ席に座らず移動することはできるかという物。
とりあえず縦か横が偶数なら出来ます。
どちらも奇数の時は結論いうと出来ません。
というわけで・・・

正解コード

#include <iostream>
using namespace std;
int main() {
	int r,c;
	while (cin>>r>>c&&r!=0&&c!=0) {
		if (r%2==0||c%2==0) {
			cout << "yes" << endl;
		} else {
			cout << "no" << endl;
		}
	}
}