TopCoder SRM 642 Div1

今回もSRM 642の解説行きます.今回からソースコードのヘッダ部分は切ります(一応マクロは残します).

今回の問題は

  • Easy: メモ化 / 確率
  • Medium: 最小費用流

となっております.


Easy (250点)

問題

ある町にはバスがN本あり,それぞれのバスは駅を出発してtime[i]分で駅に戻ってくる.一度に運行できるバスは1本だけであるため,ひとたびバスが出発するとtime[i]分はバスがでない.出発するバスはそれぞれprob[i] %の確率で選ばれる.今あなたが時刻sに駅に到着したとすると待ち時間の期待値はいくつか?

制約条件

1 <= N <= 100
0 <= s <= 100000

解法

ある時刻tにバスが出発する確率をメモ化で求める.すなわち,ある時刻にバスが出る確率をmemo[t]とするとき,
memo[t+time[i]] = sum {i: memo[t] * (prob[i] / 100.0)}
が成り立つ.

今求めたいのは時刻sから初めてバスが出る時刻なので,上のメモ化を時刻がs以上になったら打ち切る.
するとs以上に現れる確率の合計が1になるようになる.

あとは,これをsと時刻の差を取りながら期待値計算していけばいい.


Meidum (500点)

問題

あなたの庭には木がN本ある.その木はそれぞれheight[i]の高さを持っており,1日にadd[i]だけ伸びる.また,あなたはチェーンソーをM本もっていて,そのチェーンソーで木をdevice[j]の高さにすることができる.ただし,1日に各チェーンソーは1回しか使えず,木も1日に1回しか切れない.適切に木の手入れをしていった時のtime日目の木の高さの合計の最小値を求めよ.

解法

まず,着眼点としてはそれぞれの木はtime日の間でただ1回だけきればよく,それ以上切ってもチェーンソーの無駄遣いにしかなりません.

また,もしt日目に木を切ったとすれば最終日の木の高さはdevice[t] + add[i] * (time – t)です(tは1からtime).

仮に木を切ることができないのであれば,その高さはheight[i] + add[i] * timeとなるが,木を切ることができないというのを言い換えると,height[i] + add[i] * timeがいずれのdevice[t] + add[i] * (time – t)よりも小さくなるということになります.

ということは,各木について何日目にどのチェーンソーを割り当てるのが最小になるかを求める問題になり,組み合わせ+最小化ということで最小費用流が使えそうです.

問題はどうグラフを持つかですが,まず各木は1回しか切れないという条件から,sourceから各木のノードへcap=1, cost=0のエッジを引きます.

もし,各木を何日目かに切ったとするとそのあとに伸びる高さはadd[i] * jと表せるので,各木ノードと各日ノードの間にadd[i] * jのエッジを引きます.このとき,各木ノードにはそもそも1しかフローが流れないので,木が2日以上の日に切られることはありません.

次に,その日にどのチェーンソーを使うかという部分ですが,各日には各チェーンソーが1回しか使えないので,これは各日ノードから各チェーンソーノードにcap=1, cost=0のエッジを張ればいいです.

最後にチェーンソーは全体で合計time回ずつ使えて,使った時には残りの高さがdevice[i]になるので,各チェーンソーノードからsinkに向かってcap=time, cost=devide[i]のエッジを張ります.

以上で,大体OKなのですが,木を切れない場合があるので,それを別にノードとして用意します.このノードをUとすると各木ノード
からUに向かってcap=1, cost=height[i] + add[i] * timeのエッジを張り,さらにUからTへcap=N, cost=0のエッジをはればOKです.

後は木を切る本数N本をフローとして流して,最小費用流を求めればいいです.ちなみにBellman-Fordを使った実装で問題なく通りました.


まとめ

今回はEasyは結構簡単だった気がします.途中確率がパーセントで与えられているのに気付かなくて,少し時間かかりましたがw

Mediumはフローっぽいなぁとは思いましたが,グラフの作り方が思いつかず時間切れという感じです.

というわけで,今回の解説を終わります.最後までお読みいただきありがとうございました.

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください