olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

魚の生息範囲(13予選5)

N種類の魚がいて、それぞれの生息範囲が直方体で与えられる。

同時にK種類の魚が存在しうる領域の体積を求めよという問題。

まず、座標の範囲が0~1000000と非常に大きいにもかかわらず、魚の種類は最大でも50なので無駄っぽい。なのでそれぞれについてソートした後、番号をつける。すると座標は最大で100になる。

すると、100^3の各領域に関して魚が何種類存在するか調べられるので、その体積の総和を出力する。

計算量はO(N^4)(多分)

難易度は7程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2321058#1

ビンゴ(09予選6)

N*Nのビンゴに1~Mまでの数字を入れる。和をSにしないといけないという条件の下で、何通りのカードが作れるかな?という問題。

dp[i個の数字で][jを作る]通り数のDPを組む。大きいものから見ることで1次減らせる。

計算量はO(NMS)

難易度は7程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2316612#1

 

最悪の記者(07本選4)

Nチームがリーグ戦を行った。M個の勝敗の情報が与えられたとき、順位表のうちの一つを出力せよ。という問題。

なお、引き分けの試合はなく、同順位のチームもなく、順位が上のチームが下のチームに負けなかったことが保証されている。

勝ったチームから負けたチームに有向辺を張る。

以降チームは頂点とする。

全ての頂点が使われるまで、どこからも辺の伸びていない頂点を始点としBFSを行う。そのとき、通った辺は削除していく。また、訪れた頂点に伸びている辺が存在しない場合のみqueueに追加する。(そうしないと1>2,1>3,3>2のような場合にWAが発生しうる。)

また、他の順位表がありうるかどうかは、ある頂点において探索が終わったときに、queueに複数個頂点が入っていればほかの順位表がありうる。

計算量はO(max(N,M))だと思う。

難易度は7程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2316563#1

夜店(12本選3)

N個の屋台をT時間の間に遊びたい。また、時刻Sの時に花火もみたい。

一つの屋台で遊ぶ時の楽しさと時間が与えられるので、楽しさを最大化しようという問題。なお、屋台は番号の若い順にしか回れず、一つの屋台では一度しか遊べない。

N個目までの屋台について、dp[時刻iまでで得られる楽しさの最大値]というDPを組む。

一つの屋台を複数回数えない工夫が必要だった。

計算量はO(N^2)

難易度は8程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2316399#1

スタンプラリー2(16本選2)

N個の店があり、それぞれJかOかIが決まっている。3店を選んでJOIを作る。

なお、3店は番号の小さい順に選ぶ必要がある。

ここで、任意の場所に任意の文字の店を一つ追加して、JOIを作る通り数を最大化したいという問題。

まず、最初の段階でJOIの通り数を数える。数える方法は、Oの店を見つけたらその前後のJとIの数をかけ、総和を求める。(あらかじめJ,O,Iそれぞれに関して累積和を求めておく。)

また、Jを追加する際は、一番番号の小さい場所に追加すべきだし、Iは一番番号の大きい場所に追加すべきである。

Oは全通り試すほかないので愚直に試す。

O(N)で求められる。

難易度は6程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2315663#1

オレンジの出荷(16本選1)

N個のオレンジがあり、それぞれ大きさが決まっている。一個の箱には最大でM個オレンジを詰められ、箱に詰める際のコストはK+num*(MAX-MIN)で求められる。

(numは箱に詰めたオレンジの数。MAX,MINは箱に詰めたオレンジの大きさの最大値、最小値)

コストを最小化しようという問題。

DP[i個目まで詰めたときの]コストの最小値でDPを組む

計算量は(NM)

難易度は5程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2315653#1

 

ケーキの切り分け2(15本選2)

N個に切られたホールケーキがあり、それぞれの大きさが与えられる。

先攻はまず好きなピースを取り、それ以降後攻は空間が隣にあるケーキの内で大きいほうのケーキを、先攻はそのようなケーキの内好きなほうを取る。

先攻の大きさを最大化しようという問題。

N<=2000なので、dp[iから][jまでのケーキが残っているときの]これ以降取れるケーキの大きさの和の最大値、でDPを組む。

計算量はO(N^2)

難易度は7程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2315643#1