ABC - 098- A&B&C

AtCoder ABC 098 A&B&C

AtCoder - 098]

A問題

• +-*を試してみて一番結果が大きいもの

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

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

			System.out.println(Math.max(numA + numB, Math.max(numA - numB, numA * numB)));

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

B問題

• 文字列を分割するパターンを全探索
• それぞれの文字をカウントして、もう片方に文字が含まれるかを判定
  • 多分、a,b,c,・・・zをASCIIde1-26の数値に変換し、配列で判定したほうが速い気がする

	private void solveB() {
		Scanner scanner = null;
		int numN = 0;
		String numS = "";

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			numS = scanner.next();
			String numWk = "";
			int res = 0;
			numWk = numS;
			for (int i = numN - 1; i >= 0; i--) {
				char[] val1 = numWk.substring(0, i).toCharArray();
				char[] val2 = numWk.substring(i, numN).toCharArray();

				Set<Character> wkSet1 = new HashSet<Character>();
				for (int j = 0; j < val1.length; j++) {
					wkSet1.add(val1[j]);
				}

				Set<Character> wkSet2 = new HashSet<Character>();
				for (int j = 0; j < val2.length; j++) {
					wkSet2.add(val2[j]);
				}

				Set<Character> chkSet = null;
				Set<Character> resSet = null;
				if (wkSet1.size() > wkSet2.size()) {
					chkSet = wkSet1;
					resSet = wkSet2;
				} else {
					chkSet = wkSet2;
					resSet = wkSet1;
				}

				int cnt = 0;
				for (Character character : chkSet) {
					if (resSet.contains(character)) {
						cnt++;
					}
				}

				res = Math.max(res, cnt);
			}

			System.out.println(res);

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

C問題

• 全パターン試すとTLEになるので

  • 累積和を利用
    1. リーダーが左端から移っていく場合の配列（一番左-0番目-からスタート）
       • 累積和で出していく
    2. リーダーが右端から移っていく場合の配列（一番右-N番目-からスタート）
       • 累積和で出していく
    3. 左右の人の合計値の配列
       • 左右の人数の累積和を合成する $3[i]=1[i]+2[i]$

• リーダーとなった人の向きは問わない

  • 0またはN-1の人の値の処理に気をつける
  • 単純にカウントするのではなく、リーダーになった瞬間は「カウント0」で、リーダーじゃなくなった瞬間にカウントアップされる
    • 「カウント方法誤り」に図示

パターンを二つ定義

• リーダーが右端から移っていく

  • Eの人のカウントをしたい
    • Eの人がWを向いていく
    • Wの人の動きは気にしない
    • Wの人は、リーダーに到達する前には何人いるかわからず、到達後リーダーの方を向いているのでカウントしようがない

• リーダーが左端から移っていく

  • Wの人のカウントをしたい(Wの人がEを向いていく。Eの人の動きは気にしない)
    • Wの人がEを向いていく
    • Eの人の動きは気にしない
    • Eの人は、リーダーに到達する前には何人いるかわからず、到達後リーダーの方を向いているのでカウントしようがない

カウント方法

	W	E	W	E	W	E	E	E	W	W	W	E
リーダーの位置	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓
リーダーが右端から移っていく	6	5	5	4	4	3	2	1	1	1	1	0	Eをカウント
リーダーが左端から移っていく	0	1	1	2	2	3	3	3	3	4	5	6	Wをカウント

カウント方法誤り

	W	E	W	E	W	E	E	E	W	W	W	E
リーダーが右端から移っていく	6	6	5	5	4	4	3	2	1	1	1	1	Eをカウント
リーダーが左端から移っていく	1	1	2	2	3	3	3	3	4	5	6	6	Wをカウント

	private void solveC() {
		Scanner scanner = null;
		int numN = 0;
		char[] numS;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			numS = scanner.next().toCharArray();

			int[] eArray = new int[numS.length];
			int[] wArray = new int[numS.length];
			int[] resArray = new int[numS.length];

			wArray[numN - 1] = 0;
			for (int i = numN - 2; i >= 0; i--) {
				if ('E' == numS[i + 1]) {
					wArray[i] = wArray[i + 1] + 1;
				} else {
					wArray[i] = wArray[i + 1];
				}
			}
			eArray[0] = 0;
			for (int i = 0; i < numN; i++) {
				if (i >= 1 && 'W' == numS[i - 1]) {
					eArray[i] = eArray[i - 1] + 1;
				} else if (i >= 1) {
					eArray[i] = eArray[i - 1];
				}
				resArray[i] = eArray[i] + wArray[i];
			}
			Arrays.sort(resArray);
			System.out.println(resArray[0]);

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

C問題：もっと簡単な式

• 足し引きすれば良い

	private void solveC2() {
		try (Scanner scanner = new Scanner(System.in)) {
			int numN = scanner.nextInt();
			char[] numS = scanner.next().toCharArray();

			int eCnt = 0;
			int wCnt = 0;
			for (int i = 0; i < numN; i++) {
				if ('E' == numS[i]) {
					eCnt++;
				}
			}
			int res = numN;
			for (int i = 0; i <= numN; i++) {
				if (i != 0) {
					if ('W' == numS[i - 1]) {
						wCnt++;
					} else {
						if (i != 1) {
							eCnt--;
						}
					}
				} else {
					if ('E' == numS[i]) {
						eCnt--;
					}
				}

				res = Math.min(wCnt + eCnt, res);
			}
			System.out.println(res);

		}
	}