hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

蟻本練習問題解説 Part2 (2-2)

蟻本練習問題の解説をします。今回のトピックは貪欲法です!

シリーズ目次はこちらからどうぞ。

tsutaj.hatenablog.com

猪突猛進! "貪欲法"

区間

POJ 2376: Cleaning Shifts

問題リンク

区間 N 個あり、 i 番目の区間 \left[ l_{i}, r_{i} \right] の閉区間である。これらの区間の中からいくつかを選び、 \left[ 1, T \right] を全て被覆したい。そのようなことが可能であれば選ぶ区間の数の最小値を、不可能であれば  -1 と答えよ。

▶表示する

POJ 1328: Radar Installation

問題リンク

2 次元平面上に点が  N 個ある。いくつかの円を用意して、全ての点を囲みたい (点が円周上にあっても、それは囲まれていると見なす)。円は半径が  d で固定であり、中心は必ず  x 軸上になければならない。このようなことが可能ならば用意する円の個数の最小値を、不可能であれば  -1 を出力せよ。

▶表示する

POJ 3190: Stall Reservations

問題リンク

区間 N 個あり、 i 番目の区間 \left[ a_{i}, b_{i} \right] と表される。何回かの操作をしてこの区間を全て取りたい。  1 回の操作では、overlap しない範囲でいくつでも区間を取ることができる (終点と始点の overlap も許されない。つまり取る区間それぞれについて  b_{p} \lt a_{q} (p \neq q, a_{p} \lt a_{q}) を満たす)。このとき、操作の最小回数と、それぞれの区間について何回目の操作で取ったかを求めよ。

▶表示する

その他

POJ 2393: Yogurt factory

問題リンク

ヨーグルト工場では、ヨーグルトの製造・配送・貯蔵を行っている。 i 週目にヨーグルトを  1 つ製造するには  C_{i} 円がかかり、またその週には  Y_{i} 個を配送しなければならないことがわかっている。ヨーグルトを  1 週間貯蔵するには  1 つあたり  S 円がかかる。貯蔵に期限や個数の上限はない。 N 週間の予定が与えられるので、配送の予定を全てクリアするときのコストの最小値を求めよ。

▶表示する

POJ 1017: Packets

問題リンク

 1 \times 1, 2 \times 2, \dots, 6 \times 6 6 種類の正方形がいくつかある。これらを全て、  6 \times 6 のいくつかの領域の中に重なりのないように敷き詰めたい。このとき、必要な  6 \times 6 領域の最小個数を求めよ。

▶表示する

POJ 3040: Allowance

問題リンク

あなたはコインを  N 種類持っている。具体的には、 V_{i} 円のコインを  B_{i} 円持っている。コインの価格は小さい順に並べると倍数列 (すなわち、あるコインの価格はその次に価格が低いコインの倍数) である。手持ちから  C 円以上の金額を何回か払うことを考えるとき、払える回数の最大値を求めよ。

▶表示する

POJ 1862: Stripies

問題リンク

 N 匹の生き物がおり、 i 番目の生き物の体重は  w_{i} である。体重が  w_{i}, w_{j} である  2 匹の生き物同士がぶつかると、元いた生き物は消え、新たに体重  2 \times \sqrt{w_{i} w_{j}} の生き物が  1 匹現れる。生き物がぶつかって最終的に  1 匹だけになるとき、最後に残った生き物の体重の最小値を求めよ。

▶表示する

POJ 3262: Protecting the Flowers

問題リンク

牛が  N 頭おり、 i 番目の牛は座標  T_{i} (\gt 0) におり、単位時間あたり  D_{i} だけ花を食べている。牛を  1 頭ずつ納屋に帰すことを考える。納屋は座標  0 にあるため、帰すには (納屋から牛のところまで行く) + (牛のところから納屋に帰る) で  2T かかり、帰す対象の牛は待っている間も、帰っている間も花を食べない。このとき、全ての牛が納屋に帰るまでに食べられる花の量の合計を最小化せよ。

▶表示する

次回は動的計画法を解説します!