PKU400問！！！！ - simezi

ついに400の大台を達成！！！疲れた〜！！！
ここからが難しい問題ばっかで大変なんだろうけど。。。もっと頑張って問題解いて早く赤コーダーになりたい。

といいつつ今月はちょっとやることがあるのでペースは落とす予定。

No.	Title	分類・解法	主観的難易度
3348	Cows	幾何・多角形の凸包・面積	★★★☆☆
1083	Moving Tables	実装問題	★★☆☆☆
2101	Honey and Milk Land	実装問題	★☆☆☆☆
2726	Holiday Hotel	貪欲法	★★☆☆☆
1157	LITTLE SHOP OF FLOWERS	動的計画法	★★☆☆☆
2182	Lost Cows	整列（ソーティング）	★★☆☆☆

以下問題概要コード解法など。

3348 Cows

問題概要

座標平面上の点の座標が与えられる。これらを（頂点として）結んで得られる多角形のうち、面積が最大になるようなものの面積を求めよ。

解法

凸包をとってやればいいことがすぐにわかると思う。
凸包と多角形の面積についてはライブラリを使用orzごめんなさい。。。後で書けるようにする……（といいつつ幾何は後回しの予定だけど）

ソースコード

int main()
{
  int n; scanf("%d",&n);
  G g;
  rep(i,n){
    int a,b; scanf("%d%d",&a,&b);
    g.pb(P(a,b));
  }
  g=convex_hull(g);
  double a=area2(g);
  cout<<(int)a/100<<endl;

  return 0;
}

凸包の部分については略。Spaghetti Source様参考に。

1083 Moving Tables

問題概要

部屋1,3,5,7, ... ,399が一列に並んでいて、長い廊下を挟んで向かいに部屋2,4,6, ... ,400が一列に並んでいる。部屋1の向かいは部屋2、部屋3の向かいは部屋4...である。
さて、部屋から部屋へ机を運びたいが、廊下は狭いので一つの机を移動させている間、机を出す部屋から机を入れる部屋までの廊下は使うことができない。
一つの机を移動するのに10分の時間がかかるとき、与えられたリストの机を移動するのにかかる最小の時間を求めよ。

解法

廊下のある部分を何回机が通るかについて着目してみる。
すると、着目した部分を机が通った回数x10分は少なくとも時間がかかることがわかり、逆に全体で机が最も多く通った部分の回数x10分間があれば全ての机を移動させることができることがわかる。これを実装すればよい。

机を運び出す部屋のリストは必ずしも昇順でないことに注意する必要がある。（これでWA出したorz）

ソースコード

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		int n; cin>>n;
		int cor[200]={0};
		rep(i,n)
		{
			int s,t; cin>>s>>t;
			s=(s-1)/2; t=(t-1)/2;
			if(s>t)swap(s,t);
			for(int i=s;i<=t;i++)cor[i]++;
		}
		cout<<*max_element(cor,cor+200)*10<<endl;
	}
	return 0;
}

2101 Honey and Milk Land

問題概要

縦横に碁盤の目状にnxm本の川が流れている。
各川の間隔の数列a[n-1],b[m-1]が与えられる。このとき、ヘリコプターで全ての川を訪れるのに最低限必要な移動距離を求めよ。
ただし離着陸は移動距離に含めず、出発、終了の地点は自由であるとする。

解法

物凄くシンプルな問題……のはずなのだけれど問題文が非常に読み取りにくく、WA数が尋常じゃないことになっている。
問題が読み取れれば簡単、長方形の対角線の長さを計算するだけである。
主観的難易度は問題文を理解した後で、のもの。（読解能力も非常に重要だが、読み取りの難しさを入れるとアレすぎるのでｗ）

ソースコード

int n,e,w,h;

int main()
{
	cin>>n>>e; int t;
	rep(i,n-1)cin>>t,w+=t;
	rep(i,e-1)cin>>t,h+=t;
	
	cout<<(int)ceil(hypot(w,h))<<endl;
	
	return 0;
}

1157 LITTLE SHOP OF FLOWERS

問題概要

f本の花をv個の花瓶に順番をそのままにして入れていく。ただし順番が同じであれば空の花瓶があってもよい。
i番目の花をj番目の花瓶に入れるときの評価点が与えられたとき、評価点の合計を最大にするような入れ方における評価点を求めよ。

解法

i番目の花をj番目まで入れたという状態を記録して最適解を求めて行くような動的計画法をすればよい。
コードはO(n^3)の計算時間であるがn=100と小さいためにこれでも十分間に合う。

ソースコード

int sc[100][100];
int dp[100][100];

int main()
{
	int f,v; cin>>f>>v;
	rep(i,f)rep(j,v)cin>>sc[i][j],dp[i][j]=-inf;
	
	rep(i,v)dp[0][i]=sc[0][i];
	for(int i=1;i<f;i++)
	{
		rep(j,v)rep(k,j)dp[i][j]=max(dp[i][j],sc[i][j]+dp[i-1][k]);
	}
	int ans=-inf;
	rep(i,v)ans=max(ans,dp[f-1][i]);
	cout<<ans<<endl;
	
	return 0;
}

2726 Holiday Hotel

問題概要

海のそばのホテルを予約するのに、以下の条件で候補を決める。

そのホテルよりも海に近いホテルは全てそのホテルより料金が高い。
そのホテルよりも料金の高いホテルは全てそのホテルより海から遠い。

各ホテルの海からの距離と料金が与えられた時、候補となるようなホテルの軒数を求めよ。

解法

ホテルの数が最大10000であるため、O(n^2)のアルゴリズムや力技の探索ではおそらく時間的に厳しい。（試してない）
ホテルを距離の順にソートしてしまえば、解を絞り込むのにする比較が1度だけで済むことに着目すれば、ソートでO(nlog n)、解の吟味でO(n)の全体でO(nlog n)の解法に至る。

ソースコード

pi hotel[10000];

int main()
{
	int n;
	while(scanf("%d",&n),n)
	{
		rep(i,n)
		{
			int d,c; scanf("%d%d",&d,&c);
			hotel[i]=mp(d,c);
		}
		sort(hotel,hotel+n);
		
		int cands=1;
		pi prev=hotel[0];
		
		for(int i=1;i<n;i++)
		{
			if(hotel[i].first!=prev.first&&hotel[i].second<prev.second)
			cands++,prev=hotel[i];
		}
		
		printf("%d\n",cands);
	}
	return 0;
}

2182 Lost Cows

問題概要

番号1-nをもつn匹の牛が、でたらめな順番で一列に並んでいる。
列においてi番目の牛の、「自分の前にいる自分より番号の若い牛の数」がそれぞれ与えられたとき、列の牛のそれぞれの番号を求めよ。

解法

思いついた解法は以下の通り。最悪計算量O(n^2)のコードなのだけど通ってしまった。
本当はもっと高速な解法があるのではないだろうか。
（データ構造にヒープを使う……？よくわからない……）

列の先頭から牛を並べ替えていく。自分より番号の若い牛がi匹いるならば、その時点でi番目にその牛を入れ替えてしまえば、そこまでの牛は整列していることになる。
これを全ての牛について行うと、番号の順に並んでいる。
あとはそれぞれが整列した後の位置を、でたらめな列の牛に順に答えさせる。

ソースコード

int n;
vi cow;
pi tmp[8000];

int main()
{
	cin>>n;
	cow.pb(0);
	rep(i,n-1)
	{
		int l; cin>>l;
		cow.insert(cow.begin()+l,i+1);
	}
	rep(i,n)tmp[i]=mp(cow[i],i);
	sort(tmp,tmp+n);
	rep(i,n)cout<<tmp[i].second+1<<endl;
	
	return 0;
}