USACO 2008 January
初めてUSACOを解いたけどGold難しい。
問題文をよく読みたい。
PKU 3658 - Artificial Lake
問題
図のように凸凹した人口池の底面の情報が与えられる。
人工池の底面は、左からi番目のブロックでは幅W[i],基準からの高さがH[i]となっている。
ただしH[i]は全て異なる。
高さが一番低いところから単位時間に１の量の水を注ぎ込む。
各ブロックについてブロックが浸かる時間を求めよ。
ただし、各ブロックについて底面からの高さが１となるまで水が注がれたらそのブロックは浸かったとみなされる。
制約
1<=N<=100000
1<=W[i]<=1000
1<=H[i]<=1000000
解法
H[i]が全て異なるので異なるブロックが同時に浸かり始めたりすることはない。
そこでまずpriority_queueを使って各ブロックが何番目に浸かるかを求める。
具体的には、まず一番高さが低い箇所をキューに入れる。
キューに入っている一番低い箇所を取り出して、左右１個ずつを見る。
左右とも、順番が決定しているもしくは今の箇所より高ければ、そこが何番目か決まる。
そうでなければ、決まらないので何もしない。
このとき、左右でまだ決定していないものがあればキューに入れる。
これを繰り返せばO(NlogN)で順番が求まるはず。
次に、各ブロックについて、そこが浸かるようなときの幅と、左右の自分より高くなる中で最も近いものの高さを求める。
サンプルならば、それぞれ、
4 12 6
7 INF 7
となる。
高さについては、左の高さと右の高さに分けて求める。
これには、先程求めた順番に沿って左右を見るDP的なことをすればよい。
単純には多分出来無いのでUnionFindを使って工夫する必要がある。O(αN)
これが求まればシミュレーション的な感じで答えを求めれば良い。O(N)
オーバーフローに注意。
PKU 3661 - Running
問題
牛がN分間走る。
各分に対し、走れる距離D[i]が決まっている。
牛は１分走ると１疲労度がたまる。疲労度がMを超えてはいけない。
牛は好きなタイミングで休むことができて休むと１分ごとに疲労度が１減る。
休むと決めたら疲労度が0になるまで休まなければならない。
最初疲労度は0で最後も疲労度は0でなければいけない。
このとき走れる最長距離を求めよ。
制約
1<=N<=10000
1<=M<=500
1<=D[i]<=1000
解法
DP[i][j] = i分に疲労度がjのときの再長距離
PKU 3662 - Telephone Lines
問題
ノード数N、エッジ数Pのグラフが与えられる。
各エッジは値L[i]を持つ。
ノード0からノードN-1までのパスで、エッジの値の最大を最小にしたい。
ただし、エッジの値はK個まで0にすることが出来る。
このときパス内のエッジの値の最大の最小値を求めよ。
またノード0からノードN-1までのパスが存在しないときは-1を出力せよ。
制約
1<=N<=1000
1<=P<=10000
1<=L[i]<=1000000
