7K12 blog

猫でも分かるアルゴリズム解説

2020-07-08から1日間の記事一覧

ABC157 D - Friend Suggestions

https://atcoder.jp/contests/abc157/submissions/13265285 芋づる式の構造は Union-Find (disjoint-set) にするのが典型テクニック union-findと「二次元」配列を組み合わせて計算量を落とす 二次元配列で細かく区切ることで無駄を無くす i番目の人に対する…

第8回日本情報オリンピック 本選 B - ピザ

https://atcoder.jp/contests/joi2009ho/submissions/14908294 左回りと右回りの両方を二分探索する 左回りは upper_bound 右回りは upper_bound をデクリメントすると得られる 円環はデータを余分に増やすと実装が楽になることが多い 制約から二分探索で処…

AOJ ALDS1_4_B Binary Search

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4632584 lower_boundとupper_boundを比較することで値が存在するか分かる lower_bound(x) == upper_bound(x) 値xが存在しない lower_bound(x) != upper_bound(x) 値xが存在する 制約からはTLEするので…