QUPC2014 : A - 成績判定、B - 元素の系統名、C - 案内所、E - 捕獲

QUPCは平日昼間開催なので本番は不参加。
割とやさしめっぽいので復習してみた。全部自力で解けるレベルだね。
まずは100点問題から。
http://qupc2014.contest.atcoder.jp/tasks/qupc2014_a
http://qupc2014.contest.atcoder.jp/tasks/qupc2014_b
http://qupc2014.contest.atcoder.jp/tasks/qupc2014_c
http://qupc2014.contest.atcoder.jp/tasks/qupc2014_d

A - 成績判定

C人それぞれA科目の得点が与えられる。
各科目の合格点をK点とし、A科目中B科目K点以上取るとその人は合格である。
合格者がD人以上となる最大のKを求めよ。

Kを大きい順に試していくだけ。

int A,B,C,D;
int E[101][101];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>A>>B>>C>>D;
	FOR(y,C) FOR(x,A) cin>>E[y][x];
	
	for(i=101;i>=0;i--) {
		j=0;
		FOR(x,C) {
			k=0;
			FOR(y,A) k+=E[x][y]>=i;
			j+=k>=B;
		}
		if(j>=D) return _P("%d\n",i);
	}
}

B - 元素の系統名

元素番号が与えられるので、ルールに従い命名せよ。
これはルールに従い文字列をくっつけるだけ。
nが3つ続いた場合は1個消せばよい。

void solve() {
	int f,i,j,k,l,x,y;
	cin>>x;
	string s;
	
	if(x/100==0) s+="Nil";
	if(x/100==1) s+="Un";
	if(x/100==2) s+="Bi";
	if(x/100==3) s+="Tri";
	if(x/100==4) s+="Quad";
	if(x/100==5) s+="Pent";
	if(x/100==6) s+="Hex";
	if(x/100==7) s+="Sept";
	if(x/100==8) s+="Oct";
	if(x/100==9) s+="Enn";
	if(x/10%10==0) s+="nil";
	if(x/10%10==1) s+="un";
	if(x/10%10==2) s+="bi";
	if(x/10%10==3) s+="tri";
	if(x/10%10==4) s+="quad";
	if(x/10%10==5) s+="pent";
	if(x/10%10==6) s+="hex";
	if(x/10%10==7) s+="sept";
	if(x/10%10==8) s+="oct";
	if(x/10%10==9) s+="enn";
	if(x%10==0) s+="nilium";
	if(x%10==1) s+="unium";
	if(x%10==2) s+="bium";
	if(x%10==3) s+="trium";
	if(x%10==4) s+="quadium";
	if(x%10==5) s+="pentium";
	if(x%10==6) s+="hexium";
	if(x%10==7) s+="septium";
	if(x%10==8) s+="octium";
	if(x%10==9) s+="ennium";
	
	FOR(i,s.size()) {
		if(i<s.size()-2 && s[i]=='n' && s[i+1]=='n' && s[i+2]=='n') continue;
		_P("%c",s[i]);
	}
	_P("\n");
	
}

C - 案内所

2次元グリッド状の文字列が与えられる。
その後、幾つか1文字のクエリが与えられるので、グリッド中その文字の座標を返せ。

前処理として各文字の位置を配列に入れておくだけ。

int W,H;
int X[256],Y[256];
int Q;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W>>Q;
	FOR(x,256) X[x]=Y[x]=-1;
	FOR(y,H) {
		string s;
		cin>>s;
		FOR(x,W) X[s[x]]=x,Y[s[x]]=y;
	}
	
	while(Q--) {
		string s;
		cin>>s;
		if(X[s[0]]==-1) _P("NA\n");
		else _P("%d %d\n",Y[s[0]]+1,X[s[0]]+1);
	}
}

E - 捕獲

猿が初期位置(x,y)から速度(vx,vy)で等速直線運動する。
この猿に原点から速さVで追いつけるか。追いつけるならその時間を答えよ。

T秒後に追いつくと仮定すると、(x+vx*T)^2+(x+vy*T)^2 == V^2 という二次方程式ができるので、T>=0の解を求めればよい。
Tの2次の項が0となる場合に注意。

int X,Y,VX,VY,VH;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>X>>Y>>VX>>VY>>VH;
	double A=VX*VX+VY*VY-VH*VH;
	double B=2*X*VX+2*Y*VY;
	double C=X*X+Y*Y;
	
	if(A==0) {
		if(B==0) {
			if(C==0) return _P("0\n");
			else return _P("IMPOSSIBLE\n");
		}
		else {
			double ho=-C/(double)B;
			if(ho<0) return _P("IMPOSSIBLE\n");
			else return _P("%.12lf\n",ho);
		}
	}
	
	double D=B*B-4*A*C;
	if(D<0) return _P("IMPOSSIBLE\n");
	double V1=(-B-sqrt(D))/(2*A);
	double V2=(-B+sqrt(D))/(2*A);
	if(V1>V2) swap(V1,V2);
	if(V1>=0) return _P("%.12lf\n",V1);
	if(V2>=0) return _P("%.12lf\n",V2);
	return _P("IMPOSSIBLE\n");
	
}

まとめ

このあたりはすんなり。