Flu(インフルエンザ) - joi2008-day1 解説

筆者: qnighy

インフルエンザの感染経路の条件に基づいて感染をシミュレーションする問題である。

単純解法

この問題ではそれぞれの都市で最初に流行した日さえわかればよい。また、その計算が辺数最短経路であることもすぐにわかるだろう。

ここで、グラフを単純に全点間で距離を計算することで計算した場合、O(N^2)で解けることがすぐにわかる。これで配点の20% が取れる。

O(WH+d^2N)解法

ある都市から距離d以内の近傍点はO(d^2)個程度しかない。そこで予め二次元配列を作って都市の位置から逆引きできるようにしておき、ある都市に隣接する都市をそれらの近傍点を全て調べることで列挙すれば、O(d^2N)程度で解ける。

この方法ならば上記に加えさらに30%、合計50% が期待できる。

O(WH+N)解法

バケット法を用いる。つまり座標平面を大きさd×dのバケットごとに分割すれば近傍を探すとき、隣接バケット9箇所だけを調べればいいようにできる。この方法でO(WH+N)が実装できる。(このオーダーは概算であり、やや疑問が残る。)

この方法で満点が期待できる。なお、他にも平面探索木などを使うこともできる。