AtCoder ABC 125 A&B&C&D AtCoder - 125
2019/05/22 Add the problem name
2019/06/27 Added seg tree solution for C problem
A - Biscuit Generator
--T + 0.5 hours can be added for biscuits
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 is $ \ sum_ {i = 1} ^ {n} V_i $ --Y is $ \ sum_ {i = 1} ^ {n} C_i $ -Because it is the maximum value of $ X-Y $ --X should be larger -Do not count pairs with $ 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
--Take the cumulative sum of GCD from the left and right and exclude unnecessary parts
| 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 and 3-5 GCD | |
| i=3 | 1 | 2 | 4 | 5 | 1-2 and 4-5 GCD | |
| i=4 | 1 | 2 | 3 | 5 | 1-3 and 5 GCD | |
| i=5 | 1 | 2 | 3 | 4 | 1-4 GCD |
-When $ i = 3 $, if you take GCD with GCD $ of $ 1-2 and GCD $ of $ 4-5, it will be the total GCD.
- gcd(1-2,4-5)
--To achieve the above, create and merge 1-5 GCD and 5-1 GCD.
/*
*Audio description broadcast
* 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
――Well, because it's a reminder, this is also ...
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);
}
reference: Kenchon's competition professional devotion record For you who want to write a segment tree in Sora Complete domination / query processing technique on the tree Data structure in programming contest Programming Contest Challenge Book P.153 ～
/**
* segment tree version
*
*Input value sample
* [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);
/*
*Before 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]);
}
/*
*Immediately after the set is finished
* [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();
/*
*Immediately after the update is finished
* [P-1]
* [2147483647, 1, 1, 1, 7, 6, 8, 2147483647]
*
*leaf is a value and node is a common divisor
* 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++) {
/*
*Half-open section[)
* 0 - i
*GCD(i not included)
*/
long left = tree.get(0, i);
/*
*Half-open section[)
* i+1 - numN(numN not included)
*GCD
*/
long right = tree.get(i + 1, numN);
res = Long.max(res, getGcd(left, right));
}
out.println(res);
}
/**
* segment tree
*Complete binary 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;
/*
*Size adjustment
*Determining the number of required elements
*Example: numOfElm==If 3 is numOfElmSize==4
*/
while (numOfElmSize < numOfElm) {
numOfElmSize *= 2;
}
/*
*Creating an array
* numOfElm==If 3 is size==8
*/
dat = new long[numOfElmSize * 2];
Arrays.fill(dat, Integer.MAX_VALUE);
}
/**
*Create a parent node
*/
private void update() {
/*
* segment tree
*Since the leaf arrangement is packed from the back, search from the back
* dat[numOfElmSize]← Leftmost leaf
* dat[numOfElmSize + n]← Rightmost leaf
*/
int k = numOfElmSize - 1;
/*
*At this point there is only data on the leaves
*Make sequentially from the rightmost end of the array
*/
while (k > 0) {
/*
*k parent
* K*2 left side
* k*2+1 right side
*Create from the parent of the leftmost leaf
*/
dat[k] = getInnerGcd(dat[k * 2], dat[k * 2 + 1]);
k--;
}
}
/**
*Set of values
*
* @param a
* @param val
*/
private void set(int a, int val) {
/*
*The one that corresponds to the first leaf
*Set in the second half of the array
*Put it in a place larger than 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)
The transition when moving i one by one to the right is described below.
-------------------
[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);
/*
*Loop while parents are different
*Follow to the top parent to find the greatest common divisor
*If you specify the same leaf position, it will not enter the loop,
*that is(0,0)(n,n)Therefore, it is not eligible for acquisition in the first place.-> [:)
*So, rather, I want 0 to be returned.
*/
while (left < right) {
/*
*When the left is an even node, I want the whole range.
*So I want to get the parent instead of getting it here.
*For even nodes
*myself->My parents->Even-numbered nodes on the right that are not paired->Transition with the parent on the right
** If all are even, and if it becomes odd in the middle, move to the transition of odd nodes.
*
*However, in the case of odd nodes (the leaves may be even but the nodes may be odd),
*I have to take only the child and move to the right without taking the parent, so
*Get individual values (leftGcd==0 In other words, in the case of leaves, take the value of leaves)
*By the way, leftGcd==If 0, dat[i]Is returned.
*For odd nodes,
*myself->Even-numbered nodes on the right that are not paired->Transition with the parent on the right
*/
if ((left & 1) == 1) {
leftGcd = getInnerGcd(leftGcd, dat[left]);
left++;
}
/*
*When the right is an odd node, I want the whole range. .. But,
*Since it is a half-open section, you do not need to leave it on the right.
** I don't take the numN part, but is there any problem? about,
*As a matter of fact wk[numN]Since Inf is included in the value of, you can ignore it.
*
*I want the node to go to the parent as it is(I want the value stored in the parent)So transition to even nodes
*Now you can go to your parents the next time you come.
* rightGcd==If 0, dat[i]Is returned.
*For odd nodes,
*myself->Paired left even nodes->Parents and transitions common to you and the left node
*
*When the right is an even node,
*myself->Transition with parent
*/
if ((right & 1) == 1) {
--right;
rightGcd = getInnerGcd(rightGcd, dat[right]);
}
//Select parent node
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;
}
/**
*GCD for SegTree
* @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;
}
}
――This is easier than C. .. .. I should have done D without going to C. .. ..
--Invert plus and minus two at a time ――If the minus is an even number, you can make a pair and make it a plus. --If the minus is odd, you can't make a pair --In the case of odd numbers, the total can be maximized by making the smallest absolute value negative.
- is evenIt is possible to eliminate - from the condition that $ A_i and A_ {i + 1} $ are selected and inverted.
| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| -1 | -2 | -3 | -4 | -10 | |
| 1,Invert 2 | 1 | 2 | -3 | -4 | -4 |
| 3,Invert 4 | 1 | 2 | 3 | 4 | 10 |
--Pattern 2 (Even if - is separated, you can move- to make it disappear)
| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| -1 | 2 | 3 | -4 | 0 | |
| 1,Invert 2 | 1 | -2 | 3 | -4 | -2 |
| 2,Invert 3 | 1 | 2 | -3 | -4 | -4 |
| 3,Invert 4 | 1 | 2 | 3 | 4 | 10 |
- is oddIt is impossible to eliminate - due to the condition that $ A_i and A_ {i + 1} $ are selected and inverted.
| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| 1 | -2 | -3 | -4 | -8 | |
| 1,Invert 2 | -1 | 2 | -3 | -4 | -6 |
| 3,Invert 4 | -1 | 2 | 3 | 4 | 8 |
--Pattern 2 (written in a detour on purpose)
--Move - to maximize the total
-When it is an even number,-can be eliminated, but when it is an odd number, it cannot be eliminated.
-instead of,-Can be moved to the minimum value in absolute value (in the figure)-Is moving)
--You can select the target to add -
--As a result, it can be the same value as pattern 1.
| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| -1 | -2 | -3 | 4 | -8 | |
| 1,Invert 2 | 1 | 2 | -3 | 4 | 4 |
| 3,Invert 4 | 1 | 2 | 3 | -4 | 2 |
| 3,Invert 4 | 1 | 2 | -3 | 4 | 4 |
| 2,Invert 3 | 1 | -2 | 3 | 4 | 6 |
| 1,Invert 2 | -1 | 2 | 3 | 4 | 8 |
--Another solution is out of understanding
/*
*Merge processes
*/
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);
}
}
――I rewrote it because there is a lot of extra processing, but maybe the flow is easier to understand than the clear copy version above?
/*
*For to get or count values can be merged
*/
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++) {
/*
*Count things less than 0
*/
if (wk[i] < 0) {
mCnt++;
}
/*
*Get the grand total (abs)
*/
res += Math.abs(wk[i]);
/*
*Count 0
*/
if (wk[i] == 0) {
zeroCnt++;
}
}
/*
* -If is even or at least one 0
*All values+Can be converted to
*In that case, simply add up
*/
if (mCnt % 2 == 0 || zeroCnt > 0) {
out.println(res);
return;
} else {
/*
* -Is an odd number and there is no 0
*In that case,|wk[i]|The smallest value in-Can be maximized by
*Rewrite everything with abs once
*/
for (int i = 0; i < wk.length; i++) {
wk[i] = Math.abs(wk[i]);
}
//sort
Arrays.sort(wk);
for (int i = 0; i < wk.length; i++) {
/*
*× 2 is
*・ Total total that should not be included in the total- wk[i]
*・ Further from the total sum without this value-Total total- wk[i] - wk[i]
*/
if (wk[i] > 0) {
out.println(res - Math.abs(wk[i]) * 2);
return;
}
}
}
}
――I don't understand --Editorial I just tried to write
I'll write the contents of dp [] [] corresponding to input, but I don't understand the meaning.
Let's come back after doing a typical dp contest.
[Note input value]
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]);
}
Recommended Posts