貪欲法について

今回もAtCoderについての記事です。
D問題がまだ本番で1問も解けていないのが悔しいので、今週末のABC2連に向けて頑張ります。

前回に引き続き、AtCoderの勉強をしました。
ちなみに前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

前回のABCの参加記録はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

貪欲法とは

貪欲法とは、あるルールに従ってその都度最適なものをとっていく手法です。
例えば、有名なA - おつりのようなコインの問題では、コインの枚数が少なくなるように、コインの額が大きいほうからおつりをコインに変えていくというルールに従って、最小のコインの枚数を求めます。
アルゴリズムとしては単純なほうなので分かりやすいです。
基本的には決まったアルゴリズムはありませんが、いくつ決まったパターンがあります。
それが、以下のようなものです。

• 区間スケジューリング問題
• 辞書順の問題

今回は決まった解法があるこの2種類の問題に対する解き方を次の項目に書きます。

どのように解くのか（Javaの場合）

参考にしたサイトは以下のサイトです。
ここに記載されている問題のうち、2問をJavaで解いたものを載せます。
（コードが拙いのは見逃してください）
qiita.com

区間スケジューリング問題

区間スケジューリング問題は終端をソートしていくものです。
これは知らないとなかなか出ない発想なので、勉強してよかったです。
解いた問題はABC103のD問題 Islands Warです。
atcoder.jp
Atcoder Problemsというサイトで水色diffとなっていますが、おそらくこれを区間スケジューリング問題だと気付けるかが難しいと思います。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		int[][] desire = new int[M][2];
		for(int i=0; i<M; i++) {
			desire[i][0] = sc.nextInt();
			desire[i][1] = sc.nextInt();
		}

		Arrays.sort(desire, (a, b) -> a[1] - b[1]);

		int index = 0;
		int ans = 0;
		while(index < M) {
			int end = desire[index][1];
			ans++;
			index++;

			while(index < M && desire[index][0] < end)
				index++;
		}

		System.out.println(ans);
	}
}

辞書順の問題

辞書順とは、早く辞書に出てくる順番のことです。
a-zだとaのほうに近いほど早く出てきます。
文字が途中まで同じ場合は、文字数が少ないほうが優先されます。

解いた問題はABC076のC問題 Dubious Document 2です。
atcoder.jp

この問題のポイントは辞書順で最小にするために、後ろのほうから一致するか見ていくところだと思います。
あとは、?の部分をaに変えるだけで辞書順が最小にできます。
一致するかの確認方法は後ろから一文字ずつ順にみていけばいいです。
ここで気づいたのですが、JavaのString.replaceとStringBuilder.replaceは中身が全く違うんですね。
indexを指定して決まった範囲を別の文字列に置き換えたいときはStringBuilder.replaceを使うそうです。

import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String S = sc.next();
		String T = sc.next();

		StringBuilder sb = new StringBuilder(S);
		boolean matchAnswer = false;
		for(int i=S.length()-T.length(); i>=0; i--) {
			boolean isMatch = true;

			for(int j=i; j<i+T.length(); j++) {
				if(!(S.charAt(j) == T.charAt(j-i) || S.charAt(j) == '?')) {
					isMatch = false;
					break;
				}
			}

			if(isMatch) {
				sb.replace(i, i+T.length(), T);
				matchAnswer = true;
				break;
			}
		}

		String ans = "UNRESTORABLE";
		if(matchAnswer) {
			ans = sb.toString();
			ans = ans.replace("?", "a");
		}

		System.out.println(ans);
	}
}

フラグを使いまくっていますね。
（もっときれいに書けた気もします。）

ということで、今回の記事は終了です。
個人的には週末のAtCoder Beginner Contest 2連続はチャンスだと思っているので、どちらかでD問題が解けるようにしっかり準備していきたいと思います。