AtCoder Beginner Contest 182 Participation Article

Participated in AtCoder Beginner Contest 182 about 20 minutes late. Well, even if it's on time, I can't finish it, so I'll do what I can.

A - twiblr

Just calculate the upper limit of the number of followers according to the rules and subtract the current number of followers.

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        try(Scanner s = new Scanner(System.in)){
        	System.out.println(s.nextInt() * 2 + 100 - s.nextInt());
        }
    }
}

B - Almost GCD Shouldn't we find the greatest common divisor using the Euclidean algorithm? I thought, but I was convinced by the example. If the greatest common divisor is 1 as a whole, it will be bad. Then, I noticed when I thought that I should factor each number into prime factors and select the one with many common prime factors. Then, isn't it much different even if you try and divide everything from the beginning?

import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            int n = s.nextInt();
            int[] a = new int[n];
            int max = 0;
            for (int i = 0; i < n; i++) {
                a[i] = s.nextInt();
                max = Math.max(max, a[i]);
            }
            int maxCount = 0;
            int tempK = 0;
            for (int k = 2; k <= max; k++) {
                int count = 0;
                for (int x : a) {
                    if (x % k == 0) {
                        count++;
                    }
                }
                if (count > maxCount) {
                    tempK = k;
                    maxCount = count;
                    if (maxCount == n) {
                        break;
                    }
                }
            }
            System.out.println(tempK);
        }
    }
}

C - To 3 Use the fact that the remainder of dividing a number by 3 is equal to the remainder of dividing the sum of the numbers in each place by 3. Since the rest of the story can be discussed only by the remainder, it is decomposed into each part and converted to the remainder divided by 3. From here, it's hard to divide the cases. When I think that the remainder of the total is divided by 0, 1, and 2, I notice that there is.

If the total remainder is 1, and there are no remaining 1 digits, then only the remainder 0 and the remainder 2 make up the digits. If all the digits are the remainder 0, the total remainder will be 0, and if there is only one digit of the remainder 2, the total remainder should be 2. There will be at least two extra 2 digits. If you get rid of these two, you can make the remainder 0. The same applies when the total remainder is 2, so the judgment could be written in 5 lines, excluding the "find column" process.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            int[] x = s.next().chars().map(i -> (i - '0') % 3).toArray();
            int r = Arrays.stream(x).sum() % 3;
            System.out.println(remove(x, r));
        }
    }
    
    private static int remove(int[] x, int r) {
        if (r == 0) return 0;
        if (x.length == 1) return -1;
        if (find(x, r)) return 1;
        if (x.length == 2) return -1;
        return 2;
    }
    
    private static boolean find(int[] x, int target) {
        for (int a : x) {
            if (a == target){
                return true;
            }
        }
        return false;
    }
}

D - Wandering At first I thought I'd do it honestly. I wrote it with anxiety about the execution time, While writing, I was inspired to use the idea of cumulative sum and rewrote it. Since there should be a maximum amount that can move in the positive direction in a group of $ A_1 $ ~ $ A_i , (i = 1,2, \ dots, N) $. Record and compare the position when the maximum amount of movement is made. ** Do it here. ** I knew that it would overflow if I didn't make it long from the range of numbers, Since the int array that records $ A_i $ was reused as it is for the cumulative sum, it became WA once. Remake it into a long array and AC.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            s.nextLine();
            long[] a = Arrays.stream(s.nextLine().split(" "))
                                .mapToLong(Long::parseLong)
                                .toArray();
            long[] max = new long[a.length];
            max[0] = a[0];
            for (int i = 1; i < a.length; i++) {
                a[i] += a[i - 1];
                max[i] = Math.max(max[i - 1], a[i]);
            }
            
            
            long maxP = 0;
            long p = 0;
            for (int i = 0; i < a.length; i++) {
                maxP = Math.max(maxP, p + max[i]);
                p += a[i];
            }
            System.out.println(maxP);
        }
    }
}

At this point, there was about 6 minutes left, and E was not in time at all.

Recommended Posts

AtCoder Beginner Contest 182 Participation Article
AtCoder Beginner Contest 168
AtCoder Beginner Contest 132 D Problem
Solve AtCoder Beginner Contest 151 in java
Solve AtCoder Beginner Contest 150 in java
Solve AtCoder Beginner Contest 153 in java
Solve AtCoder Beginner Contest 175 in java
Solve AtCoder Beginner Contest 160 in java
Solve AtCoder Beginner Contest 152 in java
Solve AtCoder Beginner Contest 156 in java
AtCoder Beginner Contest 167 C Problem (Java)
AtCoder Beginner Contest 169 A, B, C with ruby
AtCoder Beginner Contest 170 A, B, C up to ruby
Solving with Ruby AtCoder ACL Beginner Contest C Union Find (DSU)
Learning Ruby with AtCoder 6 [Contest 168 Therefore]
[Beginner] Let's solve AtCoder problem with Ruby while looking at the article!