PKU演習問メモ(6/15) - simezi

No.	問題名	問題の種類および解法	難易度
3041	Asteroids	二部グラフの最小点カバー	★★★☆☆
2975	Nim	ゲーム	★★☆☆☆
2917	Diophantus of Alexandria	不定方程式の解の個数	★★☆☆☆

3041 Asteroids

問題概要

nxnのグリッドの中にk個の石があり、それぞれの座標が与えられる。
今、任意の1列のもしくは1行の石を全て消す操作が何回でも行えるとき、選択する列と行の個数の和を最小にして全ての石を消したい。そのような最小値を求めよ。

n≦500,k≦10000である。

解法

下のような例があるため、石が多い行、または列を選んでいくような解法は間違い。

XXX......
X..XX....
X....XX..
X......XX
.........
.........
.........
.........
.........

次のような二部グラフを考えたら上手くいった。

列に対応するn個のノードを赤、行に対応するn個のノードを青にする
(x,y)の座標に石があるとき、赤のx番目のノードと青のy番目のノードをエッジで結ぶ

すると、「石を消す列または行を選ぶ」操作は、「エッジの少なくともどちらかのノードを選ぶ」操作に対応することがわかる。
石を消す列または行の数を最小にしたいのだから、この二部グラフの最小点カバーを求めればそれが求まることがわかる。

ソースコード

int n,k;
vi e[1000];
bool v[1000]; int p[1000];

bool match(int s)
{
	if(s<0)return 1;
	fr(it,e[s])if(!v[*it])
	{
		v[*it]=1;
		if(match(p[*it]))return p[s]=*it,p[*it]=s,1;
	}
	return 0;
}

int main()
{
	scanf("%d%d",&n,&k);
	rep(i,k)
	{
		int x,y; scanf("%d%d",&x,&y);
		x--; y+=500-1;
		e[x].pb(y),e[y].pb(x);
	}
	
	int ans=0;
	fill_n(p,1000,-1);
	rep(i,n)
	{
		fill_n(v,1000,0);
		if(match(i))ans++;
	}
	cout<<ans<<endl;
	
	return 0;
}

2917 Nim

問題概要

Nim（石取りゲーム）において"losing position"とはそこから相手が最善を尽くした場合、自分がどう手を選んでも勝てない状態のことをいい、"winning position"は逆に、次の相手の手番を"losing position"の状態で渡せることを言う。

Nimにおいて有名な定理として、各山の個数のxorをとった時に0になればその状態は"losing position"であることが知られている。

今、山の状態が与えられたとき、losing positionにするような石の取り除き方は何通りあるか。
山の数nは1000以下、各山の大きさk[i]は10^9以下である。

解法

xorを二度とると0になることを利用する。
すなわち、全体のxorを求めておき、それぞれの山について

一度その山の個数のxorを取り、xorを消す
新たなその山の個数として考えられるのは0からk[i]-1である
この中に残りのxorに等しいものがあれば、そのような数になるよう石を取ることでlosing positionにできる。

これを実装したのが以下のコード。

ソースコード

int main()
{
  int n;
  while(cin>>n,n){
    ll pile[1000],sum=0;
    rep(i,n)cin>>pile[i],sum^=pile[i];
    
    int ans=0;
    rep(i,n)if((sum^pile[i])<pile[i])ans++;
    cout<<ans<<endl;
  }
  return 0;
}

2917 iophantus of Alexandria

問題概要

n≤10^9なるnが与えられるとき、
1/x + 1/y = 1/nを満たす自然数の組（順序は考慮しない）の数を求めよ。

解法

x≤yとすると、xはn<x≤2*nでなくてはならないことはすぐわかる。
式変形してy=nx/(x-n)であるが、ここでx-n=tと置くと、0<t≤nかつ
y=n^2/t + nである。

yが整数になるのはn^2/tが整数になるときであるので、0<p≤nを満たすようなn^2の約数の個数を求めればそれが解である。
n^2の約数の個数は素因数分解により求められる。このうち0<p≤nの個数aは、
「n^2の約数においてn以外のもの」にはn^2/pとpに一対一の対応があることから(a+1)/2の式で求められる。

ソースコード

int main()
{
  int CS,cs; cin>>CS;
  rep(cs,CS){
    cout<<"Scenario #"<<cs+1<<":"<<endl;
    int n,cnt[40]={0},nc=0; cin>>n;
    for(int i=2;i*i<=n;i++)if(n%i==0){
	while(n%i==0)cnt[nc]++,n/=i;
	nc++;
      }
    if(n>1)cnt[nc++]=1;

    ll ans=1;
    rep(i,nc)ans*=1+cnt[i]*2;
    ans++; ans/=2;
    cout<<ans<<endl<<endl;
  }
  return 0;
}