AtCoder Beginner Contest 079

C.Train Ticket(300)

問題

https://beta.atcoder.jp/contests/abc079/tasks/abc079_c

方針

3つのオペランドに対して+,-の8通りの組み合わせを全探索して、計算したときに7になる時のオペランドを出力すればいい。

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

            String str = in.nextString();
            int[] num = new int[4];
            for (int i = 0; i < 4; i++) {
                num[i] = Integer.parseInt(str.substring(i, i+1));
            }

            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < 2; k++) {
                        int s = num[0];
                        if (i == 0) {
                            s += num[1];
                        } else {
                            s -= num[1];
                        }
                        if (j == 0) {
                            s += num[2];
                        } else {
                            s -= num[2];
                        }
                        if (k == 0) {
                            s += num[3];
                        } else {
                            s -= num[3];
                        }
                        if (s == 7) {
                            StringBuffer sb = new StringBuffer();
                            sb.append(num[0]);
                            if (i == 0) {
                                sb.append("+");
                            } else {
                                sb.append("-");
                            }
                            sb.append(num[1]);
                            if (j == 0) {
                                sb.append("+");
                            } else {
                                sb.append("-");
                            }
                            sb.append(num[2]);
                            if (k == 0) {
                                sb.append("+");
                            } else {
                                sb.append("-");
                            }
                            sb.append(num[3]);
                            sb.append("=7");
                            out.println(sb.toString());
                            return;
                        }
                    }
                }
            }
        }

雑記

いざ改めて実装してみると、きれいに実装できなかった。23の組み合わせはビット全探索でもう少しシンプルな実装にできそうである。

D.Wall(400)

問題

https://beta.atcoder.jp/contests/abc079/tasks/abc079_d

数iからjに書き換えるときコストC(i,j)かかる。今、縦H、横WのH×Wのマス目が与えられ、1つ以上のマス目に0以上9以下の整数が1つずつ書かれている。A(i,j)のマスはA(i,j) != -1の場合はA(i,j)が書かれており、A_(i,j) = -1の場合は何も書かれていない。すべてのマスを1にする時の最小のコストを求めよ。

方針

マスに書かれている1以外のすべての数を1にしなければいけない。1でない数xを1にする時の最小のコストはxからいくつかの数を経由して1になる時の最小コストである。つまりこれは頂点10、辺100の有向グラフG上の最短経路を求めることに他ならない。ここでは実装が容易なワーシャルフロイド法で求めることにする。xから1への最小のコストを求めれば、後はH×Wマス上の1以外の数の個数を求め、数の個数とその数と1の最小コストをかけた和を求めればよい。

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

            int h = in.nextInt(), w = in.nextInt();
            int[][] g = new int[10][10];
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 10; j++) {
                    g[i][j] = in.nextInt();
                }
            }

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

            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    int l = in.nextInt();
                    map.merge(l, 1, Integer::sum);
                }
            }

            long ans = 0;
            for (Entry<Integer, Integer> e : map.entrySet()) {
                int f = e.getKey();
                if (f == -1) continue;
                ans += e.getValue() * g[f][1];
            }

            out.println(ans);
        }

雑記

数xから1への最小コストがグラフの最短経路で求められることに気づけるかどうか。