(o_o)

ブログ。

AOJ2393 Dungeon Creation

問題概要
2次元マップが与えられる.マスとマスの間にいい感じに壁を配置することで平路がないようにしたい.早い話が特徴的なグラフが与えられるからその全域木を作りたいということ.作り方は何通りあるか.

解法
行列木定理を使って求めようにも,ナイーブにやると O(H^3 W^3) になる.
実は,マップの i 行 j 列目をグラフの i*W+j 番目の頂点に対応付けてやることで,
行列の対角付近以外は値が0になるような疎行列にすることができる.
そこで行列式を求める計算を工夫すると O(H W^3) になる.

Modのライブラリをベタ貼りだとTLEしたので.割り算の度に逆元を求めていたのをなんとかしてやった.
今度は MLE.行列を保持するだけで空間計算量 O(H^2 W^2) だからなあー.行列を vector> で表現していたのを vector> とかで表現するようにした.
また TLE.unordered_map に変えても若干速くなるもののやっぱり TLE.うーん.
実はこの行列,掃き出し法の間も行の連続した高々 2W 程度の区間しか非ゼロの値を持たない.ならば衝突処理もしないような単純な mod ハッシュでいいのでは.適当なハッシュ関数を書いて提出したら正答.



gist389784ad415bbe65823e