BC - 074- A&B&C

14696 ワード
AtCoder 競技プログラミング java8 AtCoder テキストリンク

AtCoder ABC 074 A&B&C

AtCoder - 074

A問題

    private void solveA() {
        int numN = nextInt();
        int numA = nextInt();

        out.println(numN * numN - numA);
    }

B問題

  • 求めたい値は黄色の部分

　　　　　　　　　　　　　　　　

  • こんな感じの実装
  • 1点1点sumしていけばよい
    private void solveB() {
        int numN = nextInt();
        int numK = nextInt();

        int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

        int res = Arrays.stream(wk).reduce(0, (sum, num) -> {
            return sum += Math.min(num * 2, (numK - num) * 2);
        });

        out.println(res);

    }

C問題

  • $A*100*a + B*100*b + C*c + D*d \leqq numF \quad (a,b,c,dは任意の整数)$ が成り立つ {$a,b,c,d$} である
  • $E < 100 * (C*c + D*d) / (A*100*a + B*100*b)$ が成り立つこと（溶解度）

  • $100 * (C*c + D*d) / (A*100*a + B*100*b+C*c + D*d)$ が最大となる {$a,b,c,d$} を求める

  • 結論：何も考えずにforで書くのが一番良かった。再帰とか下手に考えるとTLEになる。

    private void solveC() {
        int numA = nextInt();
        int numB = nextInt();
        int numC = nextInt();
        int numD = nextInt();
        int numE = nextInt();
        int numF = nextInt();

        int[][] memoC = new int[101][2];

        double noudoMax = -1;
        int water = 0;
        int sugar = 0;
        /*
         * Aのloop・水AがF以下（未満ではない）
         */
        for (int i = 0; (numA * 100) * i <= numF; i++) {
            int wA = (numA * 100) * i;
            if (wA > numF) {
                break;
            }
            /*
             * Bのloop・水Aと水Bを足してF以下
             */
            for (int j = 0; wA + ((numB * 100) * j) <= numF; j++) {
                int wB = (numB * 100) * j;
//              if (wA + wB > numF) {
//                  break;
//              }
                if (wA + wB == 0) {
                    continue;
                }
                /*
                 * Cのloop・水Aと水Bと砂糖Cを足してF以下
                 */
                for (int k = 0; wA + wB + (numC * k) <= numF; k++) {
                    int sC = numC * k;
                    if (numE < 100 * k / (wA + wB)) {
                        break;
                    }
                    /*
                     * Dのloop・水Aと水Bと砂糖Cと砂糖Dを足してF以下
                     */
                    for (int l = 0; wA + wB + sC + (numD * l) <= numF; l++) {
                        int sD = numD * l;
                        /*
                         * 全て0は対象外
                         */
                        if (wA + wB + sC + sD == 0) {
                            continue;
                        }
                        //                      if (wA + wB + sC + sD > numF) {
                        //                          break;
                        //                      }
                        /*
                         * 砂糖がEよりも多く水に溶けている場合は対象外
                         * 除算をしていないのは丸め誤差を気にしているため
                         */
                        if (numE * (wA + wB) < 100 * (sC + sD)) {
                            break;
                        }
                        /*
                         * 濃度計算：1000000を乗算しているのは丸め誤差対策
                         */
                        double noudo = 1000000 * (sC + sD) / (wA + wB + sC + sD);

                        if (noudoMax < noudo) {
                            noudoMax = noudo;
                            water = wA + wB;
                            sugar = sC + sD;
                        }
                    }
                }
            }
        }

        out.println(water + sugar + " " + sugar);

    }