Codeforces Round #511 (Div. 2) に参加した感想

問題

Dashboard - Codeforces Round #511 (Div. 2) - Codeforces

Codeforcesの記事を書くのは久しぶりですが、記事にしていない回も参加はしていました。

A. Little C Loves 3 I

は の倍数ではない整数とします。

を満たす整数 を求める問題です。

が の倍数かそうでないかで、場合分けをすればよいです。

コード

import java.util.Scanner;

public class ProbemA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.close();
        if(n == 3) {
            System.out.println("1 1 1");
            System.exit(0);
        }
        if(n % 3 == 0) {
            int a = n / 3;
            int b = n / 3;
            int c = n / 3;
            if(a % 3 == 0) {
                a -= 2;
                b += 1;
                c += 1;
                System.out.println(a + " " + b + " " + c);
            }else {
                System.out.println(a + " " + b + " " + c);
            }
        }else {
            int a = n - 3;
            int b = 2;
            int c = 1;
            System.out.println(a + " " + b + " " + c);
        }
    }
}

B. Cover Points

第一象限に内にある格子点が与えられます。格子点は整数なので、全ての格子点を内部に持つ三角形の斜辺の方程式の候補は、

となります。 条件を満たす の最小値を答えれば良いです。

と変形できるので、この の最大値を求めれば良いです。

コード

import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[]x = new int[n];
        int[]y = new int[n];
        for(int i = 0; i < n; i++) {
            x[i] = scan.nextInt();
            y[i] = scan.nextInt();
        }
        scan.close();
        int max = 0;
        for(int i = 0; i < n; i++) {
            max = Math.max(max, x[i]+y[i]);
        }
        System.out.println(max);
    }
}

C. Enlarge GCD

WAとTLEを出しまくった問題です。コンテスト後に何度も挑戦してやっとACとなりました。基本的な方針は分かっていたんですが、ACを取るまでに苦労しました。

考え方

の最大公約数を とします。 の要素を で割ります。

の重複している要素を消したいので、 HashSet に の要素を格納することと、その要素の個数を数えます。また、重複していない要素の個数は となります。

このようにすることで、重複している要素がなくなり、計算量の減少が見込めます。

また、 で割る理由を考えると、 としたとき、最大公倍数は となります。

の部分集合 の最大公約数は になり、題意を満たします。また、 の最大公約数 でこの部分集合を割ると、 となりこの最大公約数は となりますが、割る前の部分集合を考えると、 となり題意を満たします。

つまり、 で割った後の集合の部分集合の最大公約数が でなければ、 より大きい部分集合の最大公約数が存在するということです。

ここで、 より大きい部分集合の最大公約数が存在する部分集合の要素の最大個数を求めることが必要です。そのような値を とすると、答えは となります。ただし、 ならば答えは です。

素数を利用して を求める

HashSet に の要素を格納したとします。

までのエラトステネスの篩を作成します。

また、素数をキーにもち、値が のHashMapを用意します。

HashSetの要素 を一つずつしらべ、その値が素数ならば、キーが のMapの値を の個数分増やします。

が素数でない場合、 以下の素数で が素数になるまで割り続けます。ここで、 を割り切る素数を とすると、 をキーに持つMapの値を 増やします。

例を挙げると、HashSetの要素が のとき、 は (素数)で割ることができるので、

となり、 は素数なので、キーが と のMapの値を 増やします。

まあ、やっていることは素因数分解みたいなものです。

コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

public class ProblemC {
    static int d = 15000000;
    static boolean[] isPrime = new boolean[d + 1];

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int[]a = new int[n];
        for(int i = 0; i < n; i++) {
            int t = Integer.parseInt(tokenizer.nextToken());
            a[i] = t;
        }

        int[]k = new int[d + 1];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Set<Integer> set = new HashSet<Integer>();
        int g = gcd(a[0], a[1]);
        for(int i = 2; i < n; i++) {
            g = gcd(g, a[i]);
        }

        for(int i = 0; i < n; i++) {
            a[i] = a[i] / g;
            k[a[i]]++;
            set.add(a[i]);
        }
        
        // エラトステネスの篩
        aryPrime();

        // 素数リスト
        List<Integer> list = new ArrayList<Integer>();

        int max = (int)Math.sqrt(d);
        for(int i = 2; i <= max; i++) {
            if(isPrime[i]) {
                list.add(i);
            }
        }

        for(int i : set) {
            if(isPrime[i]) {
                if(map.containsKey(i)) {
                    map.put(i, map.get(i) + k[i]);
                }else {
                    map.put(i, k[i]);
                }
            }else {
                int t = i;
                for(int j = 0; j < list.size(); j++) {
                    if(isPrime[t]) {
                        if(map.containsKey(t)) {
                            map.put(t, map.get(t) + k[i]);
                        }else {
                            map.put(t, k[i]);
                        }
                        break;
                    }else {
                        int p = list.get(j);
                        if(t % p == 0) {
                            if(map.containsKey(p)) {
                                map.put(p, map.get(p) + k[i]);
                            }else {
                                map.put(p, k[i]);
                            }
                            while(t % p == 0) {
                                t = t / p;
                            }
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int key : map.keySet()) {
            int t = map.get(key);
            if(ans < t) {
                ans = t;
            }
        }
        if(ans == 0) {
            System.out.println(-1);
        }else {
            System.out.println(n - ans);
        }

    }
    static void aryPrime(){
        int l = isPrime.length;
        for(int i = 0; i < l; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = false;
        isPrime[1] = false;
        int max = (int)Math.sqrt(l);
        for(int i = 2; i <= max; i++) {
            if(isPrime[i]) {
                for(int j = i * 2; j < l; j += i) {
                    isPrime[j] = false;
                }
            }

        }
    }
     static int gcd(int m, int n) {
        if(m < n) return gcd(n, m);
        if(n == 0) return m;
        return gcd(n, m % n);
    }
}

感想

C問題が難しかったんですが、解けて良かったです。数学よりの問題でしたが、実装が結構難しかったです。

Codeforcesの過去問などにはまだ手を出せていないので、yukicoderやAtCoderやAOJの問題を解いていきたいです。