「第20回オフラインリアルタイムどう書く」のへなちょこ解答（Java）

どう書く

土曜の夜、どう書くに行ってきました。

オフラインリアルタイムどう書くとは
鍋谷さんが出してくださるお題を、参加者が好きなプログラミング言語で解いて楽しむ会です。

記念すべき第20回目でしたが、残念ながら時間切れで負けてしまいました。

家で続きを書いて解答を完成させたので、載せておきます。

問題

今回は、「会議の時間」です！

芦ノ牧さん、馬場崎さん、印旛沼さん、陣場山さんは、1時間の会議を開催しようとしています。

芦ノ牧さんと馬場崎さんは出席必須。印旛沼さんと陣場山さんは、どちらかが出席できればOKです。

座間川さんという呼ばれもしないのにやって来て会議をめちゃくちゃにしてしまう人ｗ がいますので、座間川さんが忙しい時間帯に開催したいです。

各人のスケジュールを入力として、開催可能な最も早期の時間帯を1つ出力してください。

……という問題でした。詳細は、上の問題ページをご確認ください。

自分の解答

Javaです。

import java.util.*;

public class Meetime {

	public String solve(String input) {
		Map<Character, boolean[]> schedule = parse(input);
		List<Integer> meeting = new ArrayList<>();

		meeting = check(schedule.get('A'), schedule.get('B'),
				schedule.get('I'), schedule.get('Z'), meeting);
		meeting = check(schedule.get('A'), schedule.get('B'),
				schedule.get('J'), schedule.get('Z'), meeting);

		Collections.sort(meeting);

		if (0 < meeting.size()) {
			return convertToTime(meeting.get(0)) + "-"
					+ convertToTime(meeting.get(0) + 60);
		}
		return "-";
	}

	List<Integer> check(boolean[] as, boolean[] bs, boolean[] xs, boolean[] zs,
			List<Integer> meeting) {
		int beginIndex = 0;
		int tmp = 0;
		for (int i = 60 * 10; i < 60 * 18; i++) {
			if (tmp == 0) {
				beginIndex = i;
			}
			if (as[i] == false && bs[i] == false && xs[i] == false && zs[i]) {
				tmp++;
			} else {
				tmp = 0;
				beginIndex = 0;
			}
			if (59 < tmp) {
				meeting.add(beginIndex);
				tmp = 0;
				beginIndex = 0;
			}
		}
		return meeting;
	}

	Map<Character, boolean[]> initSchedule() {
		Map<Character, boolean[]> result = new HashMap<>();
		result.put('A', new boolean[1440]);
		result.put('B', new boolean[1440]);
		result.put('I', new boolean[1440]);
		result.put('J', new boolean[1440]);
		result.put('Z', new boolean[1440]);
		return result;
	}

	Map<Character, boolean[]> parse(String input) {
		Map<Character, boolean[]> result = initSchedule();
		String[] split = input.split(",");
		for (String str : split) {
			char name = str.charAt(0);
			boolean[] schedule = result.get(name);
			schedule = fill(schedule, convertToIndex(str.substring(1, 5)),
					convertToIndex(str.substring(6, 10)));
			result.put(name, schedule);
		}
		return result;
	}

	boolean[] fill(boolean[] schedule, int begin, int end) {
		for (int i = begin; i < end; i++) {
			schedule[i] = true;
		}
		return schedule;
	}

	String convertToTime(int index) {
		int hour = index / 60;
		int minute = index % 60;
		return String.format("%02d", hour) + String.format("%02d", minute);
	}

	int convertToIndex(String time) {
		int hour = Integer.parseInt(time.substring(0, 2));
		int minute = Integer.parseInt(time.substring(2, 4));
		return hour * 60 + minute;
	}
}

考え方

まず、60分×24時間個の要素を持つboolean配列を人数分用意します。

次に、予定がある時間帯をtrueで塗りつぶしていきます。

最後に、全員の配列を10時から18時の位置まで走査して、60分の連続した「空き（false）」のチャンクを探します。

  • その際、座間川さんに「予定があること（true）」を条件に加えます。
  • 印旛沼さんと陣場山さんのスケジュール調整については後述します。

後から直した箇所

印旛沼さんと陣場山さんのスケジュール調整

「印旛沼さんと陣場山さんはどちらかが出席すればOK」という制約を表現するために、当日はAND条件やOR条件を沢山つなげて混乱していました。

しかし、「芦ノ牧さん、馬場崎さん、印旛沼さん」と「芦ノ牧さん、馬場崎さん、陣場山さん」の両方で空き時間を探して、最も早い時間帯を解答とすればよい、とのアドバイスいただき、そりゃそーだと思って書き直しました。

String.format

配列のインデックス値を、時間を表わす文字列に変換するメソッドを、当日は次のように書いていました。

Before

	String convertToTime(int index) {
		int hour = index / 60;
		String tmpHour = Integer.toString(hour);
		if (hour < 10) {
			tmpHour = "0" + tmpHour;
		}
		int minute = index % 60;
		String tmpMinute = Integer.toString(minute);
		if (minute < 10) {
			tmpMinute = "0" + tmpMinute;
		}
		return tmpHour + tmpMinute;
	}

が、String.format使えや、というもっともなツッコミをいただいたので、コッソリ直しておきました。

After

	String convertToTime(int index) {
		int hour = index / 60;
		int minute = index % 60;
		return String.format("%02d", hour) + String.format("%02d", minute);
	}

改善できそうな箇所

Java 8を使うには、配列にインデックスアクセスしているようではいけません。それ以前に、1440個の要素を持つboolean配列を作っている時点で疑問を持つべきという話もあります。boolean配列でなく文字列にしてみました。「第20回オフラインリアルタイムどう書く」の解答（改善？編） - 虎塚

あらかじめ人数分の配列を作るのではなく、走査を1回だけにして、あるタイミング（分）ごとに、「お前今ヒマ？」と全員に確認するメソッド（おまひまメソッド）を作るとよいかもしれません。よくわかりませんが……。

（よかったら、誰かアドバイスください）

そんなわけで、またしても負けてしまいましたが、今回も楽しかったです。ありがとうございました。