PKU演習問メモ(8/20)

No. 問題名 問題の種類および解法 難易度
1970 The Game 実装 ★★☆☆☆
1939 Diplomatic License 幾何 ★☆☆☆☆
1962 Corporative Network Union-Find(のやや応用) ★★★★☆
1976 A Mini Locomotive 動的計画法 ★★☆☆☆
1975 Median Weight Bead ワーシャルフロイド ★★☆☆☆

1970 The Game

問題概要

19*19の碁盤で行われている五目並べの盤面が与えられる。
白の勝ちか、黒の勝ちか、引き分けかを判定せよ。
勝ちの条件は連続して石が5個揃っていることである。ただし石が連続して6個以上並んでいてはならない。


白と黒の両方が同時に勝っている場合は与えられないとしてよい。

解法

ループにより調べると楽……なはずなんだけど落とし穴が多かった。
(解法の説明になってない。もう疲れたので許して……orz)

ソースコード
int s[20][20];

#define ck(a,b) (0<=(a)&&(a)<19&&0<=(b)&&(b)<19)

bool win(int y,int x)
{
	for(int dy=1;dy>-2;dy--)rep(dx,2)if(dy||dx)
	{
		bool ok=1;
		rep(i,4)
		{
			int ny=y+dy*(i+1),nx=x+dx*(i+1);
			if(!ck(ny,nx)||s[ny][nx]!=s[y][x])
			{
				ok=0; break;
			}
		}
		if(ck(y+dy*5,x+dx*5)&&s[y][x]==s[y+dy*5][x+dx*5]||
			ck(y-dy,x-dx)&&s[y][x]==s[y-dy][x-dx])ok=0;
		
		if(ok)return 1;
	}
	return 0;
}

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		rep(i,19)rep(j,19)scanf("%d",s[i]+j);
		
		int winner=0,y,x;
		rep(i,19)rep(j,19)if(s[i][j])if(win(i,j))
		{
			winner=s[i][j];
			y=i,x=j; goto END;
		}
		END:printf("%d\n",winner);
		if(winner)printf("%d %d\n",y+1,x+1);
	}
	return 0;
}

1939 Diplomatic License

問題概要

n点からなる多角形が与えられる。
それらの中点を結んだ多角形を出力せよ。

解法

中点を出力するだけなのだが、どうもdoubleでX,Yを入力しないとWAになる?

ソースコード

言語選択をC++しないとフォーマット指定子の関係でWA。
あ、ちなみに普段はG++.

int n;
double X[10000],Y[10000];

int main()
{
	while(~scanf("%d",&n))
	{
		
		rep(i,n)scanf("%lf%lf",X+i,Y+i);
		printf("%d",n);
		rep(i,n)
		{
			double x=X[i]/2.0+X[(i+1)%n]/2.0, y=Y[i]/2.0+Y[(i+1)%n]/2.0;
			printf(" %.6lf %.6lf",x,y);
		}
		puts("");
	}
	
	return 0;
}

1962 Corporative Network

問題概要

n個のばらばらなネットワークがある。これに対して以下のクエリを処理せよ。

I A
Aの、Aの属するネットワークのサーバまでの距離を出力する
E I J
(ただしIはサーバで、Jはサーバとは限らない)IをJへつなげる。合体後のネットワークのサーバはJのサーバで、IからJへの距離はabs(I-J)%1000.
O
ケース終了

n≦20000以下とする。

解法

Union-Find木的なものを作る。p[x]をノードxの根、len[x]をその根までの距離とする。
p[x]がきちんと根を指していたら、根までの長さはlen[x]であり、そうでなかったら根へ木を辿りながらlenにそこまでの長さを足していく。


和を算出し終えた後、xの根をつなぎかえる(Union-FindのUnion)が、その時にlen[x]も同時に更新する。

ソースコード
int n;
int len[20000],p[20000];

int root(int x)
{
	if(x==p[x])return x;
	return p[x]=root(p[x]);
}
int rec(int x)
{
	if(p[p[x]]==p[x])return len[x];
	
	len[x]+=rec(p[x]);
	int ret=len[x]; p[x]=root(p[x]);
	
	return ret;
}

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d",&n);
		rep(i,n)len[i]=0,p[i]=i;
		
		char c; int a,b;
		while(scanf(" %c",&c),c!='O')
		{
			scanf("%d",&a);
			if(c=='E')printf("%d\n",rec(a-1));
			else
			{
				scanf("%d",&b); a--; b--;
				p[a]=b; len[a]+=abs(a-b)%1000;
			}
		}
	}
	return 0;
}

1976 A Mini Locomotive

問題概要

n個の客車を3つの小さな機関車で牽きたい。
小さな機関車は、客車の連蔵するちょうどlen両の客車を牽ける。


それぞれの客車に載っている乗客の数が与えられるとき、小さな機関車が移動させることのできる最大の乗客の数を求めよ。
n≤50000を満たす。

解法

動的計画法による。
dp[i][j]に先頭からi両目までの客車で、機関車をj個使って運べる乗客の最大の人数を持っておくと、漸化式が立つ。


ある車両を先頭にlen両の客車にの乗客の数はあらかじめ計算しておくと計算が効率化できる。
(工夫の必要はないみたい)

ソースコード
int n,pas[50000],len;
int sum[50000],dp[50001][4];


int main()
{
  int cs; scanf("%d",&cs);
  while(cs--){
    scanf("%d",&n);
    rep(i,n)scanf("%d",pas+i);
    scanf("%d",&len);

    sum[0]=accumulate(pas,pas+len,0);
    for(int i=1;i+len<=n;i++)sum[i]=sum[i-1]-pas[i-1]+pas[i+len-1];

    rep(i,n+1)rep(j,4)dp[i][j]=0;
    rep(i,n){
      rep(j,4){
	dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
	if(j<3&&i+len<=n)dp[i+len][j+1]=max(dp[i+len][j+1],dp[i][j]+sum[i]);
      }
    }
    int ans=0;
    rep(j,4)ans=max(ans,dp[n][j]);
    printf("%d\n",ans);
  }
  return 0;
}

1975 Median Weight Bead

問題概要

n個見た目の同じで重さのそれぞれ異なるビーズがある。
これらの重さの関係(aはbより重い)がm個与えられる。このとき、重さが中央値となり得ないビーズの数を求めよ。


n≤99かつnは奇数とする。

解法

ビーズの重さの大小関係からグラフを作り、ワーシャルフロイドする。
その後、自分より重いビーズまたは軽いビーズがn/2個よりも多いものをカウントする。

ソースコード
int n,m;
int d[99][99];

int main()
{
  int cs; scanf("%d",&cs);
  while(cs--){
    scanf("%d%d",&n,&m);
    rep(i,n)rep(j,n)d[i][j]=1;
    rep(i,m){
      int a,b; scanf("%d%d",&a,&b);
      d[a-1][b-1]=0;
    }
    rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    int ans=0;
    rep(i,n){
      int c1=0,c2=0;
      rep(j,n){
	if(d[i][j]==0)c1++;
	if(d[j][i]==0)c2++;
      }
      if(c1>n/2||c2>n/2)ans++;
    }
    printf("%d\n",ans);
  }
  return 0;
}