#99797 (Java21) No.382 シャイな人たち (2)

• 問題: No.382 シャイな人たち (2)
• ユーザー: 37zigen
• 提出日時: 2016-06-24 22:24:03
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 5,764 ms / 8,000 ms
• コード長: 11,072 bytes
• コンパイル時間: 4,719 ms
• コンパイル使用メモリ: 87,504 KB
• 実行使用メモリ: 60,700 KB
• 最終ジャッジ日時: 2024-04-20 02:21:38
• 合計ジャッジ時間: 102,499 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	5,764 ms; 58,720 KB
testcase_01	AC	5,522 ms; 59,540 KB
testcase_02	AC	4,617 ms; 59,428 KB
testcase_03	AC	5,670 ms; 58,960 KB
testcase_04	AC	4,268 ms; 59,396 KB
testcase_05	AC	4,882 ms; 59,392 KB
testcase_06	AC	3,977 ms; 60,552 KB
testcase_07	AC	4,882 ms; 59,384 KB
testcase_08	AC	3,824 ms; 60,700 KB
testcase_09	AC	5,502 ms; 58,688 KB
testcase_10	AC	4,271 ms; 60,100 KB
testcase_11	AC	4,930 ms; 59,948 KB
testcase_12	AC	4,171 ms; 52,300 KB
testcase_13	AC	5,155 ms; 56,044 KB
testcase_14	AC	4,591 ms; 57,824 KB
testcase_15	AC	4,709 ms; 58,096 KB
testcase_16	AC	3,452 ms; 60,264 KB
testcase_17	AC	3,388 ms; 59,112 KB
testcase_18	AC	4,843 ms; 58,040 KB
testcase_19	AC	5,052 ms; 59,988 KB
testcase_20	AC	124 ms; 41,452 KB

ソースコード

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;
    }
}