AOJ2290 Attack the Moles
問題概要
問題文から明らかな最小費用流を感じる何か
解法
右手が左手より右側になければならない，という条件は無視できる．
最小費用流で解くにしても，如何せんグラフのサイズが大きい．
きっちり辺を張ると辺の数は O(N^2) くらいになってしまう．
ここで，いい感じに辺を削除することを考える．a -> b, b -> c って辺張ってたら a -> c は要らないよね，みたいな感じで．
辺の削除にかかる時間は，全通り試すと O(N^3) だが，前処理で簡単な配列処理としてやると 2sec もかからない．
後は DAG なので負コスト辺をいい感じに正に変換したら間に合う．
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
また TLE．unordered_map に変えても若干速くなるもののやっぱり TLE．うーん．
実はこの行列，掃き出し法の間も行の連続した高々 2W 程度の区間しか非ゼロの値を持たない．ならば衝突処理もしないような単純な mod ハッシュでいいのでは．適当なハッシュ関数を書いて提出したら正答．
AOJ1293 Common Polynomial
無事院試にも受かって生活に余裕が出てきたので，そろそろAOJ-ICPCでも埋めていくことにした．
今日から毎日1問ずつ解いた問題をブログに書いていこうと思う．単純に計算すると夏休みのうちに40問くらい解くことになりそう．
まずは今日は簡単な問題から．
問題概要
2つの1変数整式が与えられるので，そのGCDを求めよ
解法
多項式ライブラリを貼って構文解析するだけ．
構文解析は簡単．しかし多項式の処理がちょいと面倒だ．
整式の剰余を求めるとき分数になりそうなときは適宜掛けてやったりとか，答えの全ての係数のGCDが1になるようにしてやったりとか，そういうことを犬の世話みたいにいちいちやらなあかん．
けど久々のプロコンなのでこういう何も考えず実装するだけの問題はちょうどいいかもしれない．
AOJ2404 ドッグフード
結構実装が大変と言われているこの問題。想定解法は指数オーダーの探索だが、これにも割と良さげな解法がある。
例えばこういうケースを例に考えてみる。ロープの上側がロープが結ばれている杭、左下側がスタート地点、右下の緑色の点がゴール地点である。
STEP 1
以下のような三角形を考える。この三角形の外側にある杭は無視してよい。三角形の内側にある杭について、その杭とゴール地点を結ぶ線分と赤い線分のなす角の小さい順に番号をつける。
STEP 2
適当な非負整数iを決め、1番目からi番目までの杭は迂回して、それ以外の杭は迂回しないとする。このとき、
(a) スタート地点、ゴール地点、1番目からi番目までの杭を頂点集合として凸包を求ると、スタート地点とゴール地点を直接結ぶ辺以外の辺の長さの和が犬の走る経路の長さとなる。
(b) ロープが結ばれている杭、ゴール地点、i+1番目以降の杭を頂点集合として凸包を求ると、ロープが結ばれている杭とゴール地点を直接結ぶ辺以外の辺の長さの和が必要なロープの長さとなる。
必要なロープの長さが実際のロープの長さ以下となるケースのうち、犬の走る経路の長さが最短となるものを求めればよい。iに対して必要なロープの長さは単調非増加なので、二分探索を用いることができ、O(N(logN)^2) で求めることができる。
AOJ1177 番犬派遣会社
高難度の場合分けゲーとして名高いこの問題だが、最近割と良さげな解法を思いついたので実装してみた。
STEP 1
原点から引数で与えられる点Pまでの建物の内部を通らない最短の道のりを求めるような関数を作る
原点とその点を結ぶ線分が建物の内部を通らないときは、その線分の長さが最短である。
そうでないときは、以下のようなグラフを作って、最短経路を求めてやればいい。
原点と点Pと長方形の頂点をグラフの頂点として、長方形の内部を通らない線分をグラフの頂点として追加すればよい。
ただし，点Pが長方形の内部にある場合は，INFを返すこと．
STEP 2
まず、原点を中心に半径lenの円を描く。
次に、長方形の各頂点について、その頂点までの原点からの最短の道のりを求め、その長さをlenから引いた長さを半径とした円をその頂点を中心に描く。ただし、その頂点までの最短の道のりの長さがlen以上である場合（つまりその頂点に番犬が到達できない場合）は円を描かない。
そして、円と建物の交点、円と円の交点を列挙する。
STEP 3
それぞれの円について、STEP 2で列挙した交点のうちその円周上に乗っているもののみを取り出し、円の中心からの角度の順にソートする。これで、フェンスの候補となる円弧を列挙することができる。後は、円弧からランダムに1点選び原点までの最短の道のりを求め、これがlenの値と一致すれば非常に高い確率でこの円弧はフェンスである。
この方法だと建物が複数個ある場合でも簡単に実装できそう。
ICPCアジア地区大会
東京大会は17位でした．
台湾大会は14位でした．
