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

kmjp's blog

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

Maximum-Cup 2013: B - Working for the World、E - Alicia's Rare card Challenge、J - ALPHAのならび

Maximum-Cupは不参加のため復習。
問題番号と難易度が一致しないのが曲者。
まずは簡単な問題から。
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_b
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_e
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_j

B - Working for the World

自然数Nが与えられるので最大の素因数を求めよ。

√Nまでで割っていくだけ。

void solve() {
	int f,i,j,k,l,x,y;
	
	while(1) {
		cin>>x;
		if(x==0) break;
		j=1;
		y=x;
		for(i=2;i*i<=y;i++) while((x%i)==0) j=i,x/=i;
		j=max(x,j);
		_P("%d\n",j);
	}
}

E - Alicia's Rare card Challenge

カードを1枚引いた際、得られるカード名・レアリティ・取得頻度のリストが与えられる。
また、10枚ごとにリスト外の不要なカードが得られることがわかっている。
T回カードを引いた際、カード名に「Alicia」を含み、かつレアリティがNormalより上のカードの取得枚数の期待値を答えよ。

先に不要カードの分T/10を引く。
あとはリストからカード名・レアリティが条件を満たす割合を求めてTと掛けるだけ。

int N,T;
double tot,ok;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>T;
	T-=T/10;
	FOR(i,N) {
		string name,rare;
		cin>>name>>rare>>x;
		
		tot+=x;
		if(name.find("Alicia",0)==string::npos) continue;
		if(rare=="N") continue;
		ok+=x;
	}
	_P("%.12lf\n",T*ok/tot);
	
}

J - ALPHAのならび

整数列Aが与えられる。この数列がK-sorted(i<j-kなら、A[i]

int N,K;
ll A[100000];

void solve() {
	int f,i,j,k,l,x,y;
	
	while(1) {
		cin>>N>>K;
		if(N==-1) return;
		FOR(i,N) cin>>A[i];
		
		
		ll ma=0;
		for(j=K+1;j<N;j++) {
			ma=max(ma,A[j-K-1]);
			if(A[j]<ma) {
				_P("No\n");
				goto out;
			}
		}
		_P("Yes\n");
		out:
		;
	}
}

まとめ

問題Eの「10枚に1枚~~」の下り、問題文をよく読まないと気づかないよ…。
おかげで何で答えが合わないかなかなかわからなかった。

広告を非表示にする