【Python】AtCoderの問題から学ぶ貪欲法の基本

スポンサーリンク
AtCoder
スポンサーリンク

今回は、AtCoderのキーエンスプログラミングコンテスト問題Bを解いて、貪欲法について勉強したことをまとめたいと思います。

スポンサーリンク

貪欲法とは

貪欲法はあるルールを定めて、最適な要素を順番に選択していくアルゴリズムです。動的計画法のように、一度選択した要素を再考することはありません。

例えば、500円玉を1枚、100円玉を5枚、50円玉を3枚持っていて、出来るだけ少ない枚数で600円支払うことを考えます。この場合、「できるだけ金額の大きな硬貨から出す」というルールを定め、 500円玉→100円玉の順に選ぶと最小の枚数になります。

問題

ある工場では、 数直線上に N 個のロボットが設置されています。 ロボット i は座標 Xi に設置されており、数直線の正負の方向にそれぞれ長さ Li の腕を伸ばすことができます。

これらのロボットのうちいくつか (0 個以上) を取り除き、 残ったどの 2 つのロボットについても、腕が動く範囲が共通部分を持たないようにしたいと思います。 ただし、各 i (1≤i≤N) に対して、 ロボット i の腕が動く範囲とは 数直線上の座標が Xi−Li より大きく Xi+Li 未満の部分を指します。

取り除かずに残せるロボットの個数の最大値を求めてください。

上の図のように、区間がかぶるロボットを除いて、出来るだけ多くのロボットを残せるようにします。

まず、どういうルールで残すロボットを決めるか考えます。

ルールの候補としては、

  1. 区間が狭いものから選ぶ
  2. 出来るだけ他のロボットと区間が被らないものを選ぶ
  3. 始点が左端のものから選ぶ
  4. 終点が左端のものから選ぶ

1〜4それぞれの反例を考えてみます。

  • 1番の場合の反例
  • 2番の場合の反例

2番の場合も最適でない選び方をする可能性があります。

  • 3番の場合の反例
  • 4番

一方、4番のルールでは、終点の位置でソートすることで、無駄なく選ぶことができそうです。

4番のルールに従って、問題を解くことにします。

タイトルとURLをコピーしました