Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2014-06-07

TCO 2014 R2A 500 NarrowPassage

00:40

Problem

There is a narrow passage of length L.

For each valid i, wolf i wants to move from a[i] to b[i].

The passage is so narrow that no two wolves cannot pass by each other.

Luckily, there is a lot of empty space on each end of the passage. If some wolves reach the same end of the passage, they can change their order arbitrarily before reentering the passage.

Return the minimum total distance the wolves have to travel.

Constraints
  • L <= 1e6.
  • a.length <= 50

解法

(1) 外に出ない狼がいる場合と,(2) そうでない場合に分けて考える.

(1) の場合は,左に行く人数と,右に行く人数を固定すると,可能かどうかがわかり,可能な場合は,最小距離も自明.

(2) の場合は,一旦全員が外に出た後,左側に居る狼が右側に移動する場合がある.(これに気付かなかった.)

初期状態 S から左側に行く人数と,終状態 T に左側から戻ってくる人数を固定する.

S から左側に行く狼の集合を L1 , 右側に行く狼の集合を R1 とする.

T に関しても同様に L2, R2 を定める.

L1 にいて R2 にいる狼の数と,R1 にいて L2 にいる狼の数の和が,右端から左端,または左端から右端に移動しなければならない狼の数となる.

 |