AtCoder ABC 129 A&B&C&D AtCoder - 129
I melted it in B for more than 50 minutes and I almost cried on the way
E and F will be updated later this month to see the solution!
A - Airplane
I was confused by the input example, but if you read it normally, you can see that the following is asked. .. ..
--Since the time required to move A-B, B-C and C-A is given, find the shortest time that all A-B-C can be turned
private void solveA() {
int p = nextInt();
int q = nextInt();
int r = nextInt();
out.println(Math.min(q + r, Math.min(p + q, p + r)));
}
B - Balance
I couldn't understand why input example 2 was so, so I melted it a lot. .. .. Reason? For some reason, you should sort what you typed! Because I thought. I leave a sort in the comment out for self-discipline. .. ..
The solution is as follows
--Move i to 1 --N-1 and get the smallest difference between the total up to 0-i and the total up to i + 1 --N-1.
So, in the actual production, I used the cumulative sum (I couldn't understand the input example 2 and thought that it wasn't a full search, right?), But it was overkill. ..
private void solveB() {
int n = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
//I'll put sorted... int[] wk = IntStream.range(0, n).map(i -> nextInt()).sorted().toArray();
int[] rui = new int[n];
//0-Perform the cumulative sum of N
rui[0] = wk[0];
for (int i = 1; i < rui.length; i++) {
rui[i] = rui[i - 1] + wk[i];
}
long res = Integer.MAX_VALUE / 10;
/*
*I to n from 1 to actually find the numerical value of T candidate-Move to 1
*Do not go to the very beginning or the end to divide into two groups
* (rui[n - 1] - rui[i]) -> i+Sum from 1 to N
* rui[i] ->Sum from 0 to i
*/
for (int i = 1; i < n - 1; i++) {
res = Math.min(res, Math.abs((rui[n - 1] - rui[i]) - rui[i]));
}
out.println(res);
}
――I think you can write more beautifully in sum1 and sum2, but I haven't come up with it.
private void solveB2() {
int n = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
long res = Integer.MAX_VALUE / 10;
for (int i = 1; i < n - 1; i++) {
int sum1 = 0;
int sum2 = 0;
for (int j = 0; j < n; j++) {
if (j <= i) {
sum1 += wk[j];
} else {
sum2 += wk[j];
}
}
res = Math.min(res, Math.abs(sum1 - sum2));
}
out.println(res);
}
C - Typical Stairs
――As the problem name suggests, a really typical DP
--If you set the DP size to n + 3 instead of n + 1, you don't need to judge ʻi + 2 <= n or ʻi + 1 <= n.
I haven't finished everything (I can't solve the high score problem at all!), But the following contests are useful.
AtCoder --Educational DP Contest / DP Summary Contest AtCoder - Typical DP Contest drken's article: A super introduction to dynamic programming! Educational DP Contest A to E Problem Explanations and Similar Issues drken's article: Explanation and similar problems of F to J problems in Educational DP Contest
private void solveC() {
int n = nextInt();
int m = nextInt();
Set<Integer> key = new HashSet<Integer>();
for (int i = 0; i < m; i++) {
key.add(nextInt());
}
long[] dp = new long[n + 1];
dp[0] = 1;
long CONST_MOD = (long) (Math.pow(10, 9) + 7);
for (int i = 0; i <= n; i++) {
if (key.contains(i)) {
continue;
}
if (i + 2 <= n) {
dp[i + 2] = dp[i + 2] % CONST_MOD + dp[i] % CONST_MOD;
}
if (i + 1 <= n) {
dp[i + 1] = dp[i + 1] % CONST_MOD + dp[i] % CONST_MOD;
}
}
out.println(dp[n] % CONST_MOD);
}
D - Lamp
――I think it was a fairly typical cumulative sum problem.
――Image of taking cumulative sums vertically and horizontally and superimposing them at the end ――How many squares can you illuminate vertically? How many squares do you illuminate next to? First make --In the middle of the code, describe what kind of operation you are doing based on input example 1 in the comment --By accumulating, when you look at [i] [j], you can add the result of the cumulative sum of H and the result of the cumulative sum of W.
I think it's slow to write code because I'm writing while commenting during the contest
private void solveD2() {
int h = nextInt();
int w = nextInt();
char[][] wk = new char[h][w];
for (int i = 0; i < wk.length; i++) {
wk[i] = next().toCharArray();
}
int[][] rui1 = new int[h][w];
/*
*Create cumulative sum for W
*/
for (int i = 0; i < h; i++) {
int cnt = 0;
/*
*Input example 1 looks like the following(Side by side)
* 012012
* 123450
* 123401
* 010123
*/
for (int j = 0; j < w; j++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui1[i][j] = cnt;
}
/*
*Smooth the accumulated results(Side by side)
* 012012
* 123450
* 123401
* 010123
*To
* 022022
* 555550
* 444401
* 010333
*Conversion to
*/
for (int j = w - 1; j > 0; j--) {
if (rui1[i][j - 1] != 0 && rui1[i][j] != 0) {
rui1[i][j - 1] = rui1[i][j];
}
}
}
int[][] rui2 = new int[h][w];
/*
*Create cumulative sum for H
*/
for (int j = 0; j < w; j++) {
int cnt = 0;
/*
*Input example 1 looks like the following(Vertically)
* 011011
* 122120
* 233201
* 040312
*/
for (int i = 0; i < h; i++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui2[i][j] = cnt;
}
/*
*Smooth the accumulated results(Vertically)
* 011011
* 122120
* 233201
* 040312
*To
* 043021
* 243320
* 243302
* 040312
*Conversion to
*/
for (int i = h - 1; i > 0; i--) {
if (rui2[i - 1][j] != 0 && rui2[i][j] != 0) {
rui2[i - 1][j] = rui2[i][j];
}
}
}
/*
*Since it is cumulative, lick it all
*However, the central part where the top, bottom, left, and right overlap-1
*/
long res = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
long cnt = rui1[i][j] + rui2[i][j] - 1;
res = Math.max(res, cnt);
}
}
out.println(res);
}
Recommended Posts