H*Wの旗があって各マスにJかOかIの文字が書かれている。 2*2の欲しい文字の並びと、白い布(最大で最大で一度一つの文字を上書きできる)が与えられるので、最大何回理想の並びが登場するかな？という問題。 まず、最初の段階で何個理想の並びが存在するか調べ…

N冊の本の中からK冊本を売る。 各本には値段とジャンルが決まっていて、同じジャンルの本を多く売るとボーナスが入るので、利益の最大値を求めようという問題。 まず、任意のジャンルに関して、高いものから売ればより高くなることはすぐにわかるのでソート…

N本のつららがあり、左右に自分より長いつららがなければ伸びていく。 長さがLを越えると折れてしまうので、全部折れるまでにどれだけかかるかな？という問題。 毎秒シミュレートしては間に合わないので他の方法を取る必要がある。 まず、最初の段階で伸びる…

円上にN個のピザ屋とM個の家があり、各家からの最も近いピザ屋までの距離の総和を求める問題。 愚直にやるとO(NM)で想定解法ではなさそうなので(10^9なので今は通るかもしれない) 二分探索をして各家がどのピザ屋とどのピザ屋の間にあるか調べる。 二分探索…

N種類の得点が得られるダーツ板に4本ダーツを投げてM点以下という制約のもと最大で何点得られるかな？という問題。 投げないという選択肢が与えられていることに注意しつつ、半分全列挙を使いO(N^2)で解ける。 難易度は6程度であるように感じられた。 http:/…

N-1個の数字が与えられ、それらを足したり引いたりしてMを作る方法は何通りあるかな？という問題。 dp[i個目までの数字で][j]を作る通り数でdpを書けばよい。 単純なDPなので難易度は4程度に感じられた。 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?…

N枚のカードからK枚カードを並べて何種類の数字ができるかな？という問題。 なお、0は存在しないのでsetに突っ込むだけである。 考察部分だけだと3程度かと思うが、set(map+queue)を適正3の人が知っているか、という部分もあると思うので難易度は4にしておく…

N*Mの一度だけ通れるマスと通れないマスでこうせいされたマップを動き回る。 一番多く動けるときはどれだけうごけるかな？といった問題。 移動の仕方が20万通りを越えないと保証されているので、解法自体は困らないと思うが、関数に配列を渡すのに苦労した。…

N匹のキャラクターが縦一列に並んでいる。 (1<=N<=10000) 同じ色のキャラクターが4匹以上隣接すると彼らは消滅する。 また、初期段階で消滅する条件を満たしていることはない。 一度だけ、任意のキャラクターの色を好きなように変えることができるのだが、一…

N個の島とK個のクエリが与えられる。 (1<=N<=100,1<=K<=5000) クエリの種類は2種類で、 ①島Bから島Cへ移動する際の最短コストを求める。 ②島Bと島Cの間にコストDの双方向に移動できる辺を置く また、開始時点では辺は存在しない 辺の追加はO(1)、最短コスト…

最大で200個(M個)の星からなる星座の位置と、最大で1000個(N個)の夜空の星の位置が与えられる。 星座の情報からどれだけ平行移動すれば実際の夜空で星座を見つけられるかな、という問題。(必ず一通りの解があることが保証されている) 愚直にやろうとすると10…

a個の電源、b個のモーター、c個のケーブルのうち、一つずつ部品を選び、接続してちゃんと動くかな？という情報が与えられるので、 ちゃんと動く場合はすべての部品が正常であることが分かる。 また、動かない場合は少なくとも一つの部品が正常でないことが分…

難しいというよりも手間のかかる問題と思う。 開始時刻と終了時刻を５分単位に直し、00:00~23:55からの各５分について雨が降っているか否かをboolで判断する。 その後、bool値と雨が降っているかいないかのbool値から、開始時刻と終了時刻を列挙する。 http:…