IOI列車で行こう(13本選2)
N両の電車とM量の電車が与えられる。それぞれはI列車とO列車のみで構成される。
順にどちらかの先頭の車両を取っていき、IOIOIOIOIのようにIとOか交互に並び、且つIが端にあるように並べたとき、最長の長さを求める問題。
なお、電車はあまらせてもよいし、ぞれぞれ先頭から好きなだけポイしてもよい
dp[Sのi両目][Tのj両目まで使い[長さが偶数or奇数]の時の長さの最大値
をもってDPを回す。
計算量は(N+M)
難易度は6程度に感じられた
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2327262#1
JOI国の買い物事情(11本選3)
N個の町、M本の道、K個のショッピングモールがある。
ショッピングモールは町の中にある。
町及び道の中で一番近いショッピングモールまでの距離が最大の値を求める問題。
まず、dijkstraで町までの距離を求め、各辺について辺上で一番遠い点を求める。
計算量はO(NlogN)
難易度は5程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325415#1
ペンキの色(08本選5)
H＊Wの看板にN個のテープが貼ってある。色を塗らなければならないスペースが何個あるかを求める問題。
座標圧縮をして、queueで何個あるか探す。
計算量は(N^3)だが定数が小さい。
難易度は7程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325312#1
ぴょんぴょん川渡り(08本選4)
N行に石があり、それぞれの行にある石の数と、位置と滑りやすさが決まっている。
向こう岸まで跳んで行った時の最小の危険度を求める問題。
なお、一行飛びジャンプはM回までできる。
dp[i行目までで][j回までの一行飛びジャンプを使い][i行目のk個目の石]にいるときの危険度の最小値をもって配るDPを回す。
計算量はO(NM)(定数倍が大きいけど)
難易度は6程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325302#1
最軽量のモビール(07本選5)
N個の棒があり、そのそれぞれにひもがつながっている。一番上の棒をつるしているひもを除いては、ひもの下には棒かおもりがある。
角棒について、自分をつるしているひもより左の長さ、右の長さ、左につるしている棒の番号、右につるしている棒の番号(おもりなら0)が与えられる。
つり合いを取れるようにし、かつおもりを最軽量化した時の重りの重さの合計を求める問題。
一番上の棒から再帰的に下の棒を見ていき、つり合いがとれていなければつり合うようにし、より軽量化できるなら軽量化する。
計算量わからない。
非情に実装難であると感じたので難易度は8程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325265#1
タクシー(14予選5)
N個の町、K本の道がある。各町にはタクシー会社が存在し、それぞれ決められた数までの道を移動できる。また、料金も決まっている。
１～Nに移動するために必要なコストの最小値を求める問題。
基本的にはdijkstraでよいが、各頂点を訪れるごとに移動できる場所をまとめる。(あらかじめまとめておくとMLEになった)
計算量はO(N^2logN)
難易度は8程度に感じられた
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2322477#1
魚の生息範囲(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
