olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

セグメントツリー

https://github.com/olphe/temp/blob/master/segment_tree.cpp

宣言時に要素数と、min,maxのどっちを求めるかを決める。

v:各要素

l:各要素がもつ範囲の一番左

r:各要素がもつ範囲の一番右

is_min:最小値を求めるか否かの判別をする。

Update,TopDown:一気に全体更新するときに使う。

RMQ:区間の最小値(最大値)を求めるときに使う。

Left:範囲の一番左を求めるときに使う。

Right:範囲の一番右を求めるときに使う。

Insert:代入するときに使う。更新するかしないかも選べる。

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本の道がある。各町にはタクシー会社が存在し、それぞれ決められた数までの道を移動できる。また、料金も決まっている。

1~Nに移動するために必要なコストの最小値を求める問題。

基本的にはdijkstraでよいが、各頂点を訪れるごとに移動できる場所をまとめる。(あらかじめまとめておくとMLEになった)

計算量はO(N^2logN)

難易度は8程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2322477#1