11/13 PKU
3622 Gourmet Grazers
牛と牧草があり、牧草ごとに値段とgreennessが決まっている。各牛は、牧草に要求する最小の値段とgreennessを持っている。牛は個性を犠牲にしたくないので、それぞれ異なる牧草を食べたい。牧草の値段の総和を求めよ。
牛と牧草をあわせてgreennessの高い順にソートして、牧草が出てきたらmapに追加、牛が出てきたら最も良い値段の牧草を取り出す
3269 Building A New Barn
グリッド上に牛が何頭かいる。ある位置に納屋を建設して、牛の不便さが最小になるようにしたい。不便さは、納屋と各牛の間のマンハッタン距離の総和で表される。納屋を牛のいる場所に建ててはいけない。最小の不便さと、それを達成することができる納屋の位置の数を求めよ。
まず、各X,Y座標について、その軸のみで見た時の不便さの和を求めておく。すると、各牛の位置について、そこに建てたとしたときの不便さがわかる。
その後、不便さの値をソートして、答えで二分探索する。すなわち、ある不便さ以下の位置が何個あるかわかればよい。不便さはX座標、Y座標について独立で考えて良いので、適当にやるとX,Y座標における不便さの和がS以下になるものは何個あるかわかる。また、建ててはいけない場所の数もわかる。
3038 Flying Right
定員Cの各駅停車の飛行機があり、牛を乗せて飛ぶ。牛はKグループあり、それぞれ起点と目的地が決まっている。グループの一部が乗れて、一部が乗れないなどになってもかまわない。飛行機は午前は北から南へ、午後は南から北へ飛ぶ。最大何頭の牛を乗せられるか。
greedyをstarry sky treeで加速する。
3172 Scales
N個のおもりがあって、昇順に並べた時、あるおもりの重さは前の２つのおもりの重さの合計以上である。N個の中からいくつか選んで、Cを超えない最大の重さを実現せよ。
おもりが1000個とか書いてあるが、条件を解釈すると高々44個であるとわかる。
半分全列挙を使うと、非常にぎりぎりであるものの通る。でも絶対これ想定解法じゃないよなあ
3169 Layout
牛が一列に、１番から順に並んでいる。いくつかの牛の組ごとに、牛の間の最大距離もしくは最小距離が決まっている。牛1と牛Nの間の最大距離を求めよ。
Bellman-Fordやるだけ
