電飾(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
ピザ(09本選2)
円上にN個のピザ屋とM個の家があり、各家からの最も近いピザ屋までの距離の総和を求める問題。
愚直にやるとO(NM)で想定解法ではなさそうなので(10^9なので今は通るかもしれない)
二分探索をして各家がどのピザ屋とどのピザ屋の間にあるか調べる。
二分探索をする際に、先頭のピザ屋を一周した先にも置いておくと楽。
(ピザ屋の情報に0とDを加える)
計算量がO(MlogN)なので通る。
難易度は6程度であるように感じた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2286134#1
ダーツ(08本選3)
N種類の得点が得られるダーツ板に4本ダーツを投げてM点以下という制約のもと最大で何点得られるかな？という問題。
投げないという選択肢が与えられていることに注意しつつ、半分全列挙を使いO(N^2)で解ける。
難易度は6程度であるように感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2285995
一年生(11予選4)
N-1個の数字が与えられ、それらを足したり引いたりしてMを作る方法は何通りあるかな？という問題。
dp[i個目までの数字で][j]を作る通り数でdpを書けばよい。
単純なDPなので難易度は4程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2285939#1
