一年生(11予選4)
N-1個の数字が与えられ、それらを足したり引いたりしてMを作る方法は何通りあるかな？という問題。
dp[i個目までの数字で][j]を作る通り数でdpを書けばよい。
単純なDPなので難易度は4程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2285939#1
カード並べ(10予選4)
N枚のカードからK枚カードを並べて何種類の数字ができるかな？という問題。
なお、0は存在しないのでsetに突っ込むだけである。
考察部分だけだと3程度かと思うが、set(map+queue)を適正3の人が知っているか、という部分もあると思うので難易度は4にしておく。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2274954#1
薄氷渡り(09予選4)
N*Mの一度だけ通れるマスと通れないマスでこうせいされたマップを動き回る。
一番多く動けるときはどれだけうごけるかな？といった問題。
移動の仕方が20万通りを越えないと保証されているので、解法自体は困らないと思うが、関数に配列を渡すのに苦労した。
結果としては多重ベクターを渡せばよさそう(ほんまか)ということに落ち着いた。
難易度は私が犯したミスがなくとも実装難かと思うので6程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2274929#1
連鎖(09予選3)
N匹のキャラクターが縦一列に並んでいる。
(1<=N<=10000)
同じ色のキャラクターが4匹以上隣接すると彼らは消滅する。
また、初期段階で消滅する条件を満たしていることはない。
一度だけ、任意のキャラクターの色を好きなように変えることができるのだが、一番多くのキャラクターを消すと、どれだけキャラクターは残るかな、といった問題。
(色は3種類)
全ての色の変え方を試せばよいだけなのだが、実装がめちゃくちゃつらい。
私は、消えた範囲をもって、その上下で色の比較をした。
オーダーの話をすればO(N^2)なので通る。(当時だと怪しいけど定数はめちゃくちゃ小さいので問題ないかと思われる)
特殊な知識などは必要ないが、発想や高い実装力が求められるので難易度は7程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2243195#1
船旅(08予選6)
N個の島とK個のクエリが与えられる。
(1<=N<=100,1<=K<=5000)
クエリの種類は2種類で、
①島Bから島Cへ移動する際の最短コストを求める。
②島Bと島Cの間にコストDの双方向に移動できる辺を置く
また、開始時点では辺は存在しない
辺の追加はO(1)、最短コストはO(N^2)で求められる。
よってO(KN^2)のため間に合う。
(辺の追加回数上限が設定されているのでもしかするとdijkstraの高速化が要求されていた時代かもしれない…？)
難易度は4程度に感じられた……がdijkstraは5以上かなあと思うので5にしておく
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2243185#1
星座探し(08予選4)
最大で200個(M個)の星からなる星座の位置と、最大で1000個(N個)の夜空の星の位置が与えられる。
星座の情報からどれだけ平行移動すれば実際の夜空で星座を見つけられるかな、という問題。(必ず一通りの解があることが保証されている)
愚直にやろうとすると1000通りの平行移動を試し、任意の星と星座の星が一致するかどうかを調べる必要があるので、O(MN^2)かかるっぽいので短縮したい(今なら多分通りそうな気はするが)
星座の情報と、夜空の情報を入れるsetを用意する。
x,yのまま扱うのは面倒なので一変数に直します。
そして、星座の一番小さな座標の星から、夜空に対応する星があるかどうか調べる。
するとO(MNlogN)となるので間に合う
難易度は6程度であるように感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2243162#1
品質検査(07予選5)
a個の電源、b個のモーター、c個のケーブルのうち、一つずつ部品を選び、接続してちゃんと動くかな？という情報が与えられるので、
ちゃんと動く場合はすべての部品が正常であることが分かる。
また、動かない場合は少なくとも一つの部品が正常でないことが分かる。
N個与えられる動くか動かないかの情報を保持しておき、
まず正常な部品を確定させる。
再びN個の情報を頭から見て、動かない組み合わせに遭遇した時に、正常な部品を2個つかっていたら、残りの部品は不良品であることが分かる。
難易度は5程度であるように感じられた
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2239909#1
