PKU演習問メモ(8/14)

No. 問題名 問題の種類および解法 難易度
2440 DNA 動的計画法・周期性 ★★★☆☆
2348 Euclid's Game ゲーム ★★★☆☆
2407 Concert Hall Scheduling 動的計画法 ★★★☆☆
2313 Sequence 動的計画法 ★★★☆☆
2183 Bovine Math Geniuses ループ検出 ★★☆☆☆

2440 DNA

問題概要

DNAが0と1の列で表される生き物がいる。
DNAの中に"101"または"111"の文字が入っていると、抗ウィルス薬の影響を受ける。


長さLのDNAのうち、抗ウィルス薬の影響を受けないものの数を2005で割った余りを求めよ。
1≦L≦10^8とする。

解法

Lが大きいので単純にDPすると時間が間に合わない気がする。
求めるのは2005で割った余りなので、これはどこかでループしてくれそうな気がする。実際に1000くらいまで出力してみると、200でループすることがわかる。


よって200まではDPし、それ以上の数はL%200として求めればよい。

ソースコード
int dp[200][4],ans[200];

void gen()
{
	dp[0][0]=dp[0][1]=2; dp[0][2]=dp[0][3]=1;
	
	for(int i=1;i<200;i++)
	{
		rep(j,4)dp[i][j]=0;
		rep(j,4)rep(k,2)if(!(j==3&&k==1||j==1&&k==1))
		dp[i][k*2+(j>>1)]=(dp[i][k*2+(j>>1)]+dp[i-1][j])%2005;
	}
	rep(i,200)ans[i]=accumulate(dp[i],dp[i]+4,0)%2005;
}

int main()
{
	gen();
	
	int l; while(cin>>l)
	{
		l%=200; if(l==0)l=200;
		if(l<3)printf("%d\n",l==1?2:4);
		else printf("%d\n",ans[l-3]);
	}
	return 0;
}

2348 Euclid's Game

問題概要

二つの数A,Bを使い、二人がゲームをする。
プレイヤーはA,Bのうち大きいほうから小さいほうの倍数を(負にならないよう)好きに引くことができる。
これを繰り返し、先に0を作ったプレイヤーが勝ちとなる。


二つの数字が与えられたとき、お互いが最善を尽くした場合における勝者を求めよ。

解法

GCJで似たような問題が出たデジャヴ!


A>Bとしてよい。
A>2Bの場合、二つの数を

  • (A%B),Bとするか
  • (A%B+B),Bとするか選べる

(A%B+B),Bにされた相手は(A%B),Bにするしかないので、先手必勝と後手必勝を好きに入れ替えられることになる。すなわちA>2Bなら必勝。


2B>Aならば選択の余地はないので再帰

ソースコード
bool rec(ll a,ll b)
{
	if(b>a)swap(a,b);
	
	if(b==0)return 0;
	if(a%b==0)return 1;
	
	if(a>=2*b)return 1;
	return !rec(b,a%b);
}
int main()
{
	ll a,b;
	while(cin>>a>>b,a)
	{
		printf("%s",rec(a,b)?"Stan":"Ollie");
		puts(" wins");
	}
	return 0;
}

2407 Concert Hall Scheduling

問題概要

2つの同じ部屋のあるコンサートホールがある。
来年のコンサートホールの申し込みが
(利用開始日) (利用終了日) (支払い料金)
のリストで与えられる。


このとき、来年の可能な最大の収入を求めよ。
利用開始日、終了日のそれぞれは1以上365以下、かつ一つの申し込みは毎日同じ部屋を使えない場合は受け付けられないものとする。


申し込みの件数は1000件以下である。

解法

申し込みを開始日でソートしておけば、dp[i][j]に部屋1がi日目まで埋まっていて、部屋2がj日目まで埋まっているような状態での最大の収入をもたせ、表を更新していくDPができる。

dp[日][i][j]とするとTLEになってしまうので、(AOJはこれでも通った)
配列をなめる順序を工夫して二次元配列だけでDPする必要がある。


上位の時間は0MSとかなので、多分もっと効率の良い解法があるはず……orz
ひょっとしたらgreedyで解けるのかもしれない。

ソースコード
int n,s[MX],t[MX],p[MX];
pair<int,pi> in[MX];
int dp[366][366];

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)scanf("%d%d%d",&in[i].first,&in[i].second.first,&in[i].second.second);
		sort(in,in+n);
		rep(i,n)s[i]=in[i].first,t[i]=in[i].second.first,p[i]=in[i].second.second;
		
		rep(i,366)rep(j,366)dp[i][j]=0;
		
		rep(i,n)
		{
			for(int k=365;k>=0;k--)for(int j=s[i]-1;j>=0;j--)
			{
				dp[t[i]][k]=max(dp[t[i]][k],dp[j][k]+p[i]);
				dp[k][t[i]]=max(dp[k][t[i]],dp[k][j]+p[i]);
			}
		}
		int ans=0;
		rep(i,366)rep(j,366)ans=max(ans,dp[i][j]);
		printf("%d\n",ans);
	}
	return 0;
}

2313 Sequence

問題概要

n項の数列anが与えられる。
この数列に対してV=|ai-bi|の最小値を求めよ。


ただし-10000≦ai≦10000, n≦100を満たす。

解法

biとして用いる値の候補はaiのいずれかだけでよいことに気づけばO(n^3)の動的計画法ができる。

ソースコード
int n,a[100];
int dp[100][100];

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d",a+i);
	
	rep(i,n)dp[0][i]=abs(a[0]-a[i]);
	for(int i=1;i<n;i++)
	{
		rep(j,n)dp[i][j]=inf;
		rep(j,n)rep(k,n)
		dp[i][j]=min(dp[i][j],dp[i-1][k]+abs(a[k]-a[j])+abs(a[i]-a[j]));
	}
	int ans=inf;
	rep(i,n)ans=min(ans,dp[n-1][i]);
	printf("%d\n",ans);
	
	return 0;
}

2183 Bovine Math Geniuses

問題概要

6桁の数を、

  • 中央の4桁を取る
  • その4桁を二乗する
  • そこから下6桁を取り、新しい数とする

操作を繰り返したとき、ループがおこる。
何回目の操作で長さがいくつのループに入るかを求めよ。

解法

ソース参照。マップに入れていく。
中央の4桁は1万通りしかないので、1万ステップ以内に絶対にループする。

ソースコード
int main()
{
	int n; scanf("%d",&n);
	
	map<int,int> M; M[n]=0;
	for(int i=1;;i++)
	{
		n=n/10%10000; n=n*n%1000000;
		if(M.count(n))
		{
			printf("%d %d %d\n",n,i-M[n],i);
			break;
		}
		M[n]=i;
	}
	
	return 0;
}