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

No.	Title	分類・解法
1026	Cipher	Simple Math, String manipulation
2231	Moo Volume	Simple Math
3299	Humidex	Bisection method
3278	Catch That Cow	BFS
3268	Silver Cow Party	Graph, Dijkstra's algorithm
3224	Go for Lab Cup!	Straight forward
1555	Polynomial Showdown	Straight forward,String manipulation

以下問題概要、解説、ソースコードなど

1026 Cipher

問題概要

相違なる自然数1...nを鍵a[i]とした次のような暗号化を考える。
平文sのi番目の文字がa[i]番目にある文字列をf(s)とする。
fをk回適用した文字列を暗号文とする。
与えられた文字列、n, kに対して対応する暗号文を求めよ。

解法

問題文にkの範囲が書かれてないが、TLE率が高いことを見るとナイーブにやるとTLEしそう。（試してない）
暗号化をk回適用すると、i番目の文字はi→a[i]→a[ a[i] ]→……→i
となっていつかiに戻ってくることを利用する。すなわちそれぞれのiについて周期を求め、kをその周期で割った余りの回数だけ（その文字に）暗号化の操作をすればよい。

ソースコード

int n,ky[200],k;
string buf;
int f[200];
bool u[200];

int rec(int c,int v)
{
	u[c]=1;
	if(v)f[c]=v;
	
	if(u[ky[c]])return 1;
	return 1+rec(ky[c],v);
}
int getp(int c,int r)
{
	if(r<1)return c;
	return getp(ky[c],r-1);
}

int main()
{
	while(cin>>n,n)
	{
		rep(i,n)cin>>ky[i],ky[i]--;
		
		while(cin>>k,k)
		{
			cin.ignore();
			getline(cin,buf);
			int l=buf.size();
			if(l<n)
			{
				buf.resize(n);
				fill(buf.begin()+l,buf.end(),' ');
			}
			
			fill(u,u+n,0);
			rep(i,n)if(!u[i])f[i]=rec(i,0);
			
			fill(u,u+n,0);
			rep(i,n)if(!u[i])rec(i,f[i]);
			
			string ans(n,' ');
			rp(i,buf)ans[getp(i,k%f[i])]=buf[i];
			
			cout<<ans<<endl;
		}
		cout<<endl;
	}
	return 0;
}

2231 Moo Volume

問題概要

数直線上にN個の牛が並んでいて、牛は他のN-1匹の牛に、その距離に等しい大きさの声で
話しかける。Nと牛の座標が与えられた時、全ての牛の声の大きさの総和(N*(N-1)個の和)を求めよ。

解法

TLE率が高いのでO(n^2)でやるとTLEしそう。（試ｓ（ｒｙ
左から順に牛と牛の間隔を見て行った時、k番目の区間は何回加算されるかを考えてみる。k番目の区間の左側の牛から右側の牛にそれぞれ一回ずつ、右側から左側にも一回ずつ呼びかけがなされるため、結局、
(左の牛)*(右の牛)*2回だけ加算されることがわかる。

あとは32bit整数に答えが入りきらない可能性があることに注意すればおｋ.

ソースコード

int n,loc[50000];

int main()
{
	cin>>n;
	rep(i,n)cin>>loc[i];
	
	sort(loc,loc+n);
	ll ans=0;
	
	rep(i,n-1)ans+=2LL*(i+1)*(n-1-i)*(loc[i+1]-loc[i]);
	cout<<ans<<endl;
	
	return 0;
}

3299 Humidex

問題概要

次の式で表されるhumidexという指数がある。

humidex = temperature + h
h = (0.5555)× (e - 10.0)
e = 6.11 × exp [5417.7530 × ((1/273.16) - (1/(dewpoint+273.16)))]

humidex,temperature,dewpointのうちいずれか二つが与えられる。残りの一つを求めよ。

解法

dが与えられればh,tは足し算引き算で求まる。t,hが与えられた場合はdを二分法により求める。
ちなみにhumidexとはカナダで使われる不快指数のような指数。dew pointは露点。

3278 Catch That Cow

問題概要

数直線上をxからx+1,x-1,2*xのいずれかに移動することができる。
初期座標とゴールの座標が与えられた時、初期座標からゴールまで到達するために必要な最小の移動回数を求めよ。いずれの座標も0以上100000以下である。

解法

幅優先探索。移動回数は最大でも|n-k|あれば済むので、その範囲を超えるような移動は考えなくて良い。

ソースコード

int n,k,mx,mxc;
int c[200001];

int main()
{
	cin>>n>>k;
	mxc=abs(n-k); mx=max(n,k)+mxc;
	fill(c,c+mx+1,inf);
	
	queue<int> Q; Q.push(n);
	c[n]=0;
	
	while(!Q.empty())
	{
		int cur=Q.front(); Q.pop();
		
		if(cur==k)
		{
			cout<<c[k]<<endl; break;
		}
		if(c[cur]>=mxc)continue;
		
		for(int d=-1;d<=1;d+=2)
		{
			int nx=cur+d;
			if(nx<0||nx>mx||c[nx]<=c[cur]+1)continue;
			c[nx]=c[cur]+1;
			Q.push(nx);
		}
		if(2*cur<=mx&&c[2*cur]>c[cur]+1)
		{
			c[2*cur]=c[cur]+1;
			Q.push(2*cur);
		}
	}
	
	return 0;
}

3268 Silver Cow Party

問題概要

n個の牧場のうち二つを結ぶ一方通行の道路がm本ある。牧場xでパーティが行われる。全ての牧場にの中で、牧場xまで行き自分の牧場まで戻るのにかかる最短の移動距離のうちで最も大きいものを求めよ。
（n≦1000, m≦100000とする）

解法

nがでかいがワーシャルフロイド法で行けるかと思ったら無理だった。ですよね。

グラフが疎である（n^2に対してmが小さい）ため、O(n^3)のワーシャルフロイドよりもO(E log V)のダイクストラ法をV回繰り返したほうが有利になる。
というわけでダイクストラ法をn回回す。これで1400MS弱となって一応Acceptedなのだが上位の解答は0MS……なんか根本的に間違った方針なのかもしれない。

ソースコード

int d[1000][1000];

int main()
{
	int n,m,x; cin>>n>>m>>x; x--;
	
	rep(i,n)fill(d[i],d[i]+n,inf);
	
	vector<vector<pi> > w(n);
	rep(i,m)
	{
		int s,t,c; cin>>s>>t>>c;
		w[s-1].pb(mp(c,t-1));
	}
	
	rep(i,n)
	{
		int vis=0;
		priority_queue<pi> Q; Q.push(mp(0,i));
		
		while(!Q.empty())
		{
			int cur=Q.top().second,c=Q.top().first;
			Q.pop();
			
			if(d[i][cur]<=-c)continue;
			vis++; d[i][cur]=-c;
			if(vis==n)continue;
			
			fr(iter,w[cur])
			{
				if(d[i][iter->second]>-c+iter->first)
				Q.push(mp(c-iter->first,iter->second));
			}
		}
	}
	
	int ans=0;
	rep(i,n)ans=max(ans,d[i][x]+d[x][i]);
	cout<<ans<<endl;
	
	return 0;
}

3224 Go for Lab Cup!

問題概要

卓球のリーグ戦のスコア表がある。a[i][j]はiがjに対して取った得点で、試合は3点先取である。勝った試合の最も多い先取を求めよ。複数いる場合は番号の若いものを答えよ。

解法

勝った試合の数を数えて最大値をもつ先取を答える。

1555 Polynomial Showdown

問題概要

9つの整数が与えられる。
1番目の数をx^8の係数に、2番目の数をx^7の係数に…9番目の数を定数項にもつような多項式を定められた書式で出力せよ。

解法

定数項、x^1の項、最も次数の大きい項、係数の絶対値が1、すべて0などの場合分けをして出力。

while(!cin.eof())としたらジャッジデータの最後に空行があってハマった……
C++にはJavaのScanner#hasNextIntに相当するようなものはないんだろうか。

ソースコード

int main()
{
	int c[9];
	while(cin>>c[0])
	{
		bool z=c[0]==0; //all zero?
		rep(i,8)
		{
			cin>>c[i+1];
			if(c[i+1])z=0;
		}
		if(z)
		{
			cout<<0<<endl; continue;
		}
		
		bool f=1; //first term?
		rep(i,9)if(c[i])
		{
			if(!f)cout<<" "<<(c[i]>0?"+ ":"- ");
			else
			{
				cout<<(c[i]<0?"-":"");
				f=0;
			}
			if(i==8||abs(c[i])!=1)cout<<abs(c[i]);
			if(i!=8)cout<<"x";
			if(i<7)cout<<"^"<<8-i;
		}
		cout<<endl;
	}
	return 0;
}