ABC - 074- A&B&C

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問題

• $A100a + B100b + Cc + Dd \leqq numF \quad (a,b,c,dは任意の整数)$ が成り立つ {$a,b,c,d$} である

• $E < 100 * (Cc + Dd) / (A100a + B100b)$ が成り立つこと（溶解度）

• $100 * (Cc + Dd) / (A100a + B100b+Cc + Dd)$ が最大となる {$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);

	}