perogram

2019-02-06から1日間の記事一覧

C - ウサギとカメ arc025_3

Quiz https://atcoder.jp/contests/arc025/tasks/arc025_3 Submit https://atcoder.jp/contests/arc025/submissions/4186238 解き方と計算量 ゴールを固定する ゴールから各ノードまでの距離をDijkstraで求める O( (N+M)logN ) 距離をソート O(NlogN) (a) 亀…

B - チョコレート (arc025_2)

Quiz https://atcoder.jp/contests/arc025/tasks/arc025_2 Submit https://atcoder.jp/contests/arc025/submissions/4184320 Note どちらかの色の値を反転しておく 矩形和=0なら濃度が同じ 二次元累積和で、矩形和をO(1)で求まるようにしておく 検索用ワー…

E - Treeone (qupc2018_e)

Quiz https://atcoder.jp/contests/qupc2018/tasks/qupc2018_e Submit https://atcoder.jp/contests/qupc2018/submissions/4183484 定義 入力A (配列) 累積和Ac (配列) 部分和が0になる個数 Za (配列) 解法 累積和を求める 累積和の中に同じ数が出現したら、…

D - Novelist qupc2018_d

Quiz https://atcoder.jp/contests/qupc2018/tasks/qupc2018_d Submit https://atcoder.jp/contests/qupc2018/submissions/4181446 Note 行きで出発したら一番速い便で帰ってくればいい 出発日と帰宅日の組を作ったら(下図ピンクの線)、もう都市の情報は忘…