LoginSignup
0

More than 3 years have passed since last update.

ABC - 133- A&B&C&D

Posted at

AtCoder ABC 133 A&B&C&D

AtCoder - 133

A - T or T

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

        out.println(n * a > b ? b : n * a);
    }

B - Good Distance

  • $(i < j)$ の条件を忘れないように
    private void solveB() {
        int n = nextInt();
        int d = nextInt();
        int[][] wk = Stream.generate(() -> IntStream.range(0, d).map(i -> nextInt()).toArray()).limit(n)
                .toArray(int[][]::new);

        int res = 0;
        for (int i = 0; i < n; i++) {
            //i < jに注意
            for (int j = i + 1; j < n; j++) {
                long tmp = 0;
                for (int k = 0; k < d; k++) {
                    tmp += Math.pow(wk[i][k] - wk[j][k], 2);
                }
                long tmpRes = (long) Math.sqrt(tmp);
                if (Math.pow(tmpRes, 2) == tmp) {
                    res++;
                }
            }
        }

        out.println(res);
    }

C - Remainder Minimization 2019

  • 最大(r)を減らせばなんとかなる?
    • mod 2019 なので、数値は0 - 2018を繰り返す
      • lを起点として0-2018を繰り返す
      • $lからr$まで全て試すのではなく、$lからmin(l+(2019*2),r)$の小さい方までを試せばよい
        • $0,1,2・・・2018,0,1,2,・・・2018$ まで試せれば最小値である0,0の組み合わせを選択できる
    • 二つの数値の理想的な最小は0,0の組み合わせ
      • r-lが2019*2より大きい場合
      • r-lが2019*2より小さい場合はその限りではない
    private void solveC() {
        final int CONST_MOD = 2019;
        int l = nextInt();
        int r = nextInt();
        /*
         * とりあえず最大を減らさないと何もできない。
         * l+2019かrかどちらか小さいほうを最大値として採用(MODなので)
         * l+2019で1周期。ただ、これだと最小値が1回しか出てこない。
         * +(2019*2)2周しておけば1が2回出てくる。
         *
         */
        int wkR = Math.min(l + (CONST_MOD * 2), r);
        int res = 2020;
        for (int i = l; i <= wkR; i++) {
            for (int j = i + 1; j <= wkR; j++) {
                res = Math.min(((i % CONST_MOD) * (j % CONST_MOD)) % CONST_MOD, res);
            }
        }

        out.println(res);
    }

D - Rain Flows into Dams

  • 連立方程式を立てて解いた
    • ダムの送料を計算して、どこか一つの山の雨を求める
    • どこか一つの山が決まれば他も決めることができる
    • 山の数は奇数なので、1 -> 3 -> 5 -> 7 -> 9 ・・・と増える
      • 常に二つずつ山が増えるので、式は次のように+-を繰り返す
        • 山A = ダム1 - ダム2 + ダム3 - ダム4 + ダム5 - + - + - + ・・・

例:2

ダム 3 8 7 5 5
a B C D E
2 4 12 2 8

      ダム1 = A/2 + B/2  ->  ダム1*2 = A + B  ->  B =  ダム1*2 - A
      ダム2 = B/2 + C/2  ->  ダム2*2 = B + C  ->  C =  ダム2*2 - B
      ダム3 = C/2 + D/2  ->  ダム3*2 = C + D  ->  D =  ダム3*2 - C
      ダム4 = D/2 + E/2  ->  ダム4*2 = D + E  ->  E =  ダム4*2 - D
      ダム5 = E/2 + A/2  ->  ダム5*2 = E + A  ->  A =  ダム5*2 - E

      上の式を変形してまず山Aを求める
      A = ダム1 - ダム2 + ダム3 - ダム4 + ダム5

      Aが決まれば山B以降は決まる
      B = ダム1*2 - A
      C = ダム2*2 - B
      D = ダム3*2 - C
      E = ダム4*2 - D
    private void solveD() {
        int n = nextInt();
        int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();

        long a = 0;

                //偶数番目のダムは+、奇数番目のダムは-
        for (int i = 0; i < wk.length; i++) {
            if (i % 2 == 0) {
                a += wk[i];
            } else {
                a -= wk[i];
            }
        }
        long[] mountain = new long[n];
        mountain[0] = a;
        //最後のヤマは山Aのことなので除外
        for (int i = 0; i < mountain.length - 1; i++) {
            mountain[i + 1] = wk[i] * 2 - mountain[i];
        }
        StringBuilder builder = new StringBuilder();
        for (long l : mountain) {
            builder.append(l + " ");
        }
        out.println(builder.toString().trim());
    }

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0