PKU演習問メモ(6/25)

No.	問題名	問題の種類および解法	難易度
2106	Boolean Expressions	構文解析	★★☆☆☆
2546	Circular Area	円の交わりの面積	★★☆☆☆
2945	Find the Clones	文字列のカウント	★★☆☆☆

2106 Boolean Expressions

問題概要

( V | V ) & F & ( F | V )

のように表される式の真偽値を求めよ。Vは真、Fは偽を表し、文字と文字の間には任意の個数の空白が入りうる。
演算子の優先順位の高い低いはない。また、否定の演算子!も式中に出現しうる。

解法

問題文適当じゃないのこれ。。。
サンプルが結構しっかりしてるからいいけど。
とりあえず二項演算子&,|は左結合、否定演算子の優先順位は最高、としてコードを書いたら上手くいった。

ソースコード

int len;
string str,tmp;

char cneg(char v)
{
	return v=='V'?'F':'V';
}
char cor(char a,char b)
{
	return a=='V'||b=='V'?'V':'F';
}
char cand(char a,char b)
{
	return a=='V'&&b=='V'?'V':'F';
}

char eval(int s,int t)
{
	if(t==s+1)return str[s];
	int p=t-1,d=0;
	for(;p>=s;p--)
	{
		if(str[p]==')')d--;
		if(str[p]=='(')d++;
		if((str[p]=='&'||str[p]=='|')&&d==0)break;
	}
	if(p==s-1)
	{
		if(str[s]=='!')return cneg(eval(s+1,t));
		return eval(s+1,t-1);
	}
	char l=eval(s,p),r=eval(p+1,t);
	if(str[p]=='|')return cor(l,r);
	assert(str[p]=='&');
	return cand(l,r);
}
int main()
{
	int cs=0;
	while(getline(cin,tmp))
	{
		str.clear();
		fr(i,tmp)if(*i!=' ')str.pb(*i);
		len=str.size();
		
		cout<<"Expression "<<++cs<<": "<<eval(0,len)<<endl;
	}
	return 0;
}

2546 Circular Area

問題概要

二円の中心(x1,y1),(x2,y2)および半径r1,r2が与えられるとき、これらの交わりの面積を小数点以下三桁の精度求めよ。

解法

円が離れている場合（一点で接するようなものも含む）、片方が片方に入り込んでいる場合、異なる二点で円周が交わる場合で場合わけ。
最後の場合は、ヘロン公式を使う以下のような回答が更なる場合わけが不要で便利？

ソースコード

int main()
{
	double x1,y1,r1,x2,y2,r2,area;
	cin>>x1>>y1>>r1>>x2>>y2>>r2;
	
	double d=hypot(x1-x2,y1-y2);
	if(r1+r2<d+EPS)area=0;
	else if(d<abs(r1-r2)+EPS)
	{
		double r=min(r1,r2);
		area=r*r*atan(1.0)*4;
	}
	else
	{
		double A=acos((r2*r2+d*d-r1*r1)/(2*r2*d));
		double B=acos((r1*r1+d*d-r2*r2)/(2*r1*d));
		double s=(r1+r2+d)/2;
		area=r1*r1*B+r2*r2*A-2*sqrt(s*(s-r1)*(s-r2)*(s-d));
	}
	printf("%.3f\n",area);
	
	return 0;
}

2945 Find the Clones

問題概要

n人の遺伝子がそれぞれm文字の文字列で与えられる。
この中で遺伝子が全く同じクローン人間がいる。

• 1人もクローンが作られていない人の数
• 1人クローン人間が作られた人の数
• ……
• n-1人クローン人間が作られた人の数

を出力せよ。
n≤5000,m≤20であり、遺伝子の各文字は'A','G','C','T'のいずれかである。

解法

mapで各遺伝子の出現回数を数えればよい。
が、多分stringのままでやるとTLE.
遺伝子は20文字以下の4進数と見ることができるので、それをlong long型の整数に変換してからmapに放り込んで数え上げれば良い。

ソースコード

int main()
{
  char nm[256];
  nm['A']=0,nm['G']=1,nm['C']=2,nm['T']=3;

  int n,m;
  while(scanf("%d%d",&n,&m),n){
    map<ll,int> dist;
    char g[21]; ll t;
    rep(i,n){
      scanf("%s",g);
      t=0;
      rep(j,m)t*=4,t+=nm[g[j]];
      dist[t]++;
    }
    int ans[n]; fill_n(ans,n,0);
    fr(i,dist)ans[i->second-1]++;
    rep(i,n)printf("%d\n",ans[i]);
  }  
  return 0;
}