ABC - 035- A&B&C

AtCoder ABC 035 A&B&C

AtCoder - 035

2019/05/27
　問題名修正
　C問題のコードの書き方を修正 int[][]の生成部分

A - テレビ

    private void solveA() {
        int w = nextInt();
        int h = nextInt();
        int wA = w % 16;
        int hA = h % 9;

        out.println(wA == 0 && hA == 0 ? "16:9" : "4:3");
    }

B - ドローン：嘘解法...？？

• ?は何を選択しても良いので後回し
  • ?を除く全ての移動を完了させる
  • 残りの?の処理は、最終位置から
    • 1ならxまたはyが大きくなる方向へ
    • 2ならxまたはyが小さくなる方向へ
    • どちらも、大きい方に対する処理
      • 大きい方をより大きくする
      • 大きい方を小さくする

    private void solveB() {
        String s = next();
        int t = nextInt();

        long x = 0;
        long y = 0;
        int unknownCnt = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
            case 'L':
                x -= 1;
                break;
            case 'R':
                x += 1;
                break;
            case 'U':
                y += 1;
                break;
            case 'D':
                y -= 1;
                break;
            case '?':
                /*
                 * 途中で下手にいじると最大/最小を出せないので、
                 * カウントして最後にくっつける。
                 */
                unknownCnt++;
                break;
            default:
                break;
            }
        }

        for (int i = 0; i < unknownCnt; i++) {
            if (Math.abs(x) > Math.abs(y)) {
                x += chkB(t, x);
            } else {
                y += chkB(t, y);
            }
        }

        out.println(Math.abs(x) + Math.abs(y));
    }

    private long chkB(int t, long pos) {
        long res = 0;
        if (pos < 0) {
            switch (t) {
            case 1:
                res = -1;
                break;
            case 2:
                res = 1;
                break;
            }
        } else {
            switch (t) {
            case 1:
                res = 1;
                break;
            case 2:
                res = -1;
                break;
            }
        }
        return res;
    }

C - オセロ

解説:p.15～

いもす法での実装

- 加算位置（加算開始位置）と減算位置（加算範囲の最終位置+1）を記録して累積和を取る
    - 加算範囲の最終位置+1　=　これより前に加算された値をこの位置で減算する

    /*
     * いもす法
     */
    private void solveC() {
        int numN = nextInt();
        int numQ = nextInt();
        int[][] wk = Stream.generate(() -> new int[] { nextInt(), nextInt() }).limit(numQ).toArray(int[][]::new);
//      int[][] wk = IntStream.range(0, numQ).collect(() -> new int[numQ][2],
//              (t, i) -> {
//                  t[i][0] = nextInt();
//                  t[i][1] = nextInt();
//              },
//              (t, u) -> {
//                  Stream.concat(Arrays.stream(t), Arrays.stream(u));
//              });

        int[] banmen = new int[numN];

        for (int j = 0; j < numQ; j++) {
            /*
             * 加算位置で加算
             */
            banmen[wk[j][0] - 1]++;
            /*
             * 減算位置が配列より大きい
             * ->
             * 最後までその値だから減算を気にしない
             */
            if (wk[j][1] < numN) {
                //減算位置で減算
                banmen[wk[j][1]]--;
            }
        }
        /*
         * 最後累積和をとる
         */
        for (int j = 1; j < numN; j++) {
            banmen[j] = banmen[j] + banmen[j - 1];
        }

        StringBuilder builder = new StringBuilder();
        for (int j : banmen) {
            /*
             * 偶数回操作されたのなら黒。奇数回なら白。
             */
            builder.append(j % 2 == 0 ? 0 : 1);
        }
        out.println(builder.toString());
    }

TLE実装

• 愚直な実装

    private void solveCTLE() {
        int numN = nextInt();
        int numQ = nextInt();
        int[][] wk = IntStream.range(0, numQ).collect(() -> new int[numQ][2],
                (t, i) -> {
                    t[i][0] = nextInt();
                    t[i][1] = nextInt();
                },
                (t, u) -> {
                    Stream.concat(Arrays.stream(t), Arrays.stream(u));
                });

        int[] banmen = new int[numN];

        for (int j = 0; j < numQ; j++) {
            for (int k = wk[j][0] - 1; k < wk[j][1]; k++) {
                banmen[k] = 1 - banmen[k];
            }

        }

        StringBuilder builder = new StringBuilder();
        for (int j : banmen) {
            builder.append(j);
        }
        out.println(builder.toString());
    }