Regionals 2008 :: Asia - Taipei

Live Archive

フロー祭
http://rhodon.u-aizu.ac.jp:8080/arena/contest.jsp
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=322

4259 - Dangerous Tunnels

問題

頂点数n+2、辺数tの重み付きグラフが与えられる。
辺はノード番号が小さいほうから大きい方へのみ通ることが出来る。
ノード0からノードn+1へ点素なパスk個を選ぶときその中の辺の最大値を最小化せよ。

制約

n<=200
k<=10

解法

最小費用流の変形版もしくは最大流＋二分探索。
頂点に流量制限があるのでinとoutに分割する。

4260 - Fortune Card Game

問題

C個のカードがある。
カードには、番号、文字、次の番号が書かれている。
全く同じカードはないが、番号が同じカード等はある。
最初番号が1のカードから初め（複数あればその中の一つ）、その番号に書かれた「次の番号」と同じ番号のカードから一つ選ぶということを繰り返す。
このときカードに書かれた文字をつなげたものが得られる文字列となる。
また、このときのスコアを「次の番号」の和で定義する。
文字列が与えられるので、その文字列が得られるようにカードを選んでいったとき、スコアの最大値を求めよ。

制約

C<=800
文字列の長さ<=150
文字列に使われる文字：AからE

解法

dp[i][j] = i文字目まで選び次の番号がjのときのスコアの最大値

4261 - Trip Planning

経路復元有りのDP

4262 - Road Networks

強連結成分の個数

4263 - Early-Morning Pickup

問題

頂点数V、辺数Eのグラフで表される町がある。
R人の代表、C人の客、M個の工場がある。
R人の代表が出勤するとき、次のどちらかの行動を取る

  • 自宅 -> 客の家の一つ -> 工場の一つ -> 会社
  • 自宅 -> 会社

全ての客の家は1人の代表に訪問されなければならない。
このとき、R人の代表の出勤時間の平均値の最小を求めよ。

制約

V<=512
R>=C

解法

代表iが客jの家によったときにかかるコスト、客の家によらないときにかかるコストを求め、最小重み最大二部マッチングっぽいことをする。
このとき二部グラフの左側を代表ノードR個、右側を客ノードC個と客の家によらない事を表すノード1個とする。

4264 - Message

やるだけ

4265 - Lost Treasure

4266 - Space Elevator

問題がわからない… →　分かった(9/14)

問題

0を原点として、右側にr個、左側にq個の点がある。
各点にはポイントが設定されており、時間tにポイントpの点に止まった場合、max(p-t,0)のスコアが入る。
時間0には原点におり、距離1移動するのに時間1がかかる。
最適な順で点に止まった場合、得られるスコアの最大値を求めよ。
ただし全ての点に止まる必要はない。

制約

r,q<=100
ポイント、座標<=1000

解法

最初、右の点に止まって左の点に止まって、また右の点に止まるというようなことはないと思っていた。
しかし、例えば
2 1
1 10
5 100
100 1000
のようなケースでは、右に行って左に行って右に行くのが最良となる。
ということで
dp[左どこまでいったか][右どこまでいったか][時間][左と右どっちにいるか]
でDPする。
時間は最大999まで考えれば良いので2*10^7とかになって間にあう。
配列は最利用する。

4267 - Finding The Heaviest Path

DFS

4268 - Bonus Adjustment

問題

n行m列の行列の各要素が小数点以下2桁までの実数として与えられる。
各行と各列の和は変えずに、各要素を整数にしたい。
ただし、各要素の値を1以上変えることは許さない。
このようにして要素を変えた行列を求めよ。
ただしこの条件で行列が作れない場合はnoと出力せよ。

制約

n,m<=50

解法

行や列の和が固定された問題は最大流が多い気がする。
ということでこの問題も最大流。
行ノードと列ノード、ソース、シンクを頂点とする。
ソースから行ノード、列ノードからシンクへ対応する和を容量とした辺を張る。
行ノードiから列ノードjへの辺をどうするか。
この辺に流れるフローが答えの(i,j)成分になるようにしたい。
ところで、答えの(i,j)成分として許される候補は、それぞれ1個または2個である。
これは、(i,j)成分に下限と上限があると考えることが出来る。
よって、行ノードiから列ノードjへは、容量に加え最小流量の制限もあるような辺を張れば良い。
最小流量の制限もある場合の最大流の解き方は蟻本に乗っており、そのとおり実装した。