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

• 問題: No.382 シャイな人たち (2)
• ユーザー: 37zigen
• 提出日時: 2016-06-24 23:44:12
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 7,250 ms / 8,000 ms
• コード長: 11,058 bytes
• コンパイル時間: 2,797 ms
• コンパイル使用メモリ: 90,152 KB
• 実行使用メモリ: 72,000 KB
• 最終ジャッジ日時: 2024-10-11 21:41:21
• 合計ジャッジ時間: 130,164 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	7,250 ms; 71,388 KB
testcase_01	AC	6,874 ms; 71,308 KB
testcase_02	AC	5,889 ms; 71,280 KB
testcase_03	AC	7,152 ms; 70,348 KB
testcase_04	AC	5,461 ms; 71,432 KB
testcase_05	AC	6,231 ms; 71,172 KB
testcase_06	AC	5,186 ms; 71,344 KB
testcase_07	AC	6,297 ms; 71,420 KB
testcase_08	AC	4,917 ms; 71,756 KB
testcase_09	AC	6,941 ms; 69,236 KB
testcase_10	AC	5,522 ms; 71,288 KB
testcase_11	AC	6,243 ms; 71,320 KB
testcase_12	AC	4,742 ms; 70,828 KB
testcase_13	AC	6,729 ms; 71,304 KB
testcase_14	AC	5,812 ms; 69,140 KB
testcase_15	AC	6,137 ms; 70,272 KB
testcase_16	AC	4,760 ms; 72,000 KB
testcase_17	AC	4,186 ms; 70,952 KB
testcase_18	AC	6,525 ms; 71,532 KB
testcase_19	AC	6,176 ms; 60,196 KB
testcase_20	AC	147 ms; 41,372 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;
    }
}