AtCoder Beginner Contest 182 参戦記事 #Java

AtCoder Beginner Contest 182に20分ほど遅れて参戦。
まあ時間通りでも最後まではいけないので、やれることをやる。

A - twiblr

ルール通りフォロー数の上限を計算し、現在のフォロー数を引くだけ。

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

ユークリッドの互除法で最大公約数求めればいいんじゃないか？と思ったが、例を見て納得。全体での最大公約数が1だとまずいことになる。
となると、それぞれの数を素因数分解して、共通する素因数が多いものを選べばいい…と思ったあたりで気づく。
だったら、最初から全部試し割りしてもさほど変わらなくないか？

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

ある数を3で割った余りは、その数の各位の数字の合計を3で割った余りに等しいことを利用。
余りの話は、余りだけで議論できるので、各位に分解して3で割った余りに変換。
ここから場合分けに四苦八苦。合計の余りが0，1，2の時で分けて、と考えていると、あることに気づく。

合計余りが1の場合で、余り1の桁がない場合は、桁を構成しているのが余り0と余り2だけという事になる。
全部の桁が余り0であれば合計余りは0になり、余り2の桁が1つだけなら合計余り2になるはずなので、
少なくとも余り2の桁が2つあることになる。この2つを抜けば、余り0にすることができる。
合計余りが2の場合も同様なので、「桁を探す」処理を除くと、判定が5行で書けた。

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;
    }
}

最初は愚直にやろうと思った。実行時間的に不安を覚えながら書いていったが、
書いているうちに、累積和の考え方が使えそうだとひらめき、書き直し。
$A_1$~$A_i\,(i=1,2,\dots ,N)$のひとかたまりで、正方向に動ける最大量があるはずなので、
その最大量動いた時の位置を記録し、比較する。
ここでやらかし。数値の範囲からlongにしないとあふれることは認識していたのに、
$A_i$を記録するint配列をそのまま累積和に再利用してしまったため、一回WAになってしまった。
longの配列に作り直して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);
        }
    }
}

この時点で残り6分程度で、Eは全く間に合わず。

AtCoder Beginner Contest 182 参戦記事

A - twiblr

B - Almost GCD

C - To 3

D - Wandering