ABC - 020 - A&B&C

AtCoder ABC 020 A&B&C

AtCoder - 020

2019/05/16 - 問題名追記

A - クイズ

    private void solveA() {
        int n = nextInt();

        out.println(n == 1 ? "ABC" : "chokudai");
    }

B - 高橋くんと文字列圧縮

    private void solveB() {
        String res = IntStream.range(0, 2).mapToObj(i -> next()).collect(Collectors.joining());

        out.println(Integer.parseInt(res) * 2);
    }

C - 壁抜け：DFS(メモ化再帰)でAC

想定解法だと以下なんだけど
　1. ワーシャルフロイド/ベルマンフォード/ダイクストラで最短経路計算
　2. 二分探索でtを絞り込んでいく

　最初想定解法と同じように考えたのでワーシャルフロイドで実装したのだけど、sampleとか自分の想定テストケースだと通るのに、実際にジャッジに投げると4分の1ほどがWAになってしまいかつ、WAの理由がわからないのであきらめてDFSで実装。
　どこかで再度想定解法で解かないといけない。
　
　ワーシャルフロイドの方はマジで誰かソースみてWAになる点教えてほしいWA

メモ化再帰で実装したときにはまった備忘（TLE対策）

• 当たり前の様に行っている実装方法の中に、おもったよりも遅いものがある

  • 最初、ずっとTLEだったのでいくつかコード修正しながら検証していった結果、以下をやめるだけで一気にTLEが解消できた（実際には修正しているうちに戻り値なくしてvoidにしたりもしてるけど。voidにするのも微妙に効果あったりはした）
  • Long#min()の利用を止める
    • メモ(dist[][])を更新するときにメモの中身をminで比較するのをやめたら劇的に速度改善した
      • dist[][]の値を更新するときにLong#min()で見ていたのを止めるように（min()しなくても済むように）ソースを修正しただけでTLE解消できた

    private void solveC() {
        int h = nextInt();
        int w = nextInt();
        long t = nextLong();
        char[][] wk = new char[h][w];

        int sX = 0;
        int sY = 0;
        int gX = 0;
        int gY = 0;
        for (int i = 0; i < wk.length; i++) {
            wk[i] = next().toCharArray();
            for (int j = 0; j < wk[i].length; j++) {
                if (wk[i][j] == 'S') {
                    sX = i;
                    sY = j;
                } else if (wk[i][j] == 'G') {
                    gX = i;
                    gY = j;
                }
            }
        }
        long low = 1;
        long high = t;
        long[][] memo = new long[h][w];

        while (high - low != 1) {
            long mid = (high + low) / 2;
            for (long[] l : memo) {
                Arrays.fill(l, Long.MAX_VALUE);
            }
            dfsC(wk, h, w, t, sX, sY, mid, 0, memo, new boolean[h][w]);
            if (memo[gX][gY] <= t) {
                low = mid;
            } else {
                high = mid;
            }
        }

        out.println(low);
    }


    static final int[] dx = new int[] { 0, 0, -1, 1 };
    static final int[] dy = new int[] { 1, -1, 0, 0 };

    private void dfsC(char[][] wk, int h, int w, long t, int currentH, int currentW, long x, long val,
            long[][] dist, boolean[][] pass) {

        /*
         * 検索範囲越え
         * または
         * 既に探索済み
         */
        if (currentH < 0 || currentH >= h || currentW < 0 || currentW >= w || pass[currentH][currentW]) {
            return;
        }

        /*
         * 現在の値がすでに入っている値より小さいならこれ以上の探索は不要
         * 現在の値がtを超えているならこれ以上の探索は不要
         */
        if (dist[currentH][currentW] < val || val > t) {
            return;
        } else {
            /*
             * 探索対象なので値を更新
             * 本当はminとしたいけど、minすると間に合わない
             */
            dist[currentH][currentW] = val;
        }
        /*
         * Gなので終了
         */
        if (wk[currentH][currentW] == 'G' || (val > 0 && wk[currentH][currentW] == 'S')) {
            return;
        }
        pass[currentH][currentW] = true;
        /*
         * 4方向の探索を行う
         */
        for (int i = 0; i < 4; i++) {
            int wkH = currentH + dx[i];
            int wkW = currentW + dy[i];
            if (wkH < 0 || wkH >= h || wkW < 0 || wkW >= w) {
                continue;
            }
            long currVal = 0;
            switch (wk[wkH][wkW]) {
            case 'S':
            case 'G':
            case '.':
                currVal = 1;
                break;
            case '#':
                currVal = x;
                break;
            default:
                break;
            }

            dfsC(wk, h, w, t, wkH, wkW, x, val + currVal, dist, pass);
        }
        pass[currentH][currentW] = false;
    }