PKU演習問メモ(4/24) - simezi

No.	Title	分類・解法	主観的難易度
2996	Help Me with the Game	実装問題	★★☆☆☆
2993	Emag eht htiw Em Pleh	実装問題	★☆☆☆☆
3044	City Skyline	データ構造	★★☆☆☆
2769	Reduced ID Numbers	整数問題	★★☆☆☆

以下問題概要解法ソースコード

2996 Help Me with the Game

問題概要

チェスの盤面が与えられる。この盤面を読み取り、各プレイヤーの各駒がどこに位置するかを文字列の形で出力せよ。

ただし、各駒の位置は左端をa列、最下段を1段とする座標系を使い、
各駒はKa1のように「駒を表す1文字」+座標と表し、（ただしポーンの識別文字は省略する）、各駒の文字列は,で区切る。

駒はランクの高い順(K>Q>R>B>N>P)に並べ、同じ駒が複数ある場合、黒のプレイヤーは段の数字が大きい順に、白のプレイヤーは段の数字が小さい順になるように駒を並べる。それでも順が決まらないときは、列を表すアルファベットが昇順になるように並べる。

解法

条件にしたがって実装すればよいのだが、並び順に関する条件指定が多いため、間違えないように気をつける。以下無駄にクラスを使った実装例。。。

ソースコード

int rank[256];

bool cmp(const string &l,const string &r)
{
	return rank[l[0]]>rank[r[0]];
}

struct pclst{
	vector<string> notpwn;
	vector<string> pwn;
	void put()
	{
		int n=notpwn.size(),m=pwn.size();
		stable_sort(all(notpwn),cmp);
		
		rep(i,n)cout<<notpwn[i]<<(i==n-1?"":",");
		if(n&&m)cout<<",";
		rep(i,m)cout<<pwn[i]<<(i==m-1?"":",");
	}
	void push(char p,int y,int x)
	{
		string pos; pos.pb('a'+x); pos.pb('1'+y);
		if(p=='p')pwn.pb(pos);
		else
		{
			p+='A'-'a';
			notpwn.pb(p+pos);
		}
	}
};

int main()
{
	rank['K']=5,rank['Q']=4,rank['R']=3,rank['B']=2,rank['N']=1;
	pclst bl,wh;
	
	vector<string> str(16);
	rep(i,16)cin>>str[i];
	
	rep(i,8)rep(j,8)
	{
		char p=str[15-2*i][2+j*4];
		if('A'<=p&&p<='Z')wh.push(p-'A'+'a',i,j);
	}
	for(int i=7;i>=0;i--)rep(j,8)
	{
		char p=str[15-2*i][2+j*4];
		if('a'<=p&&p<='z')bl.push(p,i,j);
	}
	
	cout<<"White: "; wh.put(); cout<<endl;
	cout<<"Black: "; bl.put(); cout<<endl;
	
	return 0;
}

2993 Emag eht htiw Em Pleh

問題概要

2996の逆。チェスの駒を表す文字列が与えられるので、対応する盤面を表示する。

解法

計算時間に余裕があるのでふんだんにvectorコンテナやstringコンテナなどを使う。

ソースコード

int main()
{
	vector<string> ans(17);
	rep(i,9)
	{
		rep(j,8)ans[i*2]+="+---";
		ans[i*2].pb('+');
	}
	rep(i,8)
	{
		rep(j,8)ans[i*2+1]+=(i&1^j&1)?"|:::":"|...";
		ans[i*2+1].pb('|');
	}
	
	string str;
	rep(i,2)
	{
		cin>>str; cin>>str;
		fr(it,str)if(*it==',')*it=' ';
		stringstream ss(str);
		while(ss>>str)
		{
			int l=str.size(),y=str[l-1]-'1',x=str[l-2]-'a';
			char p=l==3?str[0]:'P';
			if(i)p+='a'-'A';
			
			ans[15-2*y][4*x+2]=p;
		}
	}
	
	rep(i,17)cout<<ans[i]<<endl;
	
	return 0;
}

3044 City Skyline

問題概要

ビル群のシルエットが、その角の座標によって与えられる。
このとき、このシルエットが出来るために必要な最小限のビルの数を求めよ。

角の座標のリストはx座標が小さい順に並んでいる。

解法

ビルがなければならないのは、

凸な角が出現したとき
凹な角が出現し、それより前の角でそのy座標よりも低い辺が最後に出現したよりも後のものに、同じ高さの角が出現してないとき

である。

これはスタックを用いて実装すればよい。

ソースコード

int main()
{
	int n,w;
	scanf("%d%d",&n,&w);
	
	int ans=0,x,y;
	stack<int> S;
	rep(it,n)
	{
		scanf("%d%d",&x,&y);
		if(S.empty()||y>S.top())
		{
			if(y>0)ans++;
			S.push(y);
		}
		else
		{
			while(!S.empty()&&S.top()>y)S.pop();
			if(S.empty()||y!=S.top())if(y>0)ans++;
			S.push(y);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

2769 Reduced ID Numbers

問題概要

生徒にはユニークな1以上10^6未満の学生番号がある。
g人の生徒からなるグループを、れぞれの生徒の学生番号をmで割った余りを全て異なる値になるよう作りたい。
g人の学生番号が与えられたとき、このような最小のmを求めよ。

解法

a%m=b%mはa-bがmで割り切れることと同値。
したがって、どの二つの学生番号の差も割り切らないような最小のmが求める値である。

mの候補は100万以下なので全て覚えながら、候補としてありえないものを消していけばいい。このO(g^2*(IDの差の最大値)^1/2)の解法で計算時間も間に合う。

ソースコード

bool ok[1000000];

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		fill(ok,ok+1000000,1);
		
		int g,s[300];
		cin>>g;
		rep(i,g)
		{
			cin>>s[i];
			rep(j,i)if(s[j]>s[i])
			{
				int d=s[j]-s[i];
				for(int p=1;p*p<=d;p++)
				if(d%p==0)ok[p]=ok[d/p]=0;
			}
		}
		int ans=1;
		while(!ok[ans])ans++;
		cout<<ans<<endl;
	}
	return 0;
}