第四問を解き直します。
こちらが問題。本当に基本的な2ケース以外全て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();

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

		for (int i = 1; i <= n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			map.get(i).putZahyo(a, b, c);
		}
		// 入力完了

		for (int i = 1; i <= n; i++) {
			boolean isInside = false;
			P point = map.get(i);
			for (int j = 1; j <= n; j++) {
				if (map.get(j).isInside(point)) {
					isInside = true;
				}

			}
			System.out.println(isInside ? "Yes" : "No");
		}
	}

}

class P {
	private int myNum;

	private ArrayList<Integer> zahyo = new ArrayList<>();

	P(int a) {
		myNum = a;
	}

	public void putZahyo(int x, int y, int z) {
		zahyo.add(x);
		zahyo.add(y);
		zahyo.add(z);

	}

	public ArrayList<Integer> getZahyo() {
		return zahyo;
	}

	public boolean isInside(P point) {
		return point.getZahyo().get(0) > zahyo.get(0) && point.getZahyo().get(1) > zahyo.get(1)
				&& point.getZahyo().get(2) > zahyo.get(2);
	}

このような流れで改善していきました。
・Pをnewする→座標を代入をひとまとめに行う
・Pのコンストラクタ廃止、あわせてmyNumも不要なので廃止
・List<>()は重いので、intを3つフィールドで持つように修正
・そもそもクラスPを廃止して、Mapに直接intの配列をいれてみた
これで18/29・・・道のりは長い。。

public class Main {

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

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

		IntStream.rangeClosed(1, n).forEach(i -> map.put(i, new int[] { sc.nextInt(), sc.nextInt(), sc.nextInt() }));
		sc.close();

		// 入力完了
		for (int i = 1; i <= n; i++) {
			boolean isInside = false;
			int[] point = map.get(i);
			for (int j = 1; j <= n; j++) {
				int[] point2 = map.get(j);
				if (point[0] > point2[0] && point[1] > point2[1] && point[2] > point2[2]) {
					isInside = true;
					break;
				}
			}
			System.out.println(isInside ? "Yes" : "No");
		}
	}
}

今後いろいろ改良を試みましたが無理!!
今の自分の実力では無理・・・でした、、orz

著者

コウ

PG Battle2019解き直し~その3~ Comment

  1. これは非常に難しいです。
    予め与えられる点の順番を並び替えることができない二次元の問題にまず取り組むと見通しが良いです。以下の操作が高速にできれば良いです。
    ① 点(x,y)を集合に追加する
    ② 現集合内に点(x’,y’) (x'<x,y'<x)が存在するか答える

    この操作はオンライン区間最小値問題が解ければ解けます(RMQという単語で調べると良いでしょう。長さnの配列の区間に対する値の更新、最小値問い合わせがO(log n)でできます)

    各xに対するyの値の最小値を列に記録して、②で(x',y')が与えられたときには、列のx'番目未満の全ての要素に対して最小のyを調べ、それがy'未満であるかどうか確かめればよいです。

    ちなみに、x'未満の要素に対する問い合わせしか来ないつまり、区間が常に[0,x')の形になるので、BIT(Binary indexed tree)と呼ばれるより実装が単純(発想は技巧的)なもので代用することもできます。RMQ含めこのあたりの話はプログラミングコンテストチャレンジブックで全て学べるのでぜひ調べてみてください。

    これをどうやってもとの問題で応用するかですが、三次元のz軸でソートしてみると二次元の問題に帰着できます。

    さすらい

コメントを残す