アルゴリズム

配列が与えられた時、N個からなる最大値/最小値を求める

ABC 62-Dの3N Numbersを解いてるときに、N個からなる最大値/最小値を求める必要があったのでメモしときます。 Priority Queueを使う。 Priority Queueで実装できます。基本的なロジックは 最初のN個をPQにいれる。 PQの中にある合計を記録する変数(sum)を用…

ABC 60-D Simple Knapsack

こんにちは。今日はABC60でしたね。 D問題はナップザックだと思って以下のようなコードを書いたのですが、WAだったので自分のコードがWAするテストケースを考えました。 public static long solve(int index, long weight, long value) { String s = index +…

ABC 22-C Blue bird

重りつきのグラフが与えられ、スタート地点から出発しスタート地点へ戻ってくる最短の道のりを答える問題。 C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder 最初はダイクストラに通った道を記憶させ、それを通らないようにするんだと思って実装する…

階乗の素因数分解の仕方

ABC第52回のFactors of Factorialという問題を解いていたのですが、階乗の素因数分解をする必要がありました。やり方をしらなかったので、その方法のメモです。 この問題の答えを最初intで保持していたためinputが1000のときに正しい答えを得られず1時間ほど…

強連結成分分解においてどうしてスタックにあることを確かめる必要があるのか

強連結成分分解(SCC)を発見するTarjanアルゴリズムを学んでいたのですが、どうしてスタックにあるかどうかを確認する必要があるかがわからなかったのでその答えです。 答えを確かめるためにUVa 247を使いました。僕が解くために書いたソースコードは以下のと…

関節点で訪れたノードのとき、どうしてdfs_lowではなくdfs_numを使うのか

Articulation pointsのアルゴリズムを勉強してるときに、訪れたノードの処理でどうしてdfs_numを使うのだろう。dfs_lowではダメなのかと思ったので、その解説記事です。 僕が問題を解くために書いたソースコードです。実装が正しいかを確かめるためにUVa 315…