PKU演習問メモ(4/10)

No.	Title	分類・解法	主観的難易度
1922	Ride to School	Straight forward	★☆☆☆☆
1949	Chores	Memoization	★★☆☆☆
1964	City Game	Dynamic programming	★★★☆☆
2242	The Circumference of the Circle	Math, Geometry	★☆☆☆☆
3425	Customer support	Straight forward	★☆☆☆☆
3744	Scout YYF I	Probability, Fast powering	★★★☆☆
2649	Factovisors	Simple Math	★★☆☆☆

主観的難易度なる項目を作ってみたので解きやすい問題or骨のある問題などを探している方はご活用下さい。

• 目安

★☆☆☆☆

初級向け。
簡単な数学系や、実装系の難しくない問題。

★★☆☆☆

初級向け。
動的計画法、探索などの簡単な問題、少し考察の必要な問題。

★★★☆☆

中級向け。
有名アルゴリズムや数学的考察の必要な問題。

★★★★☆

中級向け。
有名アルゴリズムの組み合わせや考察が必要な問題など。

あんまり骨のある問題は僕が解けないのだけど……レベルアップせねばorz
頑張ってるんだけど、全然難しい問題解けるようにならないんだよねえ。努力が足りない……のだといいなあ。

以下問題概要、ソースコードなど。

1922 Ride to School

問題概要

次のような戦略で学校へ行く。

• 出発地点で同時に出発する人が居ない場合他の出発する人を待つ
• その人と同じ速度で学校へ向かう
• 途中、より速い人に抜かされた場合その人と同じ速度で学校へ向かう

他の人の出発時刻と速度が与えられたとき（全員出発地点は同じ）学校へ着く時間を求めよ。

解法

出発時刻が自分と同じかそれより遅い人の中で、一番早く学校につく人と同時につく。

1949 Chores

問題概要

n種類の雑用があり、i番目の雑用をするには、1からi-1番目のうち、それぞれ決まった雑用を事前に済ませなければならない。
それぞれの雑用にかかる時間と、事前に済ませておかなければならない雑用のリストが与えられた時、全ての雑用を最も早く終わらせるのにかかる時間を求めよ。

解法

i番目の雑用が終わる時刻をfin[i]などとして覚えておくことで、下のコードのように解ける。（解説になってないか……）

ソースコード

int n;
int fin[10000];

int main()
{
	scanf("%d",&n);
	rep(i,n)
	{
		int t,m,k,mx=0; scanf("%d%d",&t,&m);
		rep(j,m)
		{
			scanf("%d",&k);
			mx=max(mx,fin[k-1]);
		}
		fin[i]=mx+t;
	}
	cout<<*max_element(fin,fin+n)<<endl;
	
	return 0;
}

1964 City Game

問題概要

nxm（n,m≦1000）マスのグリットで表される町がある。この町の建物が建っていない部分に長方形の形に新しい建物を１つ建てたい。建てることのできる建物の（日本語おかしい？）最大の面積はいくらか。

解法

サイズが大きいのでO(nm)やO(nmlog nm)程度のアルゴリズムを使う必要がある。
（普通に実装するとO(n^2m^2)になることに注意）
O(nm)で長方形を見つける動的計画法のアルゴリズムが存在する。
http://algorithms.blog55.fc2.com/blog-entry-133.html
↑神解説

ソースコード

int h,w;
char city[1000][1000];
int hist[1000][1000];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d",&h,&w);
		rep(i,h)rep(j,w)scanf(" %c",city[i]+j);
		
		rep(i,w)hist[0][i]=city[0][i]=='F';
		for(int i=1;i<h;i++)rep(j,w)hist[i][j]=city[i][j]=='F'?hist[i-1][j]+1:0;
		
		int ans=0;
		rep(i,h)
		{
			stack<pi> S;
			rep(j,w)
			{
				if(S.empty()||S.top().second<hist[i][j])
					S.push(mp(j,hist[i][j]));
				else if(S.top().second>hist[i][j])
				{
					int left=j;
					while(!S.empty()&&S.top().second>hist[i][j])
					{
						left=S.top().first;
						ans=max(ans,(j-left)*S.top().second);
						S.pop();
					}
					S.push(mp(left,hist[i][j]));
				}
			}
			while(!S.empty())
				ans=max(ans,(w-S.top().first)*S.top().second),S.pop();
		}
		cout<<ans*3<<endl;
	}
	return 0;
}

2242 The Circumference of the Circle

問題概要

座標平面上の一直線上にない異なる3点が与えられるとき、3点を通るような円の周長を求めよ。

解法

正弦定理+余弦定理。忘れた方は高校時代の数1Aだか2Bだかの教科書などを参考に。

最初やった時サンプル合ってたのにどうしてWAになったのだろう。
精度の問題？とか思ってlong doubleも使ったのだけど……

ソースコード

const double PI=3.141592653589793;

double d2(double x,double y)
{
	return x*x+y*y;
}

int main()
{
	double x1,y1,x2,y2,x3,y3;
	while(cin>>x1>>y1>>x2>>y2>>x3>>y3)
	{
		double a2=d2(x2-x3,y2-y3),b2=d2(x1-x3,y1-y3),c2=d2(x1-x2,y1-y2);
		double cosA=(b2+c2-a2)/(2*sqrt(b2*c2));
		
		double R=sqrt(a2)/sqrt(1-cosA*cosA);
		printf("%.2f\n",R*PI);
	}
	return 0;
}

とりあえずこれはAccepted.
最初のは円周率の値をatan(1.0)*4にしたのがまずかったのだろうか？謎。

3425 Customer support

問題概要

サポートセンターの利用ログが与えられるので、利用料金を算出せよ。
利用料金は以下にしたがって決められる。

質問に回答する

$10

正しく質問に回答する

$20

説明をつけて正しく質問に回答する

$40

正しく質問に回答したが、同じ質問をされたことがある

以前に同じ質問に正しく答えた回数1回につき+$10

解法

問題文の場合分けが少し曖昧な気もするが脳内で補完して解く。
正しく回答したか、間違った回答をしたかで場合わけすると良い。以前に正しく答えた質問は、質問番号が100万以下なので100万の配列に入れておくなどする。（処理時間を見るにmapでも大丈夫な気がする）

ソースコード

int ccnt[1000001];

int main()
{
	int n,ans=0; scanf("%d",&n);
	rep(i,n)
	{
		int q,a,x; scanf("%d%d%d",&q,&a,&x);
		
		if(!a)
		{
			ans+=10; continue;
		}
		
		ans+=x?40:20;
		ans+=ccnt[q]*10;
		
		ccnt[q]++;
	}
	cout<<ans<<endl;
	
	return 0;
}

3744 powering of matrices

問題概要

数直線で表される地雷原のうち、座標が1以上1億以下の整数であるような、N個（N≦10）のマスに地雷が埋まっている。
今座標1の点から地雷原をpの確率で1だけ、1-pの確率で2だけジャンプして進むとき、地雷原を突破できる確率を求めよ。

解法

座標xにある地雷を飛び越す確率は、x-1のマスに着き、そこで2のジャンプをする確率であるから、ちょうど点xにたどりつくような確率をpとxの式で一般的に表すことができればよいことがわかる。
問題の条件から、点xに丁度たどり着く確率はPx=p*Px-1+(1-p)*Px-2である。

漸化式が求まったので一般項が求まるが、座標の値が大きいので計算に工夫が必要である。
行列の繰り返し二乗法を用いることで計算量をO(log x)にすれば良い。
（繰り返し二乗法はフィボナッチ数列の一般項を高速に求める問題などで頻出）

ソースコード

struct M{
	double a,b,c,d;
	M(){}
	M(double a,double b,double c,double d):a(a),b(b),c(c),d(d){}
	M operator*(M &r)
	{
		return M(a*r.a+b*r.c,a*r.b+b*r.d,c*r.a+d*r.c,c*r.b+d*r.d);
	}
};

double prob(int d,double p)
{
	if(d==0)return 1;
	
	M Ppw[30],E(1,0,0,1);
	Ppw[0]=M(p,1-p,1,0);
	
	rep(i,29)Ppw[i+1]=Ppw[i]*Ppw[i];
	
	rep(i,30)if(d&1<<i)E=E*Ppw[i];
	return E.c*p+E.d;
}

int main()
{
	int n; double p;
	while(cin>>n>>p)
	{
		int x,prevx=1;
		double ans=1;
		rep(i,n)
		{
			cin>>x;
			if(x==prevx)ans=0;
			else ans*=prob(x-prevx-1,p)*(1-p);
			
			prevx=x+1;
		}
		printf("%.7f\n",ans);
	}
	return 0;
}

2649 Factovisors

問題概要

n!がmで割り切れるかどうかを判定せよ。
ただしaがbで割り切れるとはb*k=aとなるような整数kが存在することをいう。

解法

nの階乗は直接計算したくないので、mの素因数についてだけn!の中にどれだけ含まれるかを調べる。素数がnの階乗にいくつ含まれてるかは簡単な考察でわかる。（たぶん中学数学あたりでやるはず……）

nが0の場合やmが0の場合もあることに注意。

ソースコード

int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		bool ok=1;
		map<int,int> fct;
		int t=m;
		
		if(m==0)
		{
			ok=0;
			goto END;
		}
		if(n==0)
		{
			if(m>1)ok=0;
			goto END;
		}
		
		for(int i=2;i*i<=t;i++)
		{
			int cnt=0;
			while(t%i==0)t/=i,cnt++;
			if(cnt)fct[i]=cnt;
		}
		if(t>1)fct[t]=1;
		
		fr(i,fct)
		{
			int c=0;
			for(int t=n;t;t/=i->first)c+=t/i->first;
			if(c<i->second)
			{
				ok=0; break;
			}
		}
		
		END:
		if(ok)cout<<m<<" divides "<<n<<"!"<<endl;
		else cout<<m<<" does not divide "<<n<<"!"<<endl;
	}
	return 0;
}