ABC - 016 - A&B&C

AtCoder ABC 016 A&B&C

AtCoder - 016

A - 12月6日

    private void solveA() {
        int m = nextInt();
        int d = nextInt();
        out.print(m % d == 0 ? "YES" : "NO");
    }

B - A±B Problem

    private void solveB() {
        int a = nextInt();
        int b = nextInt();
        int c = nextInt();

        boolean p = a + b == c;
        boolean m = a - b == c;

        if (p && m) {
            out.println("?");
        } else if (!p && !m) {
            out.println("!");
        } else if (p && !m) {
            out.println("+");
        } else if (!p && m) {
            out.println("-");
        }

    }

C - 友達の友達

• 無向グラフの頂点間の距離を求める
  • 友達を頂点とする
  • 友達との距離は1（友達間の距離は同じ）
  • 友達の友達は頂点間の距離が2
  • 友達の友達の友達は頂点間の距離が3

そろそろワーシャルフロイド法以外での解き方覚えないと。。。

    private void solveC() {
        int n = nextInt();
        int m = nextInt();

        int[] a = new int[m];
        int[] b = new int[m];
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            //MAXで埋めておく
            Arrays.fill(graph[i], Integer.MAX_VALUE / 2);
            //自分への移動コストは0
            graph[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            a[i] = nextInt() - 1;
            b[i] = nextInt() - 1;
            //隣接行列の作成
            graph[a[i]][b[i]] = 1;
            graph[b[i]][a[i]] = 1;
        }

        //ワーシャルフロイド法
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    graph[j][k] = Integer.min(graph[j][k], graph[j][i] + graph[i][k]);
                }
            }
        }

        /*
         * 自分からの移動コスト
         * 1=友達
         * 2=友達の友達
         * 3=友達の友達の友達
         * 4=友達の友達の友達の友達・・・
         * 以下続く
         */
        for (int i = 0; i < graph.length; i++) {
            int res = 0;
            for (int j = 0; j < graph.length; j++) {
                res += graph[i][j] == 2 ? 1 : 0;
            }
            out.println(res);
        }
    }