PKU演習問メモ(8/22) - simezi

集中できないお……orz

No.	問題名	問題の種類および解法	難易度
2115	C Looooops	合同式の割り算	★★★☆☆
2153	Rank List	バケットソート	★★★☆☆
2299	Ultra-QuickSort	バブルソートの交換回数	★★★★☆
2007	Scrambled Polygon	幾何・凸図形の性質	★★☆☆☆
2059	Watchdog	実装	★★☆☆☆

2115 C Looooops

問題概要

for(variable i=A;i!=B;i+=C)というループの実行回数を求めよ。
ただしvariableはkビットの符号なし整数型である。

k≦32,
A,B,C＜2^kを満たす。

解法

kがそこそこ大きいのでループをシミュレーションするとTLEになる。
A+xC≡B (mod 2^k）となるようなxを直接求める必要がある。

上の式を変形して、
xC≡B-A

この両辺をCで割りたい。
2^kとC,B-Aが互いに素の場合はmod2^kにおけるCの逆元をかければよい。

そうでない場合、元の方程式を考えると、
xC=B-A+y*2^kなので、両辺をGCD(C,B-A,2^k)で割れば、上の場合に帰着し、Cの逆元が求まる。

ソースコード

spaghetti sourceの法の逆元のコードを使用（その部分は略）

int main()
{
	int a,b,c,k;
	while(scanf("%d%d%d%d",&a,&b,&c,&k),a||b||c||k)
	{
		if(a==b)puts("0");
		else
		{
			ll K=1LL<<k;
			ll A=(b-a+K)%K,g=__gcd(A,K);
			g=__gcd(g,(ll)c);
			A/=g; c/=g; K/=g;
			
			ll ci=invMod(c,K);
			if(ci==0)puts("FOREVER");
			else printf("%lld\n",ci*A%K);
		}
	}
	return 0;
}

2153 Rank List

問題概要

n人がm回試験を行った成績が与えられる。
1〜m回目の試験終了時点での"Li Ming"の（その時点での合計得点に基づく）順位を出力せよ。

n≦10000,m≦50,
各テストの点数は0以上100以下の整数である。

解法

昔TLE出して放置した問題。

テストの点数は限られた範囲の整数なのでバケットソートができる。
バケットソートをした後、自分より上に居る人の人数を合計すれば自分の順位がわかる。
（点数は最大5000なので、これは普通に足し算すればよい）

入力がばらばら+文字列なので面倒。一度stable_sortで並べ替える。
文字列にstringを使ったりすると多分TLE?（多分昔の回答はバケットソート使ってなかったのも悪いと思うんだけど）

ソースコード

struct S{
	char s[31];
	bool operator<(const S &r)const{
		return strcmp(s,r.s)<0;
	}
};
struct cmp{
	bool operator()(const pi &l,const pi &r)const{
		return l.first<r.first;
	}
};
int n,m,nm;
pi in[500000];
int dist[5001],sc[10000];

int main()
{
	scanf("%d ",&n);
	
	map<S,int> id; int li;
	S tmp;
	rep(i,n)
	{
		gets(tmp.s);
		id[tmp]=i;
		if(strcmp(tmp.s,"Li Ming")==0)li=i;
	}
	
	scanf("%d",&m); nm=n*m;
	rep(i,nm)
	{
		int p; scanf("%d ",&p);
		gets(tmp.s);
		in[i]=mp(id[tmp],p);
	}
	stable_sort(in,in+nm,cmp());
	
	int mx=0;
	rep(i,m)
	{
		rep(j,n)
		{
			sc[j]+=in[m*j+i].second;
			mx=max(mx,sc[j]);
		}
		rep(j,mx+1)dist[j]=0;
		rep(j,n)dist[sc[j]]++;
		
		int cnt=1;
		for(int j=mx;j>sc[li];j--)cnt+=dist[j];
		printf("%d\n",cnt);
	}
	
	return 0;
}

2299 Ultra-QuickSort

問題概要

n項からなる数列a[n]が与えられる。これをバブルソートによりソートするときの交換回数を求めよ。

n＜50000,0≦a[i]≦999,999,999を満たす。

解法

spaghetti sourceのバブルソートの交換回数のページ（http://www.prefield.com/algorithm/sort/mergecount.html）に解説がある。

バブルソートの交換回数は転置数を数えればよいのだが、O(n^2)ではなくO(nlog n)でマージソートをしながら、次のようにして可能。

左半分、右半分それぞれで転置数をカウント。
マージするときに、右半分の要素が前にきたら、左半分で「残りの数」（こいつらは全て今マージしてる右の数より大きい）を転置数に足す

なるほどー。
ちなみに答えはlong longにしないと桁があふれるので注意。

ソースコード

ll rec(vi &a)
{
	ll ret=0; int n=a.size();
	if(n>1)
	{
		vi b(a.begin(),a.begin()+n/2);
		vi c(a.begin()+n/2,a.end());
		ret+=rec(b)+rec(c);
		
		for(int i=0,j=0,k=0;i<n;i++)
		{
			if(k==c.size())a[i]=b[j++];
			else if(j==b.size())a[i]=c[k++];
			else if(b[j]<=c[k])a[i]=b[j++];
			else a[i]=c[k++],ret+=n/2-j;
		}
	}
	return ret;
}

int main()
{
	int n;
	while(scanf("%d",&n),n)
	{
		vi a; int t;
		rep(i,n)scanf("%d",&t),a.pb(t);
		cout<<rec(a)<<endl;
	}
	return 0;
}

2007 Scrambled Polygon

問題概要

凸な多角形とは図形内の任意の2点を結んだ線分が、常にその図形の内部に含まれるような多角形のことをいう。
このような図形を頂点の一つを座標平面の原点に置いたとき、次のような性質が満たされる。

図形の頂点を含む象限は3つ以下である
図形を(0,0)のものから順に頂点を辿るとき、各象限内において、原点と頂点を結んだ直線の傾きは単調増加または単調減少である

いま、一点を原点にもつ凸多角形が各頂点の座標により与えられる。
多角形の頂点を、原点を出発し、反時計回りに頂点をめぐるような順序に並べ替えよ。

座標軸上に頂点はないものとする。

解法

問題文で丁寧に説明されている性質をそのまま使えばよい。
すなわち、象限それぞれで点を（原点からの）傾きの順にソートし、
最初の象限（点が含まれない象限の次）から出発して、象限を反時計回りに辿ればよい。

言葉では解りにくい気がするのでその場合はソース参照。。。

ソースコード

bool cmp(pi a,pi b)
{
	double m=a.second*1.0/a.first,mm=b.second*1.0/b.first;
	return m<mm;
}

int main()
{
	vector<pi> one,two,three,four,ans;
	int x,y;
	while(~scanf("%d%d",&x,&y))
	{
		if(x<0&&y>0)one.pb(mp(x,y));
		if(x<0&&y<0)two.pb(mp(x,y));
		if(x>0&&y<0)three.pb(mp(x,y));
		if(x>0&&y>0)four.pb(mp(x,y));
	}
	
	sort(all(one),cmp); sort(all(two),cmp);
	sort(all(three),cmp); sort(all(four),cmp);
	
	ans.pb(mp(0,0));
	if(one.empty())
	{
		fr(i,two)ans.pb(*i); fr(i,three)ans.pb(*i); fr(i,four)ans.pb(*i);
	}
	else if(two.empty())
	{
		fr(i,three)ans.pb(*i); fr(i,four)ans.pb(*i); fr(i,one)ans.pb(*i);
	}
	else if(three.empty())
	{
		fr(i,four)ans.pb(*i); fr(i,one)ans.pb(*i); fr(i,two)ans.pb(*i);
	}
	else
	{
		fr(i,one)ans.pb(*i); fr(i,two)ans.pb(*i); fr(i,three)ans.pb(*i);
	}

	fr(i,ans)printf("(%d,%d)\n",i->first,i->second);
	
	return 0;
}

2059 Watchdog

問題概要

一辺がsで各辺が座標軸に平行な正方形をした建物の屋上に、n個のハッチがある。
建物の左下の座標は(0,0)であり右上の座標は(s,s)である。

屋上に置く番犬をつなぐ杭を立てる場所を、以下のように求めよ。

x座標、y座標がともに整数
番犬から最も遠いハッチまでの距離が、最も近い屋上のふちまでの距離を超えない
候補が複数ある場合x座標が最も小さいもの（それも複数ある場合はy座標が最小のもの）

そのような候補がない場合"poodle"と出力せよ。

s≦40,n≦50を満たす。

解法

正方形内の格子点について、条件を満たすかどうか全部試す。

ソースコード

int s,n;
int X[50],Y[50];
bool ng[41][41];

bool ok(int y,int x)
{
	int mne=min(min(y,s-y),min(x,s-x));
	rep(i,n)if(mne<hypot(X[i]-x,Y[i]-y))return 0;
	
	return 1;
}

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d",&s,&n);
		rep(i,s+1)rep(j,s+1)ng[i][j]=0;
		rep(i,n)scanf("%d%d",X+i,Y+i),ng[Y[i]][X[i]]=1;
		
		int x=-1,y=-1;
		rep(j,s+1)rep(i,s+1)if(!ng[i][j]&&ok(i,j))
		{
			y=i,x=j; goto END;
		}
		
		END:
		if(x<0)puts("poodle");
		else printf("%d %d\n",x,y);
	}
	return 0;
}