Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-05-20

[][] Codeforces Round #119 : C. Weak Memory 18:56 はてなブックマーク -  Codeforces Round #119 : C. Weak Memory - 練習帳

問題文

 問題文

概要

  • 無向連結グラフが与えられている(節:n個、枝:m本)
  • グラフのうちk個の節に印がついている
  • スタート地点とゴール地点が与えられている
  • 次の条件を満たす正数qのうち、最小の値を求めよ。条件を満たすqがない場合には-1と答えよ。
    • 条件:「スタートからゴール地点への経路のうち、次の条件を満たすものが存在する。スタート地点からqステップ以内に印つきの節がある、さらにその印つきの節からqステップ以内に印つきの節がある...これを繰り返してゴール地点までたどり着ける。」
  • 制限
    • n ≦ 10**5, m ≦ 2*10**5, k ≦ n, 実行時間2秒以内

コード

 Practiceでの提出コード:Submission #1683870 - Codeforces

 UnionFindはライブラリから使用:no title

考えた過程

方針1:印つき節のみのグラフを作れるか?

 もし印つき節だけ取り出し、節間の距離を元のグラフでの最短距離とするグラフを作れれば、その上でダイクストラに近いことを行えば、与えられた課題を解くことができそうです(各節の上で、通常の「その節までの最短距離」の代わりに「その節に到達するまでにたどった枝のコストの最大値」を覚えます)。すると問題はそのような最短距離を結んだグラフが作成可能に帰着できます。でもそれは難しそう。一番嬉しいのは2つの印つき節間の距離がすべて求まる事ですが、それにはワーシャルフロイドを行う必要がありますが、印つき節の最大数は10**5なので、計算量的に無理で、仮にできたとしてもメモリが足らなさそうです。印つき節間の距離を全部は計算しないで計算が間に合うようにするということも考えられるけれど、必要不必要の判断をどのように行うかがパッとは思いつかないです。とりあえずこの方針ではこの先に思いつきませんでした。

方針2:qについて2分探索

 次に考えたアイデアはqの値について2分探索が出来る事です。つまり、ある値qでスタートからゴールまでたどり着くことが可能なら、qより大きい値でもたどり着くことは可能なので2分探索が使えます。qが3なり4なりある特定の定数になってしまえば、今いる印つきの節からqステップ以内にある印つきの点を深さ優先的に探索することで、ゴールに辿り着けるか調べられます。つまり、「ある印つき節移動する→その点を始点とするダイクストラを実行し、qステップ以内の印つき節を見つける→それらを順番に訪問する→・・・」とすれば良いです。でもダイクストラは無駄な計算をものすごくしているような気がする。ダイクストラの計算量がO(m+nlogn), 印つき節の深さ優先探索でO(k)なので、合計の計算量は大雑把にO(k(m+nlogn))。やっぱり計算量的に難しそう。

 ただ、qについて2分探索の方はそれなりに良さそうな気がしていて、印つきの2つの節について「枝が貼られている」⇔「qステップで移動可能」でグラフを作れば、求める条件は新しく作ったグラフの上でスタート地点とゴール地点が連結であるというところまで問題を簡単にできます。連結かどうかを調べるのは、深さ優先探索でもUnionFindでもできるので、この部分はあまり気にする必要がなさそうです。ただ、この場合も方針1の時と同じように、すべての印つき節のペアについてqステップで移動可能かを考えていたら時間は足らなくなってしまう。

解答

 ここまでで良くわからなくなりギブアップ。他の方の回答を見ていたのですが、以下の方針がしっくり来ました。以下のSubmissionを参考にさせていただきました。

「qステップで移動可能か」という条件のチェックがナイーブな方法では全く時間が足らないですが、この部分を工夫して計算量を減らすのがポイントだと思います。方針は次のとおりです。各節(印つきとはかぎらない)で「最も近い印つき節」と「その印つき節までの距離」の2つを覚えておきます。節vに対するこれらの値をv.n(neighbour), v.d(distance)と置く事にすると、印つき節をつなげるための規則は枝(v, w)に対して「v.d+1+w.d <= qならばv.nとw.nをつなげる」となります。キューに(v.n, v.d)を入れて、順番にこの規則を適用します。(v.n, v.d)の情報に更新があったら、その更新情報をキューに追加します。

最初に挙げた自分の提出コードに対して、次のテストケースを与えた場合を考えます。このテストケースはT字型をしたグラフでTの先端3箇所にvolunteerがいます。T字の上棒の左端が1, 右端が42, T字の下端が27番の節です。連結部分は26番で1-26間の距離は25, 26-27間の距離は15, 26-42間の距離は30です。答えとなるq=45のケースでは、T字を遠回りしなければゴールにつけません。気になるのはq=55の時で。この場合スタートからゴールまで直接移動できるのですが、自分の提出アルゴリズムでは、やはりT字を遠回りする道を選択しています。つまり、印つき節に対し「枝が貼られている」⇔「qステップで移動可能」となっているグラフよりも少ない枝を張っている事で計算量が抑えられているのだと思います。各節に対して覚えておくのは最も近い印つき節だけで覚える事でそれを達成しています。

不安になるのは、節のつなぎ漏れがないかということです。実を言うと自分でも何故これで正しくできるかをきちんとは理解できていないですのですが、今回の提出コードではそれで十分だったようです。