今回は3問目を解き直します。
3問目の問題は こちら
自分の回答はTLEだったので性能をよくしたいと思っています。

public class Main {

	public static void main(String[] args) {
		HashMap<Integer, P> map = new HashMap<>();

		Scanner sc = new Scanner(System.in);
		int result = 0;
		// 整数の入力
		int n = sc.nextInt();
		int m = sc.nextInt();

		IntStream.rangeClosed(0, n).forEach(i -> map.put(i, new P(i)));

		for (int i = 1; i <= m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			map.get(a).putNext(b);
		}
		// 高橋君
		map.get(0).putNext(0);
		// 入力完了

		for (int i = 1; i <= n; i++) {
			boolean isOK = false;
			for (int first : map.get(i).getNext()) {
				for (int second : map.get(first).getNext()) {
					for (int third : map.get(second).getNext()) {
						if (third == 0) {
							isOK = true;
						}
					}
				}
			}
			System.out.println(isOK ? "Yes" : "No");

		}
	}

}

class P {
	private int myNum;

	private HashSet<Integer> set = new HashSet<>();

	P(int a) {
		myNum = a;
	}

	public void putNext(int next) {
		set.add(next);
	}

	public HashSet<Integer> getNext() {
		return set;
	}

}

クラスPを廃止してそのままHashSetにしたのと、最後でcontainsを使用してなんとかTLEじゃなくなりました。(1990ms、ぎりぎり)
printResultで、if文の中に入った場合にYesと出力してreturn;と書いてみたのですが、こちらだとなぜかTLE・・・なぜかはよく分からないです。。

public class Main {

	public static void main(String[] args) {
		HashMap<Integer, HashSet<Integer>> map = new HashMap<>();

		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
		int m = sc.nextInt();

		IntStream.rangeClosed(0, n).forEach(i -> map.put(i, new HashSet<>()));

		for (int i = 1; i <= m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			map.get(a).add(b);
		}
		// 高橋君
		map.get(0).add(0);
		// 入力完了

		for (int i = 1; i <= n; i++) {
			printResult(i,map);
		}
	}
	
	public static void printResult(int i, HashMap<Integer, HashSet<Integer>> map ) {
		boolean isOK = false;
		for (int first : map.get(i)) {
			for (int second : map.get(first)) {
				if (map.get(second).contains(0)) {
					isOK = true;
				}
			}
		}
		System.out.println(isOK ? "Yes" : "No");
	}
}

う~ん、、TLEとの闘いはなかなか大変そうです。これだけでも結構時間かかってしまいました。
そもそもどうやれば効率よく処理できるかのセオリーの勉強が完全に足りない気がします。。引き続き精進します・・・

著者

コウ

3 Comments

  1. この問題をゴリ押しで通してしまうあたり非常にプログラミング能力の高い方だとお見受けします。この問題は単一始点の最短経路問題と呼ばれる有名なアルゴリズムの問題で、解法にはベルマンフォード法や、ダイクストラ法などがあります。非常に汎用的な手法なので、是非調べてみると解ける問題の幅がグンと広がりますよ!実装の能力と改善の地力が感じられるので、サクッとものにできると思います。

    さすらい
  2. さすらいさん

    コメントありがとうございます!
    お褒めいただき恐縮です・・・ちょっとベルマンフォード法とダイクストラ法調べてみましたが難しいですね、、
    複雑さと計算量は全く違うんですね。あたりまえですが今回実感しました。
    ダイクストラ法をちょっと応用して、経路の重さが1で、3回までしか深追いしないみたいな感じで実装すればいいんですかね。。

    せっかくなんで来週末にでも解きなおしてみたいと思います!

    コウ
  3. […] こちらの記事 でPGBattleの第三問を解きなおしてみたのですが、コメント欄にてダイキストラ法というものがあると知り、この問題用に最適化して書いて再挑戦しました。なかなか手を付 […]

    PG Battle2019解き直し~その4~ | いにこみ。

コメントを残す