がめつく行こう、貪欲法（ABC141-D解きました）Java,C++,Python

今回は貪欲法を利用する問題である、ABC141のD問題を解いたので、復習がてら書いていきます。

　問題に入る前に、貪欲法って何？という方に向けて頑張って説明してみる。貪欲法とは文字通り、ある基準において最適な解となるものを貪欲に選び続けていくアルゴリズムです。例えば、下のような問題を考えてみます。

問題

n個ある商品のうちｋ個買うとき、価値が最大となるのはどのような買い方か？

入力

n k

v_1 v_2 ..... v_n

ちょっと簡単すぎましたね（汗）。

この問題の答えはお分かりの通り、価値v_iの大きい順にk個選んでそれを出力すれば良いだけです。

　このように、とてもシンプルなアルゴリズムなのですが、問題なのは実装。毎回要素をループで調べてから云々してると絶対に間に合わないので、あるものを使って高速化します。その名も、優先度付きキュー！！このキューはとっても便利なもので、先に入れたものが先に出てくる一般的なキューとは異なり、こちらは指定した条件の中で最適となる要素を先に出してくれます！正に貪欲法のために生まれてきたといっても過言じゃない！（過言かもしれない...）では、上の問題の答えを実装してみましょう！
Java

import java.util.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.math.RoundingMode;
import java.math.BigDecimal;
 
 
public class Main{
	 public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		String ans = "";
		//優先度付きキュー
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		//要素を入れる
		for(int i = 0; i < n; i++) {
			int v = sc.nextInt();
			pq.add(v);
		}
		for(int i = 0; i < k; i++) {
			int v = pq.poll();
			//出力データを作る
			if(i==0)ans += v;
			else ans += " " + v;
		}
		System.out.println(ans);
	 }
}

C++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
 
int main() {
    int n,k;
    cin>>n>>k;
    string ans = "";
   priority_queue<int> pq;
   rep(i,n){
       int v;
       cin>>v;
       pq.push(v);
   }
   rep(i,k){
       int v = pq.top();
        pq.pop();
        cout<<v<<" ";
   }
}

Python

import heapq

n, k = map(int, input().split())
ans = ""
v = [int(input())*(-1) for i in range(n)]
heapq.heapify(v)
print("答えは")
for i in range(k):
    print(heapq.heappop(v)*(-1)

注：Pythonだけ入力と出力の仕方が違いますが、結果の数値自体は同じです。慣れてないの許して
因みに、Pythonでvの入力時に-1倍しているのは、heapq自体が昇順（小→大の順）に並べるもので、入力値を-1倍した後、出力するときにもう一度-1倍すれば降順で処理しているように扱えるからです。
　さて、ここまでで貪欲法の実装までやりましたので、今回の問題を見てみましょう。

問題文
高橋くんはN個の品物を1個ずつ順番に買う予定です。i番目に買う品物の値段は A_i円です。
高橋くんはM枚の割引券を持っています。
品物を買う際に割引券を好きな枚数使うことができます。
X円の品物を買う際にY枚の割引券を使った場合、その品物をX/(2^Y)円(小数点以下切り捨て)で買うことができます。
最小で何円あれば全ての品物を買うことができるでしょうか。

この問題、
少し考えれば分かるかと思いますが、一番高いものから順に割引券を使っていけばいいので、上の例題のコードの出力のループの中をちょちょいといじってあげればおｋ。ということで、僕が実際に書いたコードは下のJavaのやーつ。

リンク
atcoder.jp

import java.util.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.math.RoundingMode;
import java.math.BigDecimal;
 
 
public class Main{
	 public static void main(String[] args){
	   Scanner sc = new Scanner(System.in);
	   int n = sc.nextInt();
	   long m = sc.nextLong();
	   PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
	   for(int i = 0; i < n; i++) {
		   long a = sc.nextLong();
		   pq.add(a);
	   }
	   for(int i=0; i<m; i++){
			Long a = pq.poll();
			a = a/2;
			pq.add(a);
		}
	   long ans = 0;
		while(pq.size() > 0){
			ans += pq.poll();
		}
		System.out.println(ans);
	  }
	}

C++とかPythonは順次書いていく予定です。
　最後に注意点をば。ここまで貪欲法いいよ～って感じで書いてきましたが、体感としてはこれを使わない方が多いかと思います。というのも、最適解を取っていくだけでは考察が不十分となる問題の方がよく出ている気がするからです。下のリンク先の問題なんかは値がでかいヤツばっか取ってたら普通にWAです。貪欲法を使う際は、使う前に本当に正しいのか一考する必要がありますね。
atcoder.jp
　以上で貪欲法の紹介を終わります。自分で問題を作って3種類の言語でコードを書くのが意外と大変でしたが大分勉強になりました。後、今回初めてはてな記法で書いてみたんですけどどうですかね？個人的にはこれからははてな記法で書こうかなと思っています。
では今回はこの辺で。さいなら～。