PKU演習問メモ(9/16)

どれだけ問題解いても解いても解いても解いても
全然問題解く速度も上がらないし、解けない問題も解けるようにならない。

もう嫌。

No.	問題名	問題の種類および解法	難易度
3067	Japan	二部グラフの辺の交点・Fenwick Tree	★★★★☆
2859	A rectangle	長方形の検出	★★☆☆☆
2846	The Bank of Kalii	日付計算	★★☆☆☆
2724	Purifying Machine	二部グラフの最小辺カバー	★★★★☆
1691	Painting A Board	幾何・グラフ・探索	★★★☆☆
1029	False coin	実装	★★★☆☆

3067 Japan

問題概要

解法

ついにねんがんのFenwick Tree（Binary Indexed Tree）をつかったぞ

ソースコード

int n,m,k;
pi e[1000100];
ll bit[1001];

ll sum(int i)
{
	ll s=0;
	for(;i>0;i-=i&-i)s+=bit[i];
	return s;
}
void add(int i,int x)
{
	for(;i<=m;i+=i&-i)bit[i]+=x;
}
int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS)
	{
		scanf("%d%d%d",&n,&m,&k);
		rep(i,m+1)bit[i]=0;
		rep(i,k)scanf("%d%d",&e[i].first,&e[i].second);
		sort(e,e+k);
		ll cnt=0;
		rep(i,k)
		{
			cnt+=i-sum(e[i].second);
			add(e[i].second,1);
		}
		printf("Test case %d: %lld\n",cs+1,cnt);
	}
	return 0;
}

2859 rectangle

問題概要

解法

単なるSTLの二分探索で通ってしまった。

ソースコード

int n,w,h;
pi p[500000];

int main()
{
	scanf("%d%d%d",&n,&w,&h);
	rep(i,n)scanf("%d%d",&p[i].first,&p[i].second);
	sort(p,p+n);
	int ans=0;
	rep(i,n)
	{
		int x=p[i].first,y=p[i].second;
		if(binary_search(p,p+n,mp(x+w,y))&&
			binary_search(p,p+n,mp(x,y+h))&&
			binary_search(p,p+n,mp(x+w,y+h)))ans++;
	}
	printf("%d\n",ans);
	return 0;
}

2846 The Bank of Kalii

問題概要

解法

ソースコード

int day[]={31,28,31,30,31,30,31,31,30,31,30,31};
char in[20];

bool leap(int m,int y)
{
	return m==2&&(y%400==0||y%100!=0&&y%4==0);
}
int main()
{
	int CS; scanf("%d ",&CS);
	rep(cs,CS)
	{
		gets(in);
		for(int i=0;in[i];i++)if(in[i]=='/')in[i]=' ';
		int m,d,y,M,D,tm,td,ty;
		sscanf(in,"%d%d%d%d%d",&m,&d,&y,&M,&D);
		
		if(m==M&&d==D)
		{
			printf("%d SAME DAY\n",cs+1); goto END;
		}
		tm=m; td=d; ty=y;
		rep(i,7)
		{
			td++;
			if(td>day[tm-1]+leap(tm,ty))
			{
				td=1,tm++;
				if(tm>12)ty++,tm=1;
			}
			if(tm==M&&td==D)
			{
				printf("%d %d/%d/%d IS %d DAY%s AFTER\n",cs+1,M,D,ty,i+1,i?"S":"");
				goto END;
			}
		}
		tm=m; td=d; ty=y;
		rep(i,7)
		{
			td--;
			if(td<1)
			{
				tm--;
				if(tm<1)tm=12,ty--;
				td=day[tm-1]+leap(tm,ty);
			}
			if(tm==M&&td==D)
			{
				printf("%d %d/%d/%d IS %d DAY%s PRIOR\n",cs+1,M,D,ty,i+1,i?"S":"");
				goto END;
			}
		}
		printf("%d OUT OF RANGE\n",cs+1);
		END:;
	}
	return 0;
}

2724 Purifying Machine

問題概要

解法

機械に与える命令は、全て*の入ったものに置き換えてよい。
なぜなら、*が入った命令が使えない場合（片方が汚染されてないチーズの場合）はそこを0,1に適切に置き換えればよいし、0,1のいずれにも置き換えることの出来ない場合はその命令は不要だからである。

という訳で必要な*の入りの命令の最小の数を考える。

さて、するとこの問題は以下のようなチーズのグラフの最大辺カバーに帰着させることができる。
チーズの番号をグラフの頂点にして、*入りの一つの命令で一緒に清掃できるチーズ同士を辺で結ぶ。
更に、このグラフは二部グラフである。
なぜなら辺を一つまたぐと、チーズの番号を二進数で表した時の1の個数の偶奇が入れ替わるからである。

二部グラフの最小辺カバーは二部グラフの最大マッチングにより解けばよい。

ソースコード

int n,m,p[1024];
bool infec[1024],v[1024];
char in[11];

int BIT(int b)
{
	int ret=0;
	for(;b;b&=b-1)ret++;
	return ret;
}
bool match(int s)
{
	if(s<0)return 1;
	rep(i,n)if(infec[s^1<<i]&&!v[s^1<<i])
	{
		v[s^1<<i]=1;
		if(match(p[s^1<<i]))return p[s]=s^1<<i,p[s^1<<i]=s,1;
	}
	return 0;
}
int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		rep(i,1<<n)infec[i]=0,p[i]=-1;
		
		rep(i,m)
		{
			scanf("%s",in);
			int st=0;
			for(;in[st];st++)if(in[st]=='*')break;
			rep(k,2)
			{
				in[st]='0'+k;
				int t=0; rep(j,n)t*=2,t+=in[j]-'0';
				infec[t]=1;
			}
		}
		int tot=0,cnt=0;
		rep(i,1<<n)if(infec[i])
		{
			tot++;
			if(BIT(i)%2)continue;
			rep(j,1<<n)v[j]=0;
			if(match(i))cnt++;
		}
		printf("%d\n",tot-cnt);
	}
	return 0;
}

1691 Painting A Board

問題概要

解法

長方形の座標の接触の判定云々が面倒なので、それらを最初に済ませておく。
すなわち、ある板を塗る前に、塗らねばならない板の関係をグラフにする。

そして、そのグラフを深さ優先探索で次のように探索していく。

• 現在のブラシで塗れる長方形があればそれらを全て塗る
• 無いなら、ブラシの持ち替え方を全て試す。（ただし、持ち替えても塗る長方形が無いようなブラシは持ち替える必要はなし）

長方形の一辺が接するという判定は以下のようにすればよい。

abs(X[i]+x[i]-X[j]-x[j])<(X[i]-x[i]+X[j]-x[j])

これは以下のような考えによる。（あとでかく）

ソースコード

int n,cl[15];
bool e[15][15],root[15];
bool v[15];

int dfs(int fin,int bru,int cost)
{
	if(fin==n)return cost;
	int goodbrush[15],nul[15],gb=0,nutta=0;
	rep(i,n)if(!v[i])
	{
		if(!root[i])rep(j,n)if(!v[j]&&e[i][j])goto FAIL;
		
		if(cl[i]==bru)nul[nutta++]=i;
		else goodbrush[gb++]=cl[i];
		FAIL:;
	}
	int ret=inf;
	if(nutta==0)rep(i,gb)ret=min(ret,dfs(fin,goodbrush[i],cost+1));
	else
	{
		rep(i,nutta)v[nul[i]]=1;
		ret=min(ret,dfs(fin+nutta,bru,cost));
		rep(i,nutta)v[nul[i]]=0;
	}
	return ret;
}
int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d",&n);
		int x[15],y[15],X[15],Y[15];
		rep(i,n)scanf("%d%d%d%d%d",y+i,x+i,Y+i,X+i,cl+i);
		rep(i,n)rep(j,n)
		e[i][j]=y[i]==Y[j]&&abs(X[i]+x[i]-X[j]-x[j])<(X[i]-x[i]+X[j]-x[j]);
		
		rep(i,n)
		{
			root[i]=1; e[i][i]=0;
			rep(j,n)if(e[i][j])root[i]=0;
		}
		printf("%d\n",dfs(0,-1,0));
	}
	return 0;
}

1029 False coin

問題概要

解法

偽物のコインは、その重さまでは確定する必要はないらしい。
すなわち、

3 1
1 1 2
<

のようなケースでは、偽物のコインは3であるが重いか軽いかは解らない。
が、これに対する正しい答えは3である。

hev[i],lig[i]に、i番目のコインがそれぞれ「重い可能性がある」、「軽い可能性がある」というフラグを入れておく。
天秤の結果に対して次のようなことが解る。

釣り合った

皿に乗っていたコインは「重い可能性」も「軽い可能性」もなくなる。

傾いた

軽い皿に乗っていたコインは「重い可能性」がなくなり、重い皿に乗っていたコインは「軽い可能性」がなくなる。更に、皿に乗っていなかったコインは全て本物である。

これらを使って可能性を消していく。

ソースコード

int n,k,t[1000];
bool hev[1000],lig[1000];

int main()
{
	scanf("%d%d",&n,&k);
	rep(i,n)hev[i]=lig[i]=1;
	rep(i,k)
	{
		int p; char c;
		scanf("%d",&p);
		rep(j,2*p)scanf("%d",t+j),t[j]--;
		scanf(" %c",&c);
		
		if(c=='=')rep(j,2*p)hev[t[j]]=lig[t[j]]=0;
		else 
		{
			if(c=='>')rotate(t,t+p,t+2*p);
			
			rep(i,p)hev[t[i]]=0;
			rep(i,p)lig[t[i+p]]=0;
			
			bool f[1000]={0};
			rep(j,2*p)f[t[j]]=1;
			rep(j,n)if(!f[j])hev[j]=lig[j]=0;
		}
	}
	int ans=-1;
	rep(i,n)if(hev[i]||lig[i])
	{
		if(ans==-1)ans=i;
		else ans=-2;
	}
	printf("%d\n",max(0,ans+1));
	return 0;
}