Codeforces Round #69 (Div. 1 Only)

Codeforces 参加記録

Result

SystemTest Failed / 766(1WA) / (3WA) / - / -

766点 251位
1901 -> 1829


A落とすとか、解法正しかったのに引き算忘れてたCとかあって勿体無い回。

A. Heroes

問題概要

3匹のボスを7人の勇者が、3パーティに分かれて倒す。
3匹のボスの経験値はそれぞれa,b,cであり、勇者には(倒したボスの経験値)/(パーティの人数)を切り捨てた経験値が入る。

パーティの分け方にはペア度があり、勇者pが勇者qのことを好きであり、p,qが同一のパーティのときにペア度は+1される。（qがpのことを好きなときはさらに+1)


もっとも多く経験値のもらえる勇者ともっとも少ない勇者の経験値の差を最小にし、
それでもタイならペア度を最大にするようなパーティの組み方における、
経験値の差の値およびペア度を出力せよ。

方針

3^7通り試す。
経験値の最大値が20億なのでいつものようにinfを1億とかやってたら落ちた。

ソースコード（修正版）
const int inf=(int)((1ll<<31)-1);
const double INF=1e12,EPS=1e-9;

void run()
{
	char *nm[]={"Anka", "Chapay", "Cleo", "Troll", "Dracul", "Snowy" ,"Hexadecimal"};
	map<string,int> id;
	rep(i,7)id[nm[i]]=i;
	
	int n,p[9][9]={}; cin>>n;
	rep(i,n){
		string a,b,c; cin>>a>>b>>c;
		p[id[a]][id[c]]=1;
	}
	int a,b,c,pw[9], mnd=inf,mxp; cin>>a>>b>>c;
	pw[0]=1; rep(i,8)pw[i+1]=pw[i]*3;
	
	rep(i,pw[7]){
		int tmp=i,t[7]={},cnt[3]={},pt=0;
		rep(j,7){
			t[j]=tmp%3; tmp/=3;
			cnt[t[j]]++;
		}
		
		if(cnt[0]==0||cnt[1]==0||cnt[2]==0)continue;
		rep(j,7)rep(k,7)if(t[j]==t[k])pt+=p[j][k];
		
		cnt[0]=a/cnt[0]; cnt[1]=b/cnt[1]; cnt[2]=c/cnt[2];
		int mx=max(max(abs(cnt[0]-cnt[1]),abs(cnt[0]-cnt[2])),abs(cnt[1]-cnt[2]));
		if(mx<mnd||mx==mnd&&mxp<pt)mnd=mx, mxp=pt;
	}
	cout<<mnd<<" "<<mxp<<endl;
}

B. Falling Anvils

問題概要

整数a,bが与えられる。
pが0以上a以下の実数、qが-b以上b以下の実数を等確率で取るとき、
二次方程式x^2 + √p x + q = 0が少なくともひとつの実数解を持つ確率を求めよ。

方針

判別式D=4p-q≧0を座標平面に書くと長方形からy=1/4xの上を切り取ったような形になる。
(切り取られてない部分の面積)/(長方形全体の面積)が求める答え。


ただしp==0またはq==0の場合はコーナーケースであるので注意しなければならない。
（ここで1ミス）

ソースコード
void run()
{
	int t; cin>>t;
	rep(i,t){
		double x,y; cin>>x>>y;
		
		if(x==0||y==0){
			if(y==0)cout<<1<<endl;
			else cout<<0.5<<endl;
			continue;
		}
		
		double s,S=2*x*y;
		
		if(4*y>=x){
			s=x*y+x*x/8;
		}
		else{
			s=S-(y*y*2);
		}
		printf("%.9f\n",s/S);
	}
}

C. Beavermuncher-0xFF

問題概要

無向木が与えられる。各頂点にはk[i](≧1)匹のビーバーがいる。
頂点sから出発して、
「エッジの先にビーバーがいれば、その頂点のビーバーを1匹だけ殺して、その頂点に移動する」ような殺戮兵器「Beavermuncher-0xFF」がある。


殺戮兵器は、動作が終わった後ふたたび頂点sに戻らなければならない。このとき
最大何匹のビーバーを殺せるか。

方針

酷い問題。木にりんごついてるとかにしろよｗ
部分木について最適な取り方をしたら、それより根元に近い部分には影響を与えないので、部分問題に分けて考えられる。


子の部分木のそれぞれを辿る。全て辿れない場合は収穫が多い順の子から辿れるだけ辿る。
すべて辿ってもその頂点のビーバーが余ってたら、子の頂点と往復してビーバーを殺せる。
これを再帰すればO(n).

ソースコード（修正版）
int n,k[111111],kk[111111],s;
vector<vi> e;

ll rec(int cur,int p){
	
	vector<pi> cnt;
	fr(i,e[cur])if(*i!=p)cnt.pb(mp(rec(*i,cur),*i));
	sort(all(cnt),greater<pi>());
	
	ll ret=1;
	kk[cur]--;
	
	rep(i,cnt.size()){
		if(kk[cur]==0)break;
		
		ret+=cnt[i].first+1;
		kk[cur]--;
	}
	rep(i,cnt.size()){
		ret+=min(kk[cnt[i].second],kk[cur])*2;
		kk[cur]-=min(kk[cnt[i].second],kk[cur]);
	}	
	return ret;
}
void run()
{
	cin>>n;
	rep(i,n)cin>>k[i],kk[i]=k[i];
	e.clear(); e.resize(n);
	
	rep(i,n-1){
		int a,b; cin>>a>>b; a--; b--;
		e[a].pb(b); e[b].pb(a);
	}
	cin>>s; s--;
	
	k[s]++; kk[s]++;
	cout<<rec(s,-1)-1<<endl;
}

D. Domino Carpet

問題

ドミノをしきつめたmxnの長方形の模様があたえられる。
無限個のドミノがあるとき、このような模様を作る作り方は何通りか。
ただしドミノの並べ方には以下の条件がある。

  • 重複や枠の外にはみ出るなどはダメ
  • ドミノの向きも一致しなければならない
  • ドミノの左半分が(x,y)にあるとき、他のすべてのドミノの左半分は(x+1,y)または(x-1,y)にあってはならない
方針

三番目の条件がかなりきつい制約になっている。
要するに左の列から埋めていくのに、1列まとめて敷き詰めるか、2列まとめて敷き詰めていくかしかない。

なので、i列目までの敷き詰め方をdp[i]とするようなdpができる。
1列の敷き詰め方は最大1通り（ドミノをそのまま置くだけ）
2列分の敷き詰め方は、さらにもう一度dpすることで求める。

||
↑こう縦に二つドミノを並べるか
--←横に1個置くしかないので

dp2[i]にi行目までの敷き詰め方を入れるようなdpをすればよい。


ただし、2列をすべて縦に敷き詰めた場合というのはちょうど2回だけ数えていることになるのでそこは調節する。

ソースコード（本番後AC）
int h,w;
int n[300][300],d[300][300];

void run()
{
	cin>>h>>w;
	string s,l[3]; cin>>s;
	rep(i,h){
		rep(j,3)cin>>l[j];
		rep(j,w){
			n[i][j]=0;
			rep(y,3)rep(x,3)n[i][j]+=l[y][4*j+x+1]=='O';
			if(n[i][j]==2||n[i][j]==3||n[i][j]==6){
				if(n[i][j]==6)d[i][j]=l[0][4*j+2]=='O';
				else d[i][j]=l[0][4*j+1]=='O';
			}
			else d[i][j]=-1;
		}
		cin>>s;
	}

	int dp[300]={};
	bool tateok[300]={};
	if(h%2==0)rep(x,w){
		tateok[x]=1;
		rep(i,h/2)if(d[i*2][x]==1||d[i*2+1][x]==1){
			tateok[x]=0; break;
		}
	}
	
	dp[0]=1;
	rep(x,w){
		if(tateok[x])(dp[x+1]+=dp[x])%=mod;
		if(x==w-1)break;
		
		int dd[300]={}; dd[0]=1;
		rep(i,h){
			//縦二つ並べられる
			if(i<h-1&&d[i][x]!=1&&d[i+1][x]!=1&&d[i][x+1]!=1&&d[i+1][x+1]!=1)
			(dd[i+2]+=dd[i])%=mod;
			
			//横ひとつ並べられる
			if(d[i][x]!=0&&d[i][x+1]!=0)
			(dd[i+1]+=dd[i])%=mod;
		}
		if(tateok[x+1]&&tateok[x])(dd[h]+=mod-1)%mod;
		
		dp[x+2]=(dp[x+2]+(ll)dp[x]*dd[h])%mod;
	}
	cout<<dp[w]<<endl;
}