Gather the Maps! 解説

問題名：Gather the Maps!
出典：Problem F, ACM/ICPC Practice Contest for Japan Domestic, 2005-06-19
難易度：☆☆☆
問題の種類：DP
解法：動的計画法
解答ソースコード：
- p0017-deq.cpp

アルゴリズムの概略

「n 人に分割された地図が誰か一人の手に集まるのに必要な最低日数を求める」というこの問題は日数に関する動的計画法の問題です。つまり，t 日目における最適解が t-1 日目の最適解から求まるという性質があります。

Sample Inputの問題を例にとりましょう。子孫1が最初に持っている地図を地図1とします。最初 (t = 0) は自分自身の地図だけを持っています（下図参照，○は空いている日）。

1日目 (t = 1) では，子孫1と子孫3が会うことができます。そこで地図をどちらかに集めることができるのですが，ここでは「どちらかに（誰に）集めた」ことを決めるのではなく，「それぞれの子孫が t 日目までで集められる可能性のある全ての地図番号」を求めて保持しておきます。つまり，ここでは子孫1も子孫3も地図1と3を持つことが可能なわけです。

2日目 (t = 2) では，子孫2と子孫3が会うことができます。ここで，子孫3は1日目 (t-1日目) で地図1,3を持っていることができるので，子孫2と子孫3が会えば地図1,2,3を集めることができます。

最後に，3日目 (t = 3) に子孫2と子孫4が会うことで全ての地図を集めることができるので，このアルゴリズムは終了します。

このアルゴリズムでは，「誰が誰に地図を渡せばいいか」という情報は記録していません。なので，実際にどのようなパスを辿れば（誰が誰に地図を渡せば）全ての地図を集めることが可能なのかは分かりません。しかし，この問題では最低必要な日数だけ求めればいいので，これで必要十分なのです。

このアルゴリズムをまとめると，日数 t に関するループの内側では次のようになります。

その日に集まれる子孫を全て列挙（集合{X}とする）
{X}の各員が現在保持可能な地図を全て列挙（その日に集められる全ての地図，集合{Y}とする）
各{X}の保持可能な地図を全て{Y}に設定
終了条件のチェック

アルゴリズムの計算量

日数 t に関する外側のループは O(t) で最大30回まわります。次にループの内側を見てみましょう：

ある日に収集可能な地図を列挙するには，全ての子孫に関してある地図を持っているかを調べればいいので，計算量はたかだか O(n²) になります（子孫数と地図数は同じなので）。
獲得可能な地図を更新するには，その日に集まることのできる子孫に関して「収集可能な全ての地図」のフラグを更新すればいいので，最悪でも計算量は O(n²) になります。
終了条件のチェックは，その日に集まった地図の個数を数え上げればいい（個数が n なら全て揃っている）ので，計算量は O(n) になります。

結局，ループの内側の計算量のオーダーは O(n²) です。日数 t に関するループをあわせると O(t×n²) で，地図を集めれなかった最悪の場合 t = 30 で子孫数（地図数）が n = 50 なので計算量の概算は t×(2×n² + n) = 151,500 程度です。従って1つのデータセットに関しては一瞬で（1ms程度で）終わることが分かります。

アルゴリズムの実装

特に難しいことはありません。フラグ用の配列を多用することになります（それ以外の実装は面倒でしょう）。

解答ソースコードでは「収集可能な地図」の集合を set で実装しています。フラグ用の配列を使ってもほとんど変わりませんが，ここで set を使うと終了条件のチェックが少し楽に書けます。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $

deq notes