AtCoder500点, 貪欲法, 後ろから選択肢を選ぶ

問題へのリンク

問題概要

N日間のうちK日働く。

一日働いたら、直後のC日間働けない
i+1 日目は、Sの i 文字目が ‘o’ の時だけ働ける

必ず働く日を全て求めよ。 ...

グラフグラフ, 貪欲法, 最小全域木, プリム法

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月23日グラフグラフ, 貪欲法, クラスカル法, 最小全域木

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月7日グラフグラフ, 競プロ, 重み付きグラフ, 単一始点最短経路, 最短経路, ダイクストラ法, ヒープ, 優先度付きキュー, 貪欲法

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては

計算量が \(O(|E| \l ...

2020年1月19日貪欲法入門, 競プロ, 貪欲法

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。

その場での最善の手を選ぶことを繰り返す

貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いので非常に重要です。

大まか ...