#99760 (Java) No.382 シャイな人たち (2)

• 問題: No.382 シャイな人たち (2)
• ユーザー: 37zigen
• 提出日時: 2016-06-24 12:40:34
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 6,603 ms / 8,000 ms
• コード長: 8,217 bytes
• コンパイル時間: 2,603 ms
• コンパイル使用メモリ: 83,884 KB
• 実行使用メモリ: 61,340 KB
• 最終ジャッジ日時: 2024-10-11 20:29:54
• 合計ジャッジ時間: 119,262 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
other	AC * 21

ソースコード

package yukicoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {

		new Main().solver();
		// new Q382().trial();

	}

	void trial() {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[] d = new int[N - 1];
		for (int i = 0; i < N - 1; i++) {
			d[i] = sc.nextInt();
		}
		Arrays.sort(d);
		for (int i = 0; i < N - 1; i++) {
			System.out.println(d[i]);
		}
	}

	void solver() {
		Scanner sc = new Scanner(System.in);
		long S = sc.nextLong();
		long Start = System.currentTimeMillis();
		Graph g = set_edge(S);
		Pair p = ms(g);
		int n = g.n;
		if (p.cardinality == n) {
			System.out.println(-1);
		} else {
			System.out.println((p.cardinality + 1));
			boolean f = false;
			for (int i = 0; i < p.choosed_vertices.length; i++) {
				if (p.choosed_vertices[i]) {
					System.out.print((!f ? "" : " ") + (i + 1));
					f = true;
				}
			}
			System.out.println();
		}

		long T = System.currentTimeMillis();
		System.err.println((T - Start) + "ms");
	}

	final long MOD = 1000003;

	Graph set_edge(long S) {
		S = (S * 12345) % MOD;
		int N = (int) (S % 120) + 2;
		Graph g = new Graph(N);
		S = (S * 12345) % MOD;
		long P = S;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				S = (S * 12345) % MOD;
				if (S >= P) {
					g.set_edge(i, j);
				}
			}
		}
		return g;
	}

	// 無向グラフ
	class Graph {
		ArrayList<Integer>[] e;
		int n;
		int[] deg;
		boolean[] valid_vertices;// 選ぶことのできる頂点
		boolean[] choosed_vertices;// 選ばれた頂点

		Graph(int n) {
			this.n = n;
			deg = new int[n];
			valid_vertices = new boolean[n];
			choosed_vertices = new boolean[n];
			Arrays.fill(valid_vertices, true);
			e = new ArrayList[n];
			for (int i = 0; i < n; i++) {
				e[i] = new ArrayList<>();
			}
		}

		// 無向グラフの辺a<->を作成
		void set_edge(int a, int b) {
			if (!e[a].contains((Integer) b)) {
				e[a].add(b);
				e[b].add(a);
				deg[a]++;
				deg[b]++;
			}
		}

		// 辺a<->bを消去
		void delete_undirected_edge(int a, int b) {
			e[a].remove((Integer) b);
			e[b].remove((Integer) a);
			deg[a]--;
			deg[b]--;
		}

		// 頂点vを消去
		void delete_vertice(int v) {
			while (e[v].size() > 0) {
				int u = e[v].get(0);
				delete_undirected_edge(u, v);
			}
			valid_vertices[v] = false;
		}

		// 頂点vと、vの隣接頂点を消去
		void delete_v_with_neighbours(int v) {
			while (e[v].size() > 0) {
				int u = e[v].get(0);
				delete_vertice(u);
			}
			delete_vertice(v);
		}

		// deep copy
		Graph copy() {
			Graph g = new Graph(this.n);
			for (int i = 0; i < n; i++) {
				g.deg[i] = deg[i];
			}
			for (int i = 0; i < n; i++) {
				g.valid_vertices[i] = valid_vertices[i];
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < e[i].size(); j++) {
					(g.e[i]).add(e[i].get(j));
				}
			}
			return g;
		}
	}

	Pair ms(Graph g) {

		int[] deg = g.deg;
		ArrayList<Integer>[] e = g.e;
		boolean[] valid_vertices = g.valid_vertices;
		int n = g.n;
		int A = -1;// 最も次数の小さい頂点
		int B = -1;// Aにつながる頂点のうち最も次数の大きいもの
		int deg_me_min = Integer.MAX_VALUE / 4;
		int deg_to_max = -Integer.MAX_VALUE / 4;
		for (int i = 0; i < n; i++) {
			if (!valid_vertices[i])
				continue;
			if (deg[i] < deg_me_min) {
				A = i;
				deg_me_min = deg[A];
				if (deg_me_min <= 1) {
					g.delete_v_with_neighbours(A);
					Pair p = ms(g);
					p.choosed_vertices[A] = true;
					p.cardinality++;
					return p;
				}
				B = e[A].get(0);
				deg_to_max = deg[B];
				for (int j = 1; j < e[A].size(); j++) {
					int u = e[A].get(j);
					if (deg[u] > deg_to_max) {
						B = u;
						deg_to_max = deg[B];
					}
				}
			} else if (deg[i] == deg_me_min) {
				for (int j = 0; j < e[A].size(); j++) {
					int u = e[A].get(j);
					if (deg[u] > deg_to_max) {
						A = i;
						B = u;
						deg_to_max = deg[B];
					}
				}
			}
		}

		if (A == -1 && B == -1)
			return new Pair(0, new boolean[n]);
		if (A == -1 || B == -1)
			throw new AssertionError("A==-1||B==-1");
		if (deg[A] > deg[B])
			throw new AssertionError("deg[A]>deg[B]");
		if (deg[A] == 2) {
			int B2 = -1;
			if(e[A].size()!=2)
				throw new AssertionError("e[A].size!=2");
			if(e[A].get(0)!=B){
				B2=e[A].get(0);
			}else if(e[A].get(1)!=B){
				B2=e[A].get(1);
			}else{
				throw new AssertionError();
			}
			for(int i=0;i<e[B2].size();i++){
				int u=e[B2].get(i);
				if(u==B){
					g.delete_v_with_neighbours(A);
					Pair p=ms(g);
					p.cardinality++;
					p.choosed_vertices[A]=true;
					return p;
				}
			}
			
		}
		if (deg[A] == 3) {
			Graph g2 = g.copy();
			g2.delete_v_with_neighbours(A);
			Pair p2 = ms(g2);
			p2.cardinality++;
			p2.choosed_vertices[A] = true;

			ArrayList<Integer> d = new ArrayList<>();
			for (int i = 0; i < e[A].size(); i++) {
				d.add(e[A].get(i));
			}
			g.delete_vertice(A);
			Pair p1 = ms2(g, A, 0, d);
			return pair_bigger(p1, p2);
		}
		// else if (dominance(B, A, g)) {
		// g.delete_vertice(B);
		// Pair p = ms(g);
		// p.cardinality++;
		// p.choosed_vertices[B] = true;
		// return p;
		// }
		Graph g2 = g.copy();
		g2.delete_v_with_neighbours(B);
		g.delete_vertice(B);
		Pair p1 = ms(g);
		Pair p2 = ms(g2);
		p2.cardinality++;
		p2.choosed_vertices[B] = true;
		if (p1.cardinality > p2.cardinality) {
			return p1;
		} else {
			return p2;
		}
	}

	// 頂点vの隣接頂点から少なくとも二つ使う場合を考える。
	// count==1なら2回目
	// count==0なら1回目
	Pair ms2(Graph g, int v, int count, ArrayList<Integer> neighbour) {
		int[] deg = g.deg;
		ArrayList<Integer>[] e = g.e;
		boolean[] valid_vertices = g.valid_vertices;
		int n = g.n;

		Pair p = new Pair(0, new boolean[n]);
		while (!neighbour.isEmpty()) {
			int u = neighbour.get(0);
			if (!valid_vertices[u]) {
				if (!neighbour.remove((Integer) u)) {
					throw new AssertionError("neighbour dosent have u");
				}
				if (count == 0)
					throw new AssertionError("error");
				continue;
			}
			if (deg[u] <= 1) {
				g.delete_v_with_neighbours(u);
				if (!neighbour.remove((Integer) u)) {
					throw new AssertionError("neighbour dosent have u");
				}
				if (count == 0) {
					Pair p1 = ms2(g, v, (count + 1), neighbour);
					p1.choosed_vertices[u] = true;
					p1.cardinality++;
					return p1;
				} else if (count == 1) {
					Pair p1 = ms(g);
					p1.choosed_vertices[u] = true;
					p1.cardinality++;
					return p1;
				} else {
					throw new AssertionError("error");
				}
			}
			Graph g2 = g.copy();
			g2.delete_v_with_neighbours(u);
			if (!neighbour.remove((Integer) u)) {
				throw new AssertionError("neighbour dosent have u");
			}

			if (count == 0) {
				Pair p2 = ms2(g2, v, (count + 1), neighbour);
				p2.choosed_vertices[u] = true;
				p2.cardinality++;
				p = pair_bigger(p, p2);
			} else if (count == 1) {
				Pair p2 = ms(g2);
				p2.choosed_vertices[u] = true;
				p2.cardinality++;
				p = pair_bigger(p, p2);

			} else {
				throw new AssertionError("error");
			}
		}
		if (neighbour.size() != 0) {
			throw new AssertionError("neighbour.size()==" + neighbour.size());
		}
		return p;
	}

	Pair pair_bigger(Pair p1, Pair p2) {
		return p1.cardinality > p2.cardinality ? p1 : p2;
	}

	class Pair {
		int cardinality;
		boolean[] choosed_vertices;

		Pair(int cardinality, boolean[] choosed_vertices) {
			this.cardinality = cardinality;
			this.choosed_vertices = choosed_vertices;
		}
	}

	// whethere N(B)&B is subset of N(A)&A or not;
	boolean dominance(int A, int B, Graph g) {
		Set<Integer>as = new HashSet<>();
		Set<Integer> bs = new HashSet<>();
		ArrayList<Integer>[] e = g.e;
		for (int i = 0; i < e[A].size(); i++) {
			as.add(e[A].get(i));
		}
		for (int i = 0; i < e[B].size(); i++) {
			bs.add(e[B].get(i));
		}

		if (!as.contains(B)) {
			as.add(B);
		}
		if (!bs.contains(A)) {
			bs.add(A);
		}

		if (as.size() < bs.size())
			return false;

		for (Iterator<Integer> it = bs.iterator(); it.hasNext();) {
			if (!as.contains(it.next())) {
				return false;
			}
		}
		return true;
	}
}