TCO 2012 Round 2C

能力相応の完敗につき、敗退。

300

N都市を巡回するときに、一番近い都市を貪欲に選択することを考える。一つの道だけコストを変更して妨害することを考えるとき、移動コストの総計の最大値を答えよ、という問題。

全部の道について、影響が出るような改変(他の道のどれかと同じか、1だけコストを小さくする)を試して貪欲に計算した結果を答えれば良いらしい。

貪欲の最中で、パスが変わり得るものを試しつつ貪欲を継続するという方針でやるとTLEの心配はなくなるが考慮漏れが多くてひどいことになる。

500

二次元平面状にあるたくさんの点について、三点の位置関係が指定された通りに並んでいるものの組み合わせは何通りあるか答えよ、という問題。

二点の位置関係をSegtreeか何かで覚えておいて、それを三点に拡張すれば良いらしい。中心の点から見た位置関係と、下の点から見た位置関係の両方が必要。

900

見てない。