魚の生息範囲(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