JOI logo
第21回日本情報オリンピック　二次予選

2022年2月5日
情報オリンピック日本委員会

問題
５ 		　　交易計画 (Trade Plan)　(配点 100点)
　　時間制限 : 4 sec / メモリ制限 : 1024 MB

解説

解説担当：山縣 龍人 (tatyam)

小課題 1

Q = 1 の場合を考えよう．この場合，両端が交易に協力してくれる都市であるような道路のみを取り出してグラフを作り，そのグラフ上で DFS や UnionFind を用いて都市 A から都市 B まで移動できるか判定することで，時間計算量 O(N + M) で解くことができる．

また，Q 回の交易それぞれで上を行うことで，時間計算量 O(Q (N + M)) でこの問題を解くことができる．小課題 1 では，N ≦ 1000，M ≦ 1000，Q ≦ 1000 と制約が小さいので，このアルゴリズムは十分高速である．

小課題 2

小課題 2 では，すべての州は連結である．(飛び地のない地図を考えてみると良いだろう．) したがって，各交易では，都市 A の属する州と都市 B の属する州がとなり合っているか (あるいは同じであるか) を判定すれば良い．

州 S[U] に属する都市と州 S[V] に属する都市を結ぶ道路があれば，州 S[U] と州 S[V] はとなり合っているという情報を平衡二分探索木 (C++ における std::set) などに記録し，各交易で都市 A の属する州と都市 B の属する州がとなり合っているか時間計算量 O(log M) で判定すれば，時間計算量 O(N + (M + Q) log M) でこの問題を解くことができる．シラバス外ではあるが，平衡二分探索木の代わりにハッシュテーブルを使うのも良いだろう．

小課題 3

小課題 3 は，小課題 1 の時間計算量 O(Q(N + M)) から何か改善したアルゴリズムで解くことを想定している．ここでは，時間計算量 O(N + M Q1/2 log M + Q(log M + log Q)) のアルゴリズムを解説する．他の方法でも正解できるかもしれない．

小課題 1 の UnionFind による解法を改善することを考える．まず，長さ N の UnionFind を Q 回作ることができないので，UnionFind を，経路圧縮せず変更履歴を持つ undo 可能 UnionFind に変更する．アルゴリズムは以下のようになる．

  1. 長さ N の undo 可能 UnionFind を作る．
  2. 道路を両端の州によって分類する．
  3. 都市 A から都市 B に特産品を届けられるか判定する．
    1. 両端が州 S[A] に属する道路を UnionFind に追加する．
    2. 両端が州 S[B] に属する道路を UnionFind に追加する．
    3. 一端が州 S[A] に，もう一端が州 S[B] に属する道路を UnionFind に追加する．
    4. 都市 A から都市 B に移動可能か判定する．
    5. 道路の追加を全て undo する．

このままでは，同じ道路が何度も追加・削除されてしまう．そこで，一端の州が同じ交易をまとめて処理する．

  1. 長さ N の undo 可能 UnionFind を作る．
  2. 道路を両端の州によって分類する．
  3. 交易を両端の州によって分類する．
  4. 一端が州 S[A] の都市である交易を判定する．
    1. 両端が州 S[A] に属する道路を UnionFind に追加する．
    2. もう一端が州 S[B] の都市である交易を判定する．
      1. 両端が州 S[B] に属する道路を UnionFind に追加する．
      2. 一端が州 S[A] に，もう一端が州 S[B] に属する道路を UnionFind に追加する．
      3. 一端が州 S[A] に，もう一端が州 S[B] に属する交易全てについて，都市 A から都市 B まで移動可能か判定する．
      4. 1. 2. を undo する．
    3. 1. を undo する．

これでもまだ，「両端が州 S[B] に属する道路を UnionFind に追加する」部分で同じ道路が何度も追加・削除されてしまう．この量を抑えるために，S[A] と S[B] に (両端が州 S[A] に属する道路の数) > (両端が州 S[B] に属する道路の数) または (両端が州 S[A] に属する道路の数) = (両端が州 S[B] に属する道路の数) かつ S[A] ≧ S[B] という条件を付け，両端がその州に属する道路が多い州ほどまとめて処理されやすくする．

  1. 長さ N の undo 可能 UnionFind を作る．
  2. 道路を両端の州によって分類する．
  3. 交易を両端の州によって分類する．
    1. (両端が州 S[A] に属する道路の数) < (両端が州 S[B] に属する道路の数) または (両端が州 S[A] に属する道路の数) = (両端が州 S[B] に属する道路の数) かつ S[A] < S[B] であれば，A と B を交換する．
  4. 一端が州 S[A] の都市である交易を判定する．
    1. 両端が州 S[A] に属する道路を UnionFind に追加する．
    2. もう一端が州 S[B] の都市である交易を判定する．
      1. 両端が州 S[B] に属する道路を UnionFind に追加する．
      2. 一端が州 S[A] に，もう一端が州 S[B] に属する道路を UnionFind に追加する．
      3. 一端が州 S[A] に，もう一端が州 S[B] に属する交易全てについて，都市 A から都市 B まで移動可能か判定する．
      4. 1. 2. を undo する．
    3. 1. を undo する．

実は，これで時間計算量 O(N + M Q1/2 log M + Q(log M + log Q)) を達成している．これを確かめよう．

「両端が州 S[B] に属する道路を UnionFind に追加する」以外の場所では，各道路は高々 1 回しか UnionFind に追加されないので，この操作がない場合の計算量は O(N + M log M + Q(log M + log Q)) である．したがって，「両端が州 S[B] に属する道路を UnionFind に追加する」操作が何回行われるかを調べれば良い．両端がその州に属する道路の数が M/Q1/2 以上である州を大きな州，M/Q1/2 未満である州を小さな州と呼ぶことにする．州 S[B] が小さい州である場合，操作は交易 1 回あたり高々 M/Q1/2 回なので，これを Q 回やっても高々 M Q1/2 回である．州 S[B] が大きい州である場合，州 S[A] も大きい州でなければならない．道路が M 個しかないことから，大きい州は高々 M/(M/Q1/2) = Q1/2 個しか存在しないので，両端が州 S[B] に属する道路が追加される回数は高々 Q1/2 回で，全ての道路で合計しても高々 M Q1/2 回である．

「両端が州 S[B] に属する道路を UnionFind に追加する」操作が高々 2 M Q1/2 回しか行われないことが分かったので，時間計算量は O(N + M Q1/2 log M + Q(log M + log Q)) である．

小課題 4

実は，小課題 2 がこの問題を解くヒントになっている．小課題 2 では，各州が連結であるため，州がとなり合っているかを判定したのであった．これは，1 つの州を 1 つの頂点に縮約して，一端が州 S[A] に，もう一端が州 S[B] に属する交易が来たら，一端が州 S[A] に，もう一端が州 S[B] に属する道路を追加して判定するものと見ることができる．ここで重要なのは，S[A] でも S[B] でもない州の縮約が答えに影響を与えないことである．(そもそもそのような州の都市を通ることができないため)

これより，あらかじめ両端が同じ州に属する道路を全て追加してしまって良いことがわかる．その後は小課題 3 と同様にすると，アルゴリズムは以下のようになる．

  1. 長さ N の undo 可能 UnionFind を作る．
  2. 道路を両端の州によって分類する．
  3. 両端が同じ州に属する道路を UnionFind に追加する．
  4. 交易を両端の州によって分類する．
  5. 一端が州 S[A] に，もう一端が州 S[B] に属する交易を判定する．
    1. 一端が州 S[A] に，もう一端が州 S[B] に属する道路を UnionFind に追加する．
    2. 一端が州 S[A] に，もう一端が州 S[B] に属する交易全てについて，都市 A から都市 B まで移動可能か判定する．
    3. 1. を undo する．

これで時間計算量は O(N + M log M + Q(log M + log Q)) となり，満点を取ることができる．また，「両端が同じ州に属する道路を UnionFind に追加」した後の状態を覚えておくことで，経路圧縮のある通常の UnionFind でも undo することができ，さらに (シラバス外ではあるが) 道路と交易の分類にハッシュテーブルを使うことで，時間計算量が O(N + (M + Q) α(M)) となる．