priority_queue

このタグの解説について

この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

競技プログラミング日記•1年前

PAST15 J問題

PAST15J 問題の言い換えダメージの累計が最小になる様に手裏剣を使う．思考の流れいくつか思いつくことがある．まず暫定的な答えを出す．これは簡単に求まるというのが大事．手裏剣を 0枚使ったときの求めて，その答えを修正していく．手裏剣 1枚でどれくらい得をするのかを考える．敵が 1体のときに，\(x = 0, 1\) で場合分けして考える．敵が \(N\) 体で，全て \(x = 0\) の場合を考える． \(x = 1\) の場合は，手裏剣を投げることで \(x=0\) に帰着できるから．それぞれについて詳しく見ていく．敵が 1体のとする．手裏剣を \(u\) 枚使ったと…

#PAST#アルゴリズム実技検定#priority_queue#場合分け#暫定の答えを修正

関連ブログ

競技プログラミング日記•1年前

PAST14 L問題

PAST14L 準備 \(A\) が \(B\) より強いと分かっているとき，かつそのときに限り \(A\) から \(B\) に矢を張ったグラフ \(G\) を考える．問題 Easy 辞書順を無視して，強い順に並べる．これは \(G\) においてトポロジカルソートするのと同じ． Normal(本問) 辞書順最小の，強い順に並べる．トポロジカルソートで頂点を並べるとき，選ぶ頂点の候補が複数あれば最小の物を選ぶようにすればよい．これは，入次数 0 の頂点を入れる入れ物として， min priority queue を用いれば良い．使っている記号，マクロ等 "https://ecsmt…

#アルゴリズム実技#PAST#トポロジカルソート#priority_queue

競技プログラミング日記•2年前

AtCoder Beginner Contest 217E

ABC217E ソートの部分を速く済ませるのが課題．毎回ソートするのではなく，必要な部分だけソートして，そうでないときはソートを保留しておきたい． priority queue を用いると，各元を追加したときに同時にソートされた形になる．追加に \(O(log(size(que)))\) がかかる．実装:\(b\) を priority queue, \(a\) を queue とする．組 \( (b,a) \) を，vector \(b * a\) と同一視する．ここで，\(b * a\) は \(b\) の元の後ろに \(a\) の元を並べた vector. もちろん，実装は…

#query#priority_queue#AtCoder#AtCoder Beginner Contest