プロコン練習におすすめの問題
こんにちはtatsyです。
昨日はGCJ2013のRound2でした。いや、1問もできなかったですけど。
気を取り直して、解いた問題の中から難しめと思われる問題をリストアップしておこうと思います。
どちらかというと個人的な備忘録的内容です。
幅優先・深さ優先
幅優先ないし反復深化深さ優先探索で解いてやればいいのはすぐ分かるのですが、全状態を真面目に探索すると計算量が多すぎて解けません。
フロー
蟻本にも紹介されている問題です。一見最小費用流の問題に見えるのですが、普通に最小費用流で解いたのではTLEになります。やり方は蟻本を参考にしてください。
幾何
幾何の入門問題として良いと思います。距離を二乗してlong longの分数で数を持つようにすれば、適当に計算しても解けますが、doubleで計算する場合は誤差に注意が必要です。