ABC - 104- A&B&C

AtCoder ABC 104 A&B&C

AtCoder - 104

A問題

	private void solveA() {
		Scanner scanner = null;
		int numRating = 0;

		try {
			scanner = new Scanner(System.in);
			numRating = scanner.nextInt();

			if (numRating < 1200) {
				System.out.println("ABC");
			} else if (numRating < 2800) {
				System.out.println("ARC");
			} else {
				System.out.println("AGC");
			}

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

B問題

• 先頭一文字目はA
• S の先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1 個含まれる
  • 2個以上あったらWA
• 以上の A, C を除く S のすべての文字は小文字である
  • javaだと小文字はCharacter#isLowerCaseで判定可能

private void solveB() {
		Scanner scanner = null;
		String strS = "";

		try {
			scanner = new Scanner(System.in);
			strS = scanner.next();

			if (strS.charAt(0) != 'A') {
				System.out.println("WA");
				return;
			}
			int res = 0;
			int wkIndex = 0;
			for (int i = 2; i < strS.length() - 1; i++) {
				if (strS.charAt(i) == 'C') {
					res++;
					wkIndex = i;
				}
			}
			if (res != 1) {
				System.out.println("WA");
				return;
			}
			for (int i = 0; i < strS.length(); i++) {
				if (i != 0 && i != wkIndex && !Character.isLowerCase(strS.charAt(i))) {
					System.out.println("WA");
					return;
				}
			}
			System.out.println("AC");

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

C問題

• $D ; = ; 2^{10}$ なので、、、greedyで。。。

	private void solveC() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numD = scanner.nextInt();
			int numG = scanner.nextInt();
			//色々初期計算しとけばバグ減らせそうなので多めに
			long[][] wk = new long[10][5];

			for (int i = 0; i < numD; i++) {
				wk[i][0] = (i + 1) * 100;//単価
				wk[i][1] = scanner.nextLong();//問題数
				wk[i][2] = scanner.nextLong();//コンプリートボーナス
				wk[i][3] = (wk[i][0] * wk[i][1]) + wk[i][2];//コンプリート総額
			}

			long operationNum = 999999999;
			int[] mask = new int[10];
			/*
			 * mask回数分ループ
			 */
			for (int i = 0; i < Math.pow(2, 10); i++) {
				/*
				 * mask生成
				 * ちなみにこのマスクは、
				 * 配点の低いやつをコンプリート -> 配点の高いやつをコンプリート
				 * という順序のmaskを生成しています。
				 */
				int maskNum = i;
				int cnt = 0;
				while (maskNum > 0) {
					mask[cnt] = maskNum % 2;
					cnt++;
					maskNum /= 2;
				}

				//処理用変数：目標点数
				int wkG = numG;
				//処理用変数：操作回数
				int wkOperationNum = 0;

				/*
				 * maskの分だけループする
				 */
				for (int j = 0; j < mask.length; j++) {
					/*
					 * 使う対象の問題
					 * 全問解いてコンプリートもらうと決めたやつ -> mask[i]=1
					 * &
					 * 取り込めている奴 -> wk[i][0] > 0
					 */
					if (mask[j] == 1 && wk[j][0] > 0) {
						/*
						 * 使うと決めたので全部解く
						 * コンプリート総額を利用
						 */
						wkG -= wk[j][3];
						/*
						 * 問題を解いた回数=問題数　を記録
						 * これでこの問題は全て終了
						 */
						wkOperationNum += wk[j][1];
					}
					/*
					 * 結果として取得したい点数を達成済みの場合はこのマスクはbreak
					 * この後の点数合わせは不要
					 */
					if (wkG <= 0) {
						//break前に問題数を記録
						operationNum = Math.min(operationNum, wkOperationNum);
						break;
					}
				}
				/*
				 * 希望点数に達していないため、まだ解かないといけない問題がある
				 */
				if (wkG > 0) {
					/*
					 * 今回のループの対象は、maskしていない=コンプリートしないと決めた問題
					 * ただし、配点の高い順から
					 * 配点の高さはwk[i]のiの大きい順から
					 * なので、mask.length-1ではなく、10でもwk.length-1でもどれでもよい
					 * 解く手数を減らしたいなら配転の高いのからやったほうがいいよね
					 */
					outside: for (int j = mask.length - 1; j >= 0; j--) {
						/*
						 * 使う対象の問題
						 * 全問解いてコンプリートもらわないやつ -> mask[i]=0
						 * &
						 * 取り込めている奴 -> wk[i][0] > 0
						 * なので、このループのwkG-=ではコンプリートボーナスつかいません
						 */
						if (mask[j] == 0 && wk[j][0] > 0) {
							/*
							 * 解く対象の配点問題で問題数をループ
							 */
							for (int k = 0; k < wk[j][1]; k++) {
								//1個ずつ解いて回数をカウントアップ
								wkG -= wk[j][0];
								wkOperationNum++;
								/*
								 * これ以上不要ならbreak
								 * 汚いけど外まで飛ぶ
								 */
								if (wkG <= 0) {
									//break前に問題数を記録
									operationNum = Math.min(operationNum, wkOperationNum);
									break outside;
								}
							}
						}
					}
					/*
					 * ここまでくるとこのmaskでは解きようがない
					 * 全ての問題解いてもクリアできない点ということなので
					 */
				}
			}

			System.out.println(operationNum);
		}

	}