AtCoder Beginner Contest 073

C.Write and Erase(300)

問題

https://beta.atcoder.jp/contests/abc073/tasks/abc073_c

方針

A_1,A_2,...,A_Nに含まれる数の個数を求め、奇数個の数の個数を出力すればよい。計算量はO(N)。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            long[] a = in.nextLongArray(n);
            Map<Long, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                map.merge(a[i], 1, Integer::sum);
            }

            int ans = 0;
            for (int i : map.values()) {
                if (i % 2 == 1) ans++;
            }

            out.println(ans);
        }

雑記

特になし

D.joisino's travel(400)

問題

https://beta.atcoder.jp/contests/abc073/tasks/abc073_d

N個の頂点、M個の辺で結ばれる無向グラフGが与えられる。i本目の辺はA_iとB_iをコストC_iで結んでいる。R個の頂点r1,r2,...,rRの頂点をすべて訪問するときの最小コストを求めよ。

方針

R個の頂点を訪問するとき、訪問する順番はR!通りである。2<=R<=8であるから、R!は高々8!=40320通りである。また頂点数が2<=N<=200であることからO(N³)で全点対間最短経路が求められる。以上より、R!通りのすべての順番を全探索し、各々の頂点間のコストの和が最小となる値を求めればよい。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), m = in.nextInt(), r = in.nextInt();
            int[] rn = new int[r];
            for (int i = 0; i < r; i++) {
                rn[i] = in.nextInt()-1;
            }
            Arrays.sort(rn);

            int[][] g = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        g[i][j] = 0;
                    } else {
                        g[i][j] = INF;
                    }
                }
            }
            for (int i = 0; i < m; i++) {
                int a = in.nextInt()-1, b = in.nextInt()-1, c = in.nextInt();
                g[a][b] = c;
                g[b][a] = c;
            }

            for (int k = 0; k < n; k++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                    }
                }
            }

            Permutation p = new Permutation();

            long ans = 0;
            for (int i = 0; i < r-1; i++) {
                ans += g[rn[i]][rn[i+1]];
            }

            while (p.next(rn)) {
                long tmp = 0;
                for (int i = 0; i < r-1; i++) {
                    tmp += g[rn[i]][rn[i+1]];
                }
                ans = Math.min(ans, tmp);
            }
            out.println(ans);
        }

        static class Permutation {
            public static boolean next(int[] a) {
                int n = a.length;

                int i = n - 1;
                while (i > 0 && a[i - 1] >= a[i])
                    i--;
                if (i <= 0)
                    return false;

                int j = n - 1;
                while (a[j] <= a[i - 1])
                    j--;
                swap(a, i - 1, j);

                int k = n - 1;
                while (i < k)
                    swap(a, i++, k--);

                return true;
            }

            private static void swap(int[] a, int i, int j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }

雑記

特になし