PKU演習問メモ(9/1)

復活きたあああああ

解説は風呂にでも入った後で書く。←翌日になってようやく書き終えた

No.	問題名	問題の種類および解法	難易度
2654	Rock-Paper-Scissors Tournament	実装	★☆☆☆☆
2626	Chess	動的計画法or最小費用流	★★☆☆☆
2640	Playground	枝刈り付き探索	★★★☆☆
2661	Factstone Benchmark	対数	★★☆☆☆
2610	Dog & Gopher	幾何	★★☆☆☆
2632	Crashing Robots	シミュレーション	★★☆☆☆
2603	Brave balloonists	約数の個数	★★☆☆☆
1013	Counterfeit Dollar	探索	★★☆☆☆

2654 Rock-Paper-Scissors Tournament

問題概要

n人がじゃんけんの総当りの試合をk回行う（全体で試合はn*(n-1)/2*k回）
各人の出した手は全て与えられる。

勝率をw/(l+w)とするとき、（wは勝った回数、lは負けた回数で、あいこはどちらにも数えない）各人の勝率を出力せよ。
勝率が定義できない場合は"-"を出力せよ。

n≦100を満たす。

解法

じゃんけんの判定を行って勝ち数と負け数を数えればよい。

ソースコード

int n,k;
int win[101],lose[101];

int main()
{
	while(scanf("%d",&n),n)
	{
		scanf("%d",&k);
		rep(i,n+1)win[i]=lose[i]=0;
		
		rep(i,n*(n-1)/2*k)
		{
			int a,b; char h1[10],h2[10];
			scanf("%d%s%d%s",&a,h1,&b,h2);
			if(h1[0]==h2[0])continue;
			if(h1[0]=='r'&&h2[0]=='s'||h1[0]=='s'&&h2[0]=='p'
				||h1[0]=='p'&&h2[0]=='r')win[a]++,lose[b]++;
			else win[b]++,lose[a]++;
		}
		for(int i=1;i<=n;i++)
		{
			if(win[i]+lose[i]==0)puts("-");
			else printf("%.3f\n",win[i]/double(win[i]+lose[i]));
		}
		puts("");
	}
	return 0;
}

2626 Chess

問題概要

n人の中から30人のチェスチームを作る。
それぞれのプレイヤーの先手番での強さおよび後手番での強さが与えられる。

チームにおいて、先手を担当する人間、後手を担当する人間はそれぞれ15人で、途中で先手と後手の担当を入れ替えることはできない。

チーム全体の強さは各人の担当する手番での強さの和となる。
このとき、チーム全体の強さの最大値を求めよ。

n≦1000を満たす。

解法

動的計画法での解法、最小費用流を用いる解法の2通りが考えられた。
DPの場合、dp[i][j][k]にi人まで見て、先手番にj人、後手番にk人割り振ったときのチームの強さをもたせ、表を更新していく。

費用流の解法は、それぞれのプレイヤーと(先手番・後手番担当を表す2つのノード)とを容量1,コスト(プレイヤーのその手番での強さ*-1)の辺で結び、
先手番・後手番担当を表すノードと、シンクをそれぞれ容量15,コスト0の辺で結び、最小費用流を流す。

費用流で解いたらWAだったんだけど何でだろう。
［追記］費用流でもAC. Primal-Dual法はコストが負の辺があるとダメみたい（わかってない
それを回避するために辺のコストに適当に100とかの数字を足して一旦正にして、後で引いて帳尻を合わせる。

費用流使ったの初めて！これで次から費用流も解けるね！

ソースコード

int n,w[1000],b[1000];
int dp[2][16][16];

int main()
{
	while(~scanf("%d%d",w+n,b+n))n++;
	
	rep(i,16)rep(j,16)dp[0][i][j]=0;
	int cur=0,next=1;
	rep(i,n)
	{
		rep(j,16)rep(k,16)dp[next][j][k]=dp[cur][j][k];
		rep(j,16)rep(k,16)
		{
			if(j<15)dp[next][j+1][k]=max(dp[next][j+1][k],dp[cur][j][k]+w[i]);
			if(k<15)dp[next][j][k+1]=max(dp[next][j][k+1],dp[cur][j][k]+b[i]);
		}
		swap(cur,next);
	}
	printf("%d\n",dp[cur][15][15]);
	
	return 0;
}

spaghetti sourceの最小費用流のライブラリを用いた別解
ライブラリは微妙にいじってある。

struct Edge {
  int src, dst;
  Weight capacity,cost;
  Edge(int src, int dst, Weight capacity=0, Weight cost=0) :
    src(src), dst(dst), capacity(capacity), cost(cost) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.cost != f.cost ? e.cost > f.cost : // !!INVERSE!!
    e.capacity != f.capacity ? e.capacity > f.capacity :
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

#define RESIDUE(u,v) (capacity[u][v] - flow[u][v])
#define RCOST(u,v) (cost[u][v] + h[u] - h[v])
pair<Weight, Weight> minimumCostFlow(const Graph &g, int s, int t) {
  const int n = g.size();
  Matrix capacity(n, Array(n)), cost(n, Array(n)), flow(n, Array(n));
  rep(u,n) fr(e,g[u]) {
    capacity[e->src][e->dst] += e->capacity;
    cost[e->src][e->dst] += e->cost;
  }
  pair<Weight, Weight> total; // (cost, flow)
  vector<Weight> h(n);

  for (Weight F = inf; F > 0; ) { // residual flow
    vector<Weight> d(n, inf); d[s] = 0;
    vector<int> p(n, -1);
    priority_queue<Edge> Q; // "e < f" <=> "e.cost > f.cost"
    for (Q.push(Edge(-2, s)); !Q.empty(); ) {
      Edge e = Q.top(); Q.pop();
      if (p[e.dst] != -1) continue;
      p[e.dst] = e.src;
      fr(f, g[e.dst]) if (RESIDUE(f->src, f->dst) > 0) {
        if (d[f->dst] > d[f->src] + RCOST(f->src, f->dst)) {
          d[f->dst] = d[f->src] + RCOST(f->src, f->dst);
          Q.push( Edge(f->src, f->dst, 0, d[f->dst]) );
        }
      }
    }
    if (p[t] == -1) break;

    Weight f = F;
    for (int u = t; u != s; u = p[u])
      f = min(f, RESIDUE(p[u], u));
    for (int u = t; u != s; u = p[u]) {
      total.first += f * cost[p[u]][u];
      flow[p[u]][u] += f; flow[u][p[u]] -= f;
    }
    F -= f;
    total.second += f;
    rep(u, n) h[u] += d[u];
  }
  return total;
}
void addE(Graph &g,int src,int dst,Weight capacity,Weight cost)
{
	g[src].pb(Edge(src,dst,capacity,cost)); g[dst].pb(Edge(dst,src,0,-cost));
}

int main()
{
	int n=0,w[1000],b[1000];
	while(~scanf("%d%d",w+n,b+n))
	{
		w[n]=100-w[n]; b[n]=100-b[n];
		n++;
	}
	
	Graph g(n+4);
	rep(i,n)
	{
		addE(g,0,i+1,1,0);
		addE(g,i+1,n+1,1,w[i]);
		addE(g,i+1,n+2,1,b[i]);
	}
	addE(g,n+1,n+3,15,0); addE(g,n+2,n+3,15,0);
	
	pi ans=minimumCostFlow(g,0,n+3);
	printf("%d\n",3000-ans.first);
	
	return 0;
}

2640 Playground

問題概要

n個の半円の形をしたスチールの棒がある。
それぞれの長さが与えられるとき、弧の端と端をぴったりとくっつけ、輪を作ることが出来るかを答えよ。使わない弧があってもかまわない。

それぞれの弧の長さは小数であり、n≦20を満たす。

解法

半円の弧を、その両端を結ぶ線分の棒と考えてやる。
そして、三角不等式を満たすペアを探すよう深さ優先探索する。

枝刈りをしないとTLEだが、以下のような枝刈りをすれば30msくらいで通る。

• 三角形の辺の長さを限定する（a≦b≦cのようなものだけ考える）
• 残りの全ての棒を短い辺につないでもa+b≧cにならなかったらすぐに探索を打ち切る

ソースコード

int k;
double l[20];

bool dfs(int cur,double a,double b,double c)
{
	if(a>b||b>c)return 0;
	if(c>0&&a+b>=c)return 1;
	
	if(cur==k)return 0;
	
	double d=a+b-c;
	for(int i=cur;i<k;i++)d+=l[i];
	if(d<0)return 0; //brunch-cut
	
	if(
		dfs(cur+1,a+l[cur],b,c)||
		dfs(cur+1,a,b+l[cur],c)||
		dfs(cur+1,a,b,c+l[cur])||
		dfs(cur+1,a,b,c)
	)return 1;
	return 0;
}

int main()
{
	while(scanf("%d",&k),k)
	{
		rep(i,k)scanf("%lf",l+i);
		sort(l,l+k,greater<double>());
		puts(dfs(0,0,0,0)?"YES":"NO");
	}
	
	return 0;
}

2661 Factstone Benchmark

問題概要

Amtel社は2010年に128bitのCPUを発表した。CPUは10年毎にリリースされ、bitは10年毎に2倍になる。
（2020年は256bit,逆に2000年時点では64bit……）

CPUで表せる最大の整数の階乗n!としたとき、nをFactstone Benchmarkと呼ぶ。
年yが与えられたとき、その年でのCPUのFactstone Benchmarkを求めよ。

1960≦y≦2160を満たす。

解法

まず年度でのbitを求める。これはdouble型に収まる。
収まる整数は2^bit乗なので、それ以下となるn!を、logを取り探す。
すなわち、bit≦log n! / log 2を満たすnを、log kを順次足していき見つければよい。

long doubleを一応つけてみたけど不要っぽい。

ソースコード

int main()
{
	int n;
	while(scanf("%d",&n),n)
	{
		n/=10; n-=194;
		ld bit=pow(2,(ld)1.0*n)*log((ld)2.0);
		int ans=1;
		while(bit>0)bit-=log(1.0*++ans);
		
		printf("%d\n",ans-1);
	}
	return 0;
}

2610 Dog & Gopher

問題概要

犬とリスが一匹ずつおり、それぞれの初期座標が与えられる。
座標平面にはいくつかの穴があり、犬はリスを追いかけ、リスは穴に逃げる。
犬の速度はリスの速度の二倍である。

リスが犬から逃げて穴に先に入れるかを判定せよ。

解法

それぞれの穴について、リスからの距離と犬からの距離を求め、リスが犬より先につけるかを判定すればよい。

ソースコード

int main()
{
	double gx,gy,dx,dy,ax=INF,ay=INF,x,y;
	scanf("%lf%lf%lf%lf",&gx,&gy,&dx,&dy);
	
	while(~scanf("%lf%lf",&x,&y))
	{
		if(ax!=INF)continue;
		if(hypot(gx-x,gy-y)*2<=hypot(dx-x,dy-y))ax=x,ay=y;
	}
	if(ax==INF)puts("The gopher cannot escape.");
	else printf("The gopher can escape through the hole at (%.3f,%.3f).\n",
		ax,ay);
	
	return 0;
}

2632 Crashing Robots

問題概要

AxBのグリッドであらわされる部屋にn個のロボットがあり、それにm個の命令を出す。
命令は"ロボットの番号 方向 回数"の形式で与えられ、一つの命令が完全に実行され終えた後で次の命令が実行される。

グリッドにはロボットが最大一つしか入ることができず、同じグリッドにロボットが二つ入ろうとするとクラッシュする。また、ロボットは壁にぶつかる指示を出されてもクラッシュする。
m個の命令をクラッシュせず実行できるなら"OK"を、クラッシュするなら最初のクラッシュを出力せよ。

解法

シミュレートすればよい。
座標系がやっかいなので要注意。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int h,w,m,n;
int rx[100],ry[100],rd[100];
int r[100][100];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d%d%d",&w,&h,&n,&m);
		rep(i,h)rep(j,w)r[i][j]=-1;
		rep(i,n)
		{
			char d; scanf("%d%d %c",rx+i,ry+i,&d);
			ry[i]=h-ry[i]; rx[i]--;
			r[ry[i]][rx[i]]=i;
			rd[i]=d=='N'?0:d=='S'?2:d=='E'?3:1;
		}
		
		int crush=-1,target=-1;
		rep(i,m)
		{
			int no,rp; char ac;
			scanf("%d %c%d",&no,&ac,&rp); no--;
			
			if(crush!=-1)continue;
			
			if(ac=='F')
			{
				r[ry[no]][rx[no]]=-1;
				while(rp--)
				{
					ry[no]+=dy[rd[no]]; rx[no]+=dx[rd[no]];
					if(ry[no]<0||ry[no]>=h||rx[no]<0||rx[no]>=w)
					{
						crush=no; break;
					}
					if(r[ry[no]][rx[no]]!=-1)
					{
						crush=no; target=r[ry[no]][rx[no]]; break;
					}
				}
				r[ry[no]][rx[no]]=no;
			}
			else
			{
				rd[no]+=(ac=='L'?1:3)*rp;
				rd[no]%=4;
			}
		}
		if(crush==-1)puts("OK");
		else
		{
			printf("Robot %d crashes into ",crush+1);
			if(target==-1)puts("the wall");
			else printf("robot %d\n",target+1);
		}
	}
	return 0;
}

2603 Brave balloonists

問題概要

10個の自然数a1,a2,a3……,a10が与えられる。
積a1a2a3……a10の約数の個数の下一桁を求めよ。

解法

ある数のAの約数の個数を求めるには定石どおり素因数分解して
A=p1^q1 p2^p2……
とおけば(1+q1)*(1+q2)*……
である。これをmod10で出力すればよい。

ソースコード

int cnt[10000];

void calc(int a)
{
	for(int i=2;i*i<=a;i++)if(a%i==0)
	{
		int c=0;
		while(a%i==0)a/=i,c++;
		cnt[i]+=c;
	}
	if(a>1)cnt[a]++;
}

int main()
{
	int a;
	rep(i,10)scanf("%d",&a),calc(a);
	
	int ans=1;
	rep(i,10000)ans=ans*(cnt[i]+1)%10;
	printf("%d\n",ans);
	
	return 0;
}

1013 Counterfeit Dollar

問題概要

12個の見た目が同じコインの中に1つだけ重さの違う偽物のコインが混ざっている。
天秤を3回使ってそれらを量った結果が与えられるとき、偽物のコインを求めよ。

それぞれのコインは英大文字一文字A-Lで表され、天秤の測定結果は

ABCD EFGH even 

のように与えられる。

また、測定結果から偽物のコインが必ず一意に定まるとしてよい。

解法

偽物のコインはA-Lで重いor軽いの24通り。なのでそれらを全て、測定結果と矛盾しないか試せばよい。

気づいたら無駄にビット演算を使ってた。

ソースコード

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		int isl[3]={0},isr[3]={0},re[3]={0};
		rep(i,3)
		{
			char l[7],r[7],res[7];
			scanf("%s%s%s",l,r,res);
			
			for(int j=0;l[j];j++)isl[i]|=1<<l[j]-'A';
			for(int j=0;r[j];j++)isr[i]|=1<<r[j]-'A';
			if(res[0]=='u')re[i]=1;
			else if(res[0]=='d')re[i]=-1;
		}
		
		int ans=0,w;
		for(;ans<12;ans++)for(w=-1;w<2;w+=2)
		{
			rep(i,3)
			{
				int s=0;
				if(isl[i]&1<<ans)s+=w;
				if(isr[i]&1<<ans)s-=w;
				if(s!=re[i])goto FAIL;
			}
			goto END;
			FAIL:;
		}
		END:
		printf("%c is the counterfeit coin and it is %s.\n",
			ans+'A',w>0?"heavy":"light");
	}
	return 0;
}