ABC - 125- A&B&C&D

AtCoder ABC 125 A&B&C&D

AtCoder - 125

解説放送

2019/05/22
　問題名を追記

2019/06/27
　C問題のseg tree解法追加

A - Biscuit Generator

• t+0.5時間を超えない間はビスケットを追加できる

	private void solveA() {
		int a = nextInt();
		int b = nextInt();
		int t = nextInt();

		int res = 0;

		//		double time = 0;
		//		while ((time += a) <= (t + 0.5)) {
		//			res += b;
		//		}

		res = t / a * b;

		out.println(res);
	}

B - Resale

• Xは$\sum_{i=1}^{n} V_i$
• Yは$\sum_{i=1}^{n} C_i$
  • $X-Y$の最大値なので
    • Xの方が大きいほうが良い
    • $V_i<C_i$となる組をカウントしてはいけない

	private void solveB() {
		int numN = nextInt();
		int[] v = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		int[] c = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		long res = 0;
		for (int i = 0; i < numN; i++) {
			if (v[i] > c[i]) {
				res += (v[i] - c[i]);
			}
		}

		out.println(res);
	}

C - GCD on Blackboard

累積和

• 左右からGCDの累積和をとっていき、不要な部分を除外する

position						GCD
	1	2	3	4	5	1-5のGCD
i=1		2	3	4	5	2-5のGCD
i=2	1		3	4	5	1と3-5のGCD
i=3	1	2		4	5	1-2と4-5のGCD
i=4	1	2	3		5	1-3と5のGCD
i=5	1	2	3	4		1-4のGCD

• $i=3$の時だと、$1-2のGCD$と$4-5のGCD$でGCDをとるとトータルのGCDになる
  • gcd(1-2,4-5)
  • 上記を実現するために、1-5のGCDと5-1のGCDを作ってマージする

/*
	 * 解説放送
	 * https://www.youtube.com/watch?v=8lm8o8L9Bmw
	 */
	private void solveC() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		long[] forward = new long[numN];
		long[] backward = new long[numN];

		long forGcd = 0;
		long backGcd = 0;
		for (int i = 0; i < numN; i++) {
			forGcd = forward[i] = getGcd(forGcd, wk[i]);
			backGcd = backward[numN - 1 - i] = getGcd(backGcd, wk[numN - 1 - i]);
		}
		long max = 1;

		for (int i = 0; i < numN; i++) {
			if (i == 0) {
				max = Long.max(max, backward[i + 1]);
			} else if (i == numN - 1) {
				max = Long.max(max, forward[i - 1]);
			} else {
				max = Long.max(max, getGcd(forward[i - 1], backward[i + 1]));
			}
		}
		out.println(max);
	}

	private long getGcd(long num1, long num2) {
		long max = Long.max(num1, num2);
		long min = Long.min(num1, num2);
		if (min == 0) {
			return max;
		}
		long amari = max % min;

		while (amari != 0) {
			max = min;
			min = amari;
			amari = max % min;
		}
		return min;

	}

TLE

• まぁ、備忘なのでこんなのも、、、、

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

		long maxGcd = 0;

		for (int i = 0; i < numN; i++) {
			long max = 0;
			for (int j = 0; j < numN; j++) {
				if (i == j) {
					continue;
				}
				max = getGcd(max, wk[j]);
			}
			maxGcd = Long.max(maxGcd, max);
		}
		out.println(maxGcd);
	}

seg treeで解いた

参考：
けんちょんの競プロ精進記録
セグメント木をソラで書きたいあなたに
完全制覇・ツリー上でのクエリ処理技法
プログラミングコンテストでのデータ構造
プログラミングコンテストチャレンジブック P.153～

	/**
	 * segment tree version
	 *
	 * 入力値サンプル
	 * [P-1]
	 * 3
	 * 7 6 8
	 *
	 * [P-2]
	 * 6
	 * 12 3 6 9 15 11
	 *
	 */
	private void solveC3() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		SegTree tree = new SegTree(numN);

		/*
		 * set前
		 * [P-1]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
		 *
		 * [P-2]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
		 */
		for (int i = 0; i < wk.length; i++) {
			tree.set(i, wk[i]);
		}
		/*
		 * set終わった直後
		 * [P-1]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 7, 6, 8, 2147483647]
		 *
		 * [P-2]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]
		 *
		 */
		tree.update();
		/*
		 * update終わった直後
		 * [P-1]
		 * [2147483647, 1, 1, 1, 7, 6, 8, 2147483647]
		 *
		 * leaf　は値で、nodeは公約数
		 *  1( k 1)
		 *     |----------------------|
		 *     |                      |
		 *  1(2k 2)               1(2k+1 3)
		 *     |--------|             |----------|
		 *     |        |             |          |
		 *  7(2k 4) 6(2k+1 5)     8(2k 6)   2147483647(2k+1 7)
		 *
		 *
		 *  [P-2]
		 *  [2147483647, 1, 3, 1, 3, 3, 1, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]
		 *
		 *  1( k 1)
		 *     |----------------------------------------|
		 *     |                                        |
		 *  3(2k 2)                                  1(2k+1 3)
		 *     |-----------------|                      |------------------------|
		 *     |                 |                      |                        |
		 *  3(2k 4)            3(2k+1 5)             3(2k 6)                  2147483647(2k+1 7)
		 *     |-------|         |------------|         |----------|             |--------------------|
		 *     |       |         |            |         |          |             |                    |
		 * 12(2k 8)  3(2K+1 9)  6(2k 10)  9(2K+1 11) 15(2k 12)  11(2K+1 13)   2147483647(2k 14)    2147483647(2k+1 15)
		 */

		long res = 0;

		for (int i = 0; i < numN; i++) {
			/*
			 * 半開区間[)
			 * 0 - i
			 * のGCD(iは含まず)
			 */
			long left = tree.get(0, i);
			/*
			 * 半開区間[)
			 * i+1 - numN(numNは含まず)
			 * のGCD
			 */
			long right = tree.get(i + 1, numN);
			res = Long.max(res, getGcd(left, right));

		}

		out.println(res);
	}

	/**
	 * segment tree
	 * 完全二分木
	 * @author pc9801bx2
	 *
	 */
	private static class SegTree {

		private long[] dat;
		private int numOfElmSize;
		private int numOfElm;

		private SegTree(int numOfElm) {
			this.numOfElm = numOfElm;
			numOfElmSize = 1;
			/*
			 * サイズの調整
			 * 必要要素数の決定
			 * 例：numOfElm==3 なら numOfElmSize==4
			 */
			while (numOfElmSize < numOfElm) {
				numOfElmSize *= 2;
			}

			/*
			 * 配列の作成
			 * numOfElm==3 なら size==8
			 */
			dat = new long[numOfElmSize * 2];
			Arrays.fill(dat, Integer.MAX_VALUE);
		}

		/**
		 * 親のノードを作る
		 */
		private void update() {
			/*
			 * segment tree
			 * leafの配置が後ろから詰められているので、後ろから探す
			 * dat[numOfElmSize]       ← 一番左の葉
			 * dat[numOfElmSize + n]   ← 一番右の葉
			 */
			int k = numOfElmSize - 1;
			/*
			 * この時点では葉にしかデータがないので
			 * 配列の一番右端から順次作っていく
			 */
			while (k > 0) {
				/*
				 * k     親
				 * K*2   左側
				 * k*2+1 右側
				 * 一番左端の葉の親から作成していく
				 */
				dat[k] = getInnerGcd(dat[k * 2], dat[k * 2 + 1]);
				k--;
			}

		}

		/**
		 * 値のセット
		 *
		 * @param a
		 * @param val
		 */
		private void set(int a, int val) {
			/*
			 * 最初の葉に該当するものは
			 * 配列の後半にセット
			 * numOfElmSize　以上の場所に入れる
			 */
			dat[a + numOfElmSize] = val;
		}

		/**
		 *
		6
		12 3 6 9 15 11
		 [2147483647, 1, 3, 1, 3, 3, 1, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]

		 1( k 1)
		    |----------------------------------------|
		    |                                        |
		 3(2k 2)                                  1(2k+1 3)
		    |-----------------|                      |------------------------|
		    |                 |                      |                        |
		 3(2k 4)            3(2k+1 5)             3(2k 6)                  2147483647(2k+1 7)
		    |-------|         |------------|         |----------|             |--------------------|
		    |       |         |            |         |          |             |                    |
		 12(2k 8)  3(2K+1 9)  6(2k 10)  9(2K+1 11) 15(2k 12)  11(2K+1 13)   2147483647(2k 14)    2147483647(2k+1 15)


		 iを一つずつ右にずらす場合の遷移を下記に記載
		-------------------
		 [0:0):GCD=0
		 left 8
		 right 8

		 [1:6):GCD=1
		 left 9 -> 5 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [2:6):GCD=1
		 left 10 -> 5 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [0:2):GCD=3
		 left 8 -> 4 -> 2
		 right 10 -> 5 -> 2

		 [3:6):GCD=1
		 left 11 -> 6 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [0:3):GCD=3
		 left 8 -> 4 -> 2
		 right 11 -> 5 -> 2

		 [4:6):GCD=1
		 left 12 -> 6 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [0:4):GCD=3
		 left 8 -> 4 -> 2 -> 1
		 right 12 -> 6 -> 3 -> 1

		 [5:6):GCD=11
		 left 13 -> 7
		 right 14 -> 7
		-------------------
		 [0:5):GCD=3
		 left 8 -> 4 -> 2 -> 1
		 right 13 -> 6 -> 3 -> 1

		 [6:6):GCD=0
		 left 14
		 right 14
		 */
		private long get(int a, int b) {
			long leftGcd = 0;
			long rightGcd = 0;
			int left = a + numOfElmSize;
			int right = b + numOfElmSize;
			//			System.out.println("a:b / " + a + " : " + b + " -- left : right / " + left + " : " + right);
			/*
			 * 親が違う間ループ
			 * 一番上の親までたどって最大公約数を探していく
			 * もし、同じ葉の位置を指定した場合ループに入らないが、
			 * それは(0,0)(n,n)なのでそもそも取得対象外。 -> [:)
			 * なので、むしろ0が返ってほしい。
			 */
			while (left < right) {
				/*
				 * 左が偶数ノードの時は、その範囲全て欲しい。
				 * なので、ここで取得するではなく親を取得したい。
				 * 偶数ノードの時、
				 * 自分 -> 自分の親 -> 対とならない右隣の偶数ノード -> 右隣の親 と遷移
				 * ※全て偶数の場合、途中で奇数になる場合は、奇数ノードの遷移に移る
				 *
				 * ただし、奇数ノードの場合（葉は偶数でもノードは奇数になる場合もある）は、
				 * 子だけとって親をとらずに右に移らないといけないので、
				 * 個々の値を取得（leftGcd==0つまり葉の場合は、葉の値をとる）
				 * ちなみに、leftGcd==0の場合はdat[i]が返る。
				 * 奇数ノードの時、
				 * 自分 -> 対とならない右隣の偶数ノード -> 右隣の親 と遷移
				 */
				if ((left & 1) == 1) {
					leftGcd = getInnerGcd(leftGcd, dat[left]);
					left++;
				}
				/*
				 * 右が奇数ノードの時は、その範囲全て欲しい。。が、
				 * 半開区間なので、右そのままは要らない。
				 * ※numNの部分を取らないけど問題ないのか？については、
				 * 実際のところwk[numN]の値はInfが入っているので無視してOK
				 *
				 * ノードはそのまま親へ行ってほしい(親に格納している値が欲しい)ので偶数ノードに遷移
				 * これで、次に来るときに親に行ける。
				 * rightGcd==0の場合はdat[i]が返る。
				 * 奇数ノードの時、
				 * 自分 -> 対となる左側の偶数ノード -> 自分と左側ノード共通の親 と遷移
				 *
				 * 右が偶数ノードの時、
				 * 自分 -> 親 と遷移
				 */
				if ((right & 1) == 1) {
					--right;
					rightGcd = getInnerGcd(rightGcd, dat[right]);
				}
				//親ノードを選択
				left = left / 2;
				right = right / 2;
				//				System.out.println("left : right / " + left + " : " + right);
			}
			long res = getInnerGcd(leftGcd, rightGcd);
			//			System.out.println("res : " + res);
			return res;
		}

		/**
		 * SegTree用のGCD
		 * @param num1
		 * @param num2
		 * @return
		 */
		private long getInnerGcd(long num1, long num2) {
			long max = Long.max(num1, num2);
			long min = Long.min(num1, num2);
			if (min == 0) {
				return max;
			}
			long amari = max % min;

			while (amari != 0) {
				max = min;
				min = amari;
				amari = max % min;
			}
			return min;

		}
	}

D - Flipping Signs：清書版

• Cよりこっちのほうが簡単だ。。。CにかからずにDやればよかった。。。

• 一回に2個同時にプラスマイナスを反転させる

  • マイナスが偶数ならすべて対をつくってプラスにできる
  • マイナスが奇数なら対を作れない
    • 奇数の場合は、一番絶対値で小さいものをマイナスにするのが合計の最大化ができる

-が偶数　

$A_iとA_{i+1}$を選んで反転させるという条件より、-を消滅させることが可能

• パターン1

	1	2	3	4	合計
	-1	-2	-3	-4	-10
1,2を反転	1	2	-3	-4	-4
3,4を反転	1	2	3	4	10

• パターン2(-が離れていても、-を移動させて消滅させられる)

	1	2	3	4	合計
	-1	2	3	-4	0
1,2を反転	1	-2	3	-4	-2
2,3を反転	1	2	-3	-4	-4
3,4を反転	1	2	3	4	10

-が奇数

$A_iとA_{i+1}$を選んで反転させるという条件より、-を消滅させることが不可能

• パターン1

	1	2	3	4	合計
	1	-2	-3	-4	-8
1,2を反転	-1	2	-3	-4	-6
3,4を反転	-1	2	3	4	8

• パターン2(わざと遠回りに書いている)
  • -を移動して、合計を最大化している
  • 偶数の時は-を消滅させられるが、奇数の時は消滅させられない
  • 代わりに、-を絶対値で最小の値に移動させることができる（図だと$|1|$に-を移動させている）
    • -をつける対象を選択することができる
  • 結果として、パターン1と同じ値にすることが可能

	1	2	3	4	合計
	-1	-2	-3	4	-8
1,2を反転	1	2	-3	4	4
3,4を反転	1	2	3	-4	2
3,4を反転	1	2	-3	4	4
2,3を反転	1	-2	3	4	6
1,2を反転	-1	2	3	4	8

• 別解は理解範囲外

	/*
	 * 処理をマージ
	 */
	private void solveD() {
		int numN = nextInt();
		int[] wk = new int[numN];

		int mCnt = 0;
		long res = 0;
		int zeroCnt = 0;
		for (int i = 0; i < numN; i++) {
			int val = nextInt();
			if (val < 0) {
				mCnt++;
			}
			if (val == 0) {
				zeroCnt++;
			}
			wk[i] = Math.abs(val);
			res += wk[i];
		}
		Arrays.sort(wk);
		if (mCnt % 2 == 0 || zeroCnt > 0) {
			out.println(res);
		} else {
			out.println(res - Math.abs(wk[0]) * 2);
		}

	}

D - Flipping Signs：思考過程の備忘用

• 余計な処理が多いので書き直したけど、多分上の清書版よりは流れがわかりやすい？

	/*
	 * 値を取得したり、カウントしたりのforはマージ可能
	 */
	private void solveD2() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		int mCnt = 0;
		long res = 0;
		int zeroCnt = 0;
		for (int i = 0; i < numN; i++) {
			/*
			 * 0よりちいさいものをカウントしておく
			 */
			if (wk[i] < 0) {
				mCnt++;
			}
			/*
			 * 総合計を取得しておく（abs）
			 */
			res += Math.abs(wk[i]);
			/*
			 * 0をカウントしておく
			 */
			if (wk[i] == 0) {
				zeroCnt++;
			}
		}
		/*
		 * -が偶数または0が一つでもある場合、
		 * 全ての値を+に変換することが可能
		 * その場合、単純に合計を出せばよい
		 */
		if (mCnt % 2 == 0 || zeroCnt > 0) {
			out.println(res);
			return;
		} else {
			/*
			 * -が奇数個で0が一つもない
			 * その場合、|wk[i]|　で一番小さい値を-にすれば最大化できる
			 * 一旦、absで全部書き換え
			 */
			for (int i = 0; i < wk.length; i++) {
				wk[i] = Math.abs(wk[i]);
			}
			//ソート
			Arrays.sort(wk);
			for (int i = 0; i < wk.length; i++) {
				/*
				 * ×2しているのは、
				 * ・本来合計に含まれていてはいけない　総合計 - wk[i]
				 * ・この値を抜いた総合計からさらに-する　総合計 - wk[i] - wk[i]
				 */
				if (wk[i] > 0) {
					out.println(res - Math.abs(wk[i]) * 2);
					return;
				}
			}
		}

	}

D問題：DP解法

• 理解できん
  • editorialみて書いてみただけ

inputに対応したdp[][]の中身書いておくけど、意味わからん。
typical dp contest　やってから戻ってこよう。

【備忘入力値】

5
10 -4 -8 -11 3

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 10 / dp[i][1] : -10
i:2 / dp[i][0] : 6 / dp[i][1] : 14
i:3 / dp[i][0] : 22 / dp[i][1] : 14
i:4 / dp[i][0] : 25 / dp[i][1] : 33
i:5 / dp[i][0] : 30 / dp[i][1] : 36
30

5
10 -4 -8 -11 9

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 10 / dp[i][1] : -10
i:2 / dp[i][0] : 6 / dp[i][1] : 14
i:3 / dp[i][0] : 22 / dp[i][1] : 14
i:4 / dp[i][0] : 25 / dp[i][1] : 33
i:5 / dp[i][0] : 34 / dp[i][1] : 42
34

5
8 8 8 8 8

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 8 / dp[i][1] : -8
i:2 / dp[i][0] : 16 / dp[i][1] : 0
i:3 / dp[i][0] : 24 / dp[i][1] : 8
i:4 / dp[i][0] : 32 / dp[i][1] : 16
i:5 / dp[i][0] : 40 / dp[i][1] : 24
40

5
-8 -8 -8 -8 -8

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : -8 / dp[i][1] : 8
i:2 / dp[i][0] : 16 / dp[i][1] : 0
i:3 / dp[i][0] : 8 / dp[i][1] : 24
i:4 / dp[i][0] : 32 / dp[i][1] : 16
i:5 / dp[i][0] : 24 / dp[i][1] : 40
24

	private void solveD3() {
		int numN = nextInt();
		long[] wk = LongStream.range(0, numN).map(i -> nextInt()).toArray();

		long[][] dp = new long[numN + 1][2];
		dp[0][0] = 0;
		dp[0][1] = Integer.MIN_VALUE;

		for (int i = 0; i < numN; i++) {
			dp[i + 1][0] = Long.max(dp[i][0] + wk[i], dp[i][1] - wk[i]);
			dp[i + 1][1] = Long.max(dp[i][0] - wk[i], dp[i][1] + wk[i]);
			out.println("i:" + i + " / dp[i][0] : " + dp[i][0] + " / dp[i][1] : " + dp[i][1]);
		}
		out.println("i:" + numN + " / dp[i][0] : " + dp[numN][0] + " / dp[i][1] : " + dp[numN][1]);
		out.println(dp[numN][0]);
	}