オレンジの出荷(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
IOI饅頭(14本選2)
N個の饅頭があり、それぞれ価格が決まっている。
M個の箱があり、それぞれ何個饅頭を入れられるか、購入の際のコストが決まっている。
利益を最大化しようという問題。
まず、饅頭をi個売る時は、高いもの時からi個売るのがいいので、ソートして累積和を求めて置く。
次に、DP[i個目の箱までで[j個以下饅頭を詰められるときの]費用の最小値を求める。
最後に饅頭を売る数で全探索する。
計算量はO(NM)
難易度は6程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2314284#1
電飾(14本選1)
N個の電球が並んでいて、それらは点いているか消えている。
一回だけ、連続する電球の点灯状態を反転させて、交互に並べたい。
最大で何個できるかな?という問題。
まず、連続して同じ状態の電球が並んでいるところをリストアップしておき、それらの中で隣接している二つをそうでなくなるようにする、というのを全パターン試す。
なお、何個交互に並ぶかは、リストから求められるので、計算量はO(N)
難易度は6程度に感じられた
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2314233#1
JOI紋章(13本選1)
H*Wの旗があって各マスにJかOかIの文字が書かれている。
2*2の欲しい文字の並びと、白い布(最大で最大で一度一つの文字を上書きできる)が与えられるので、最大何回理想の並びが登場するかな?という問題。
まず、最初の段階で何個理想の並びが存在するか調べておき、各マスごとにJに変えたとき、Oに変えたとき、Iに変えたときの登場回数の差分を記録して置き、最大値を出力する。
なお、張り替えたときに調べるのは張り替えたマスが左上、右上、左下、右下となる4パターンのみでよいので、O(H*W)となる。
発想は簡単だが実装に苦戦したので、難易度は6程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2314204#1
古本屋(11本選2)
N冊の本の中からK冊本を売る。
各本には値段とジャンルが決まっていて、同じジャンルの本を多く売るとボーナスが入るので、利益の最大値を求めようという問題。
まず、任意のジャンルに関して、高いものから売ればより高くなることはすぐにわかるのでソートしておく。
また、これによって各ジャンルについて、売った冊数から売価を求められる。
その結果を利用し、
dp[iジャンル目までで][j冊売った]時の利益の最大値
というdpを回せばよい。計算量はO(N^2)
難易度は7程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2286172#1
つらら(10本選3)
N本のつららがあり、左右に自分より長いつららがなければ伸びていく。
長さがLを越えると折れてしまうので、全部折れるまでにどれだけかかるかな?という問題。
毎秒シミュレートしては間に合わないので他の方法を取る必要がある。
まず、最初の段階で伸びるつららに関しては何秒で折れるかはすぐにわかる。
最初に自分より長いつららが隣にあるつららは、隣にある自分より長いつららが全て折れてから伸び始めることもわかるので、隣にある自分より長いのつららが折れるまでの時間の最大値に自分が伸び始めてから折れるまでの時間を足せばよいことが分かる。
再起関数で解いた。計算量は多分O(N)
難易度は7程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2286155#1