結果

問題 No.382 シャイな人たち (2)
ユーザー 37zigen37zigen
提出日時 2016-06-23 21:07:18
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 4,879 bytes
コンパイル時間 2,511 ms
コンパイル使用メモリ 85,624 KB
実行使用メモリ 142,108 KB
最終ジャッジ日時 2024-04-19 23:58:08
合計ジャッジ時間 21,432 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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) {
		long S=System.currentTimeMillis();
		new Main().solver();
		long T=System.currentTimeMillis();
		System.err.println((T-S)+"ms");
	}

	void solver() {
		Scanner sc = new Scanner(System.in);
		long S = sc.nextLong();
		Graph g = set_edge(S);
		Pair p=ms(g);
		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;
			}
		}
	
	}

	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[i];
				if (deg_me_min <= 1) {
					g.delete_v_with_neighbours(i);
					Pair p= ms(g);
					p.choosed_vertices[i]=true;
					p.cardinality++;
					return p;
				}
				deg_to_max = deg[e[A].get(0)];
				B = e[A].get(0);
				for (int j = 0; j < e[A].size(); j++) {
					int u = e[A].get(j);
					if (!valid_vertices[u])
						continue;
					if (deg[u] > deg_to_max) {
						B = u;
						deg_to_max = deg[u];
					}
				}
			} else if (deg[i] == deg_me_min) {
				for (int j = 0; j < e[A].size(); j++) {
					int u = e[A].get(j);
					if (!valid_vertices[u])
						continue;
					if (deg[u] > deg_to_max) {
						B = u;
						A = i;
						deg_to_max = deg[u];
					}
				}
			}
		}
		

		
		if (A == -1 && B == -1)
			return new Pair(0,new boolean[n]);
		if(dominance(A,B,g)){
			g.delete_vertice(A);
		}
		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;
		}
		// }
	}
	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;
	}
}
0