9/12 PKU

3010 The Genome Database of All Space Life

規則によって圧縮された文字列が与えられるからその文字列のi文字目を求めよ、という問題。

圧縮文字列を木構造にして木を適当にたどるだけ

3469 Dual Core CPU

デュアルコアCPUがあって、それにN個の処理をさせる。処理は2つのコアのうちどちらかで行い、それぞれのコアについてかかるコストが決まっている。また、M組の2つの処理に対して、違うコアで行うとかかるペナルティコストが決まっている。コストを最小にしてすべての処理を行うとき、コストはいくらか、という問題。

なぜか最大流。起点->処理のcapacityをコアAでのコスト、処理->終点のcapacityをコアBでのコストとし、ペナルティコストが決まっている処理P,Qに対してはP->Qのcapacity、Q->Pのcapacityをペナルティコストとして最大流。

N,Mがとても大きいので(N<=20,000、M<=200,000)、Edmonds-Karpでは余裕でTLEするらしい。ここでは、Dinicを用いて、一気に複数のフローを流すようにするとなんとか間に合う。

Dinic速い。すばらしいです

追記：最大流でやりたくなるけどやったらTLEしそうと言った3614は、Dinicを使ってもTLEしました。たぶん、Ford-FurkersonでやってもTLEします。

2038 Team Rankings

いくつかの5人の順序が与えられる。各順序までの距離の和が最小のもののうち、辞書順に最小のものを求めよ。順序間の距離は、「2つの要素の組で、両順序間で順番が異なるもの」の数として定義される。

言うまでもなく、やるだけ