Hatena::Grouptopcoder

Hiro180の日記

 | 

2017-06-18

AOJ-ICPC埋め (2nd) 15:02

面白かったのをピックアップします。

鎖中経路 (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で徐々につなげていって最大値を求める。

 |