PKU演習問メモ(4/19)

PKU
No. Title 分類・解法 主観的難易度
3055 Digital Friends 実装問題 ★★☆☆☆
1887 Testing the CATCHER 動的計画法 ★★☆☆☆

以下問題概要解法などなど

3055 Digital Friends

問題概要

２数x,yが同じ種類の数字から構成されるとき、これらを"friends"であると定義する。
この数のうち連続する2つの桁の数字を一カ所だけ+1,-1したものが"friends"であるとき"almost friends"であると定義する。ただし数の先頭が０になってはならない。


このとき、与えられた数がfriends、almost friednsあるいはそのどちらでもないかを判定せよ。

解法

数字の変更の仕方は高々(xの桁数+yの桁数）*2通りしかないため総当たりで調べれば良い。
ただしfriendsであるかの判定をナイーブにやるとTLEになるため、（というか単に僕がバグを出した可能性大なのだが）x,yに0-9の数字がいくつずつ出現するかをあらかじめ数えておいてやるとよい。

ソースコード
int cmp(int *c1,int *c2){
  int d=0;
  rep(i,10)if((!!c1[i])^(!!c2[i]))d++;
  return d;
}
bool solve(int *x,int *c1,int *c2,int l1){
  rep(i,l1-1)for(int d=-1;d<=1;d+=2){
    if(x[i]+d<0||x[i]+d>9||x[i+1]-d<0||x[i+1]-d>9)continue;
    if(i==0&&x[i]+d==0)continue;

    c1[x[i]]--,c1[x[i]+d]++,c1[x[i+1]]--,c1[x[i+1]-d]++;
    if(cmp(c1,c2)==0)return 1;
    c1[x[i]]++,c1[x[i]+d]--,c1[x[i+1]]++,c1[x[i+1]-d]--;
  }
  return 0;
}

int main()
{
  int n; scanf("%d",&n);
  while(n--){
    char xs[110],ys[110];
    scanf(" %s %s",xs,ys);
    int l1=strlen(xs),l2=strlen(ys);
    
    int xn[110],yn[110],c1[10]={0},c2[10]={0};
    rep(i,l1)xn[i]=xs[i]-'0',c1[xn[i]]++;
    rep(i,l2)yn[i]=ys[i]-'0',c2[yn[i]]++;
    
    int d=cmp(c1,c2);
    if(d==0){
      cout<<"friends"<<endl; continue;
    }else if(d>4){
      cout<<"nothing"<<endl; continue;
    }
    bool f=solve(xn,c1,c2,l1)||solve(yn,c2,c1,l2);
    cout<<(f?"almost friends":"nothing")<<endl;
  }
  return 0;
}

1887 Testing the CATCHER

問題概要

次のような性質をもつミサイル防衛装置がある。

  • 防衛装置が初めて破壊するミサイルはどんなものでもよい。
  • 防衛装置が二回目以降破壊できるミサイルは、前のミサイルと同じ大きさか、前のミサイルよりも小さいミサイルである。

飛んでくるミサイルの大きさが与えられた時、このミサイル防衛装置が破壊できる最大のミサイルの個数を求めよ。

解法

要するに、数列a[n]の単調非増加部分列を求めよという問題なので典型的な動的計画法を利用する問題。
i本目のミサイルまでで、破壊する本数の最適解をdp[i]本とおけば、dp[i+1]はdp[0]からdp[i]のうち、ミサイルがi本目よりも小さくないものの最大値をdp[j]とすればdp[j]+1である。

ソースコード
int n,h[50000];
int dp[50000];

int main()
{
	int cs=1;
	while(cin>>h[n++],~h[0])
	{
		while(cin>>h[n],~h[n])n++;
		fill(dp,dp+n,1);
		
		rep(i,n)rep(j,i)if(h[j]>=h[i])dp[i]=max(dp[i],dp[j]+1);
		
		int ans=*max_element(dp,dp+n);
		cout<<"Test #"<<cs++<<":"<<endl<<
"  maximum possible interceptions: "<<ans<<endl<<endl;
		
		n=0;
	}
	return 0;
}