ABC - 130- A&B&C&D

AtCoder ABC 130 A&B&C&D

AtCoder - 130

E、Fは近いうちに更新予定

A - Rounding

    private void solveA() {
        int x = nextInt();
        int a = nextInt();

        out.println(x < a ? 0 : 10);
    }

B - Bounding

    private void solveB() {
        int n = nextInt();
        int x = nextInt();
        int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();

        int d = 0;
        //必ずD1=0の時に跳ねるので1から
        int cnt = 1;

        for (int i = 0; i < wk.length; i++) {
            d = d + wk[i];
            if (d <= x) {
                cnt++;
            }
        }

        out.println(cnt);
    }

C - Rectangle Cutting

• 誤読してた
  • (x,y) を通る直線で長方形を 2 つの部分に分割　について、
    • (x,y)を通る直線は長方形の外周とは直角に交わる と。(題意としては直角とは限らない)
  • 外周と直角に交わらないのであれば、長方形の重心を通る形で直線を引くことによって長方形を二等分にすることが可能（長方形なので）
    • そのため、分割した最大値は元の長方形の面積の半分
    • (x,y)が重心の時、分割するための直線は複数引くことが可能
      • むしろ、(x,y)が重心でないのならば直線は一つしか引けない

    private void solveC() {
        double w = nextInt();
        double h = nextInt();
        double x = nextInt();
        double y = nextInt();

        double res = (w * h) / 2;
        String ref = String.format("%.10f", res);
        int bF = 0;
        if (w == 2 * x && h == 2 * y) {
            bF = 1;
        }
        out.println(ref + " " + bF);
    }

D - Enough Array

• 問題の読み替えができれば簡単になる
  • 「Kを超える組み合わせ」を探すのではなく、「組み合わせの総数から、Kを超えないものの組み合わせを引く」
  • こうすることによって、尺取法でカウントできるようになる
    • 「Kを超える組み合わせ」をカウントする方法もあるとは思うが思いつかなかった

    private void solveD() {
        int n = nextInt();
        long k = nextLong();
        //      int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
        long[] wk = new long[n];
        for (int i = 0; i < n; i++) {
            wk[i] = nextLong();
        }

        long res = 0;
        long total = 0;
        int right = 0;
        /*
         * 「Kを超える組み合わせ」を数えるのが難しそうなので、
         * 「全体の組み合わせの数から、Kを超えないものの組み合わせを引く」方針で
         */
        for (int left = 0; left < n; left++) {
            //totalにwk[right]を加えることができるならright++
            while (right < n && total + wk[right] < k) {
                total += wk[right];
                right++;
            }
            //rightは条件を満たす最大となっている
            res += (right - left);

            if (right == left) {
                right++;
            } else {
                total -= wk[left];
            }

        }

        /*
         * kとかを無視した組み合わせの総数
         * 部分列なので n * (n+1)
         * longへのキャストを忘れるとintになってWA
         */
        long totalCnt = (long) n * ((long) n + 1L) / 2L;
        out.println(totalCnt - res);
    }