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

kmjp's blog

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

yukicoder : No.88 次はどっちだ、No.89 どんどんドーナツどーんといこう!、No.90 品物の並び替え

yukicoder openに参加。前半の早解きのおかげで上々の順位だが、Alice and Graphが解けなかったのが残念。
http://yukicoder.me/problems/148
http://yukicoder.me/problems/179
http://yukicoder.me/problems/209

No.88 次はどっちだ

オセロの盤面と、先手の名前が与えられる。
次の手番はどちらか。

石の数の偶奇を見れば、次の手番がどちらかわかる。

string P,S[10];
int num;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P;
	j=0;
	FOR(y,8) {
		cin>>S[y];
		FOR(x,8) j+=S[y][x]!='.';
	}
	if(j%2==0 ^ P=="oda" ^ 1) cout<<"oda"<<endl;
	else cout<<"yukiko"<<endl;
}

No.89 どんどんドーナツどーんといこう!

ドーナツの単位体積当たりのカロリーCと、ドーナツが2つの同心円に見える向きで見たときの内側と外側の円の半径Rin,Routが与えられる。
このドーナツの総カロリーを求めよ。

ヒント通りパップス・ギュルダンの定理を用いればよい。
断面積は((Rin-Rout)/2)^2*π、重心の回転距離は((Rin-Rout)/2)*2*πとなる。

int C,I,O;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>C>>I>>O;
	double pi=atan(1)*4;
	double han=(O-I)/2.0;
	double ret=((I+O)/2.0)*2*pi*(han*han*pi)*C;
	_P("%.12lf\n",ret);
	
}

No.90 品物の並び替え

0~(N-1)番のN個の商品を並べる。
item1[i]番の商品がitem2[i]番の商品の前にあると、score[i]点を得ることができる。
商品を並べ替えて得られる最高得点を求めよ。

Nが9以下と小さいので、next_permutationで総当たりすればよい。

int N,M;
int I[2][1000],S[1000];
int mat[100][100];
int V[10];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>I[0][i]>>I[1][i]>>S[i];
		mat[I[0][i]][I[1][i]]=S[i];
	}
	FOR(i,N) V[i]=i;
	
	int ma=0;
	do {
		int sc=0;
		
		FOR(x,N) FOR(y,x) sc+=mat[V[y]][V[x]];
		
		ma=max(ma,sc);
		
	} while(next_permutation(V,V+N));
	cout<<ma<<endl;
}

まとめ

このあたりはまだまだ余裕。

広告を非表示にする