ABC - 035- A&B&C

#AtCoder ABC 035 A&B&C
AtCoder - 035

2019/05/27
　問題名修正
　C問題のコードの書き方を修正 int[][]の生成部分

#A - テレビ

	private void solveA() {
		int w = nextInt();
		int h = nextInt();
		int wA = w % 16;
		int hA = h % 9;

		out.println(wA == 0 && hA == 0 ? "16:9" : "4:3");
	}

#B - ドローン：嘘解法...？？

• ?は何を選択しても良いので後回し
  • ?を除く全ての移動を完了させる
  • 残りの?の処理は、最終位置から
    • 1ならxまたはyが大きくなる方向へ
    • 2ならxまたはyが小さくなる方向へ
    • どちらも、大きい方に対する処理
      • 大きい方をより大きくする
      • 大きい方を小さくする

	private void solveB() {
		String s = next();
		int t = nextInt();

		long x = 0;
		long y = 0;
		int unknownCnt = 0;
		for (int i = 0; i < s.length(); i++) {
			switch (s.charAt(i)) {
			case 'L':
				x -= 1;
				break;
			case 'R':
				x += 1;
				break;
			case 'U':
				y += 1;
				break;
			case 'D':
				y -= 1;
				break;
			case '?':
				/*
				 * 途中で下手にいじると最大/最小を出せないので、
				 * カウントして最後にくっつける。
				 */
				unknownCnt++;
				break;
			default:
				break;
			}
		}

		for (int i = 0; i < unknownCnt; i++) {
			if (Math.abs(x) > Math.abs(y)) {
				x += chkB(t, x);
			} else {
				y += chkB(t, y);
			}
		}

		out.println(Math.abs(x) + Math.abs(y));
	}

	private long chkB(int t, long pos) {
		long res = 0;
		if (pos < 0) {
			switch (t) {
			case 1:
				res = -1;
				break;
			case 2:
				res = 1;
				break;
			}
		} else {
			switch (t) {
			case 1:
				res = 1;
				break;
			case 2:
				res = -1;
				break;
			}
		}
		return res;
	}

#C - オセロ
解説:p.15～

###いもす法での実装
- 加算位置（加算開始位置）と減算位置（加算範囲の最終位置+1）を記録して累積和を取る
- 加算範囲の最終位置+1　=　これより前に加算された値をこの位置で減算する

	/*
	 * いもす法
	 */
	private void solveC() {
		int numN = nextInt();
		int numQ = nextInt();
		int[][] wk = Stream.generate(() -> new int[] { nextInt(), nextInt() }).limit(numQ).toArray(int[][]::new);
//		int[][] wk = IntStream.range(0, numQ).collect(() -> new int[numQ][2],
//				(t, i) -> {
//					t[i][0] = nextInt();
//					t[i][1] = nextInt();
//				},
//				(t, u) -> {
//					Stream.concat(Arrays.stream(t), Arrays.stream(u));
//				});

		int[] banmen = new int[numN];

		for (int j = 0; j < numQ; j++) {
			/*
			 * 加算位置で加算
			 */
			banmen[wk[j][0] - 1]++;
			/*
			 * 減算位置が配列より大きい
			 * ->
			 * 最後までその値だから減算を気にしない
			 */
			if (wk[j][1] < numN) {
				//減算位置で減算
				banmen[wk[j][1]]--;
			}
		}
		/*
		 * 最後累積和をとる
		 */
		for (int j = 1; j < numN; j++) {
			banmen[j] = banmen[j] + banmen[j - 1];
		}

		StringBuilder builder = new StringBuilder();
		for (int j : banmen) {
			/*
			 * 偶数回操作されたのなら黒。奇数回なら白。
			 */
			builder.append(j % 2 == 0 ? 0 : 1);
		}
		out.println(builder.toString());
	}

###TLE実装

• 愚直な実装

	private void solveCTLE() {
		int numN = nextInt();
		int numQ = nextInt();
		int[][] wk = IntStream.range(0, numQ).collect(() -> new int[numQ][2],
				(t, i) -> {
					t[i][0] = nextInt();
					t[i][1] = nextInt();
				},
				(t, u) -> {
					Stream.concat(Arrays.stream(t), Arrays.stream(u));
				});

		int[] banmen = new int[numN];

		for (int j = 0; j < numQ; j++) {
			for (int k = wk[j][0] - 1; k < wk[j][1]; k++) {
				banmen[k] = 1 - banmen[k];
			}

		}

		StringBuilder builder = new StringBuilder();
		for (int j : banmen) {
			builder.append(j);
		}
		out.println(builder.toString());
	}