2017-06-18
■ AOJ-ICPC埋め (2nd)
面白かったのをピックアップします。
鎖中経路 (550pts)
中心&交点を列挙してdijkstraする。辺を貼れる条件の言いかえが結構難しい。
ぼくのかんがえたさいきょうのおふとん (550pts)
dp[mask] = (maskに含まれる布団のぬくもりの和をSとするとき、maskに含まれる布団のあり得る順番すべてに対して需要がS以下の日に対する不快度の和の最小値)とすると通る。
Dictionary (550pts)
色々な意味で難しい。dp[L][R][K] = (L~Rの辞書をK文字目以降で辞書順に並べ替える方法の数)とする。
選挙活動 (600pts)
考えるべき点は(人-多角形の頂点)の直線同士の交点のみ。あとはライブラリを貼ってなんとかする。
ICPC Teams (600pts)
これはかなり難しい、あと良問。余事象を考えて包除原理すると制約がsameだけになるのでできる。
Polygon Guards (700pts)
凹多角形と点の包含関係は偏角の和で判定できるらしい。あとは解の上界を見積もって枝狩り探索。
Towns along a Highway (800pts)
探索木の大きさをO(2^N)にしようと考えると解ける。左右から1つずつ決めていくだけ。
回転と書換 (800pts)
区間DPである区間を文字chに変換できるかを求めたあと、2つの区間を持つDPで徐々につなげていって最大値を求める。
