AtCoder Beginner Contest 110 の感想

AtCoder Beginner Contest 110

今回はB問題まで解くことができました。C問題が分からなかったので、途中でCodeforcesに参加しました。こちはC問題まで解けました。

abc110.contest.atcoder.jp

A - Maximize the Formula

数字を入れ替えてできる式の最大値を求める問題です。全通り試すか、数字をソートして解答することが考えられます。

コード

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        int C = scan.nextInt();
        scan.close();
        int max = 10 * A + B + C;
        max = Math.max(max, 10 * B + A + C);
        max = Math.max(max, 10 * C + A + B);
        System.out.println(max);
    }
}

B - 1 Dimensional World's Tale

与えられた数列の最小値と最大値を求めて条件と比較する問題です。

僕はArrays.sort()で整列させてから最小値と最大値を求めました。

import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int X = scan.nextInt();
        int Y = scan.nextInt();
        int[]x = new int[N];
        int[]y = new int[M];
        for(int i = 0; i < N; i++) {
            x[i] = scan.nextInt();
        }
        for(int i = 0; i < M; i++) {
            y[i] = scan.nextInt();
        }
        scan.close();
        Arrays.sort(x);
        Arrays.sort(y);
        if(x[N - 1] < y[0]) {
            int k = y[0];
            if(k > X && k <= Y) {
                System.out.println("No War");
            }else {
                System.out.println("War");
            }
        }else {
            System.out.println("War");
        }
    }
}

C - String Transformation

コンテスト中は、Mapを使って解答するのかな？と思ったんですが、実装はできませんでした。

解説では置換表をつかって解答するようです。良く分からなかったので、他の人の解説を待ちたいと思います。

コード

import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String S = scan.next();
        String T = scan.next();
        scan.close();
        int l = S.length();
 
        int[]R1 = new int[26];
        int[]R2 = new int[26];
        Arrays.fill(R1, -1);
        Arrays.fill(R2, -1);
        // 'a' = 97
        int[]s = new int[l];
        int[]t = new int[l];
        for(int i = 0; i < l; i++) {
            s[i] = (int)S.charAt(i) - 97;
            t[i] = (int)T.charAt(i) - 97;
        }
        for(int i = 0; i < l; i++) {
            if(R1[s[i]] >= 0) {
                if(R1[s[i]] != t[i]) {
                    System.out.println("No");
                    System.exit(0);
                }
            }else {
                R1[s[i]] = t[i];
            }
            if(R2[t[i]] >= 0) {
                if(R2[t[i]] != s[i]) {
                    System.out.println("No");
                    System.exit(0);
                }
            }else {
                R2[t[i]] = s[i];
            }
        }
        System.out.println("Yes");
    }
}

D - Factorization

二項係数のmodを取るやつが難しいと思いました。

drken1215.hatenablog.com

コード

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class ProblemD {
    static final int MAX = 1000005;
    static final int MOD = 1000000007;
    static long[]fact = new long[MAX];
    static long[]factInv = new long[MAX];
    static long[]inv = new long[MAX];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        long M = scan.nextLong();
        scan.close();
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        long m = M;
        for(long i = 2; i * i <= M; i++) {
            if(m % i == 0) {
                int cnt = 1;
                m = m / i;
                while(m % i == 0) {
                    m = m / i;
                    cnt++;
                }
                map.put(i, cnt);
            }
        }
        if(m > 1) {
            if(map.containsKey(m)) {
                map.put(m, map.get(m) + 1);
            }else {
                map.put(m, 1);
            }
        }
        factMOD();
        invMOD();
        factInvMOD();

        long ans = 1;
        for(int i : map.values()) {
            ans *= combMOD(N + i - 1, i) % MOD;
            ans = ans % MOD;
        }
        System.out.println(ans % MOD);
    }

    //
    static void factMOD() {
        fact[0] = 1;
        for(int i = 1; i < MAX; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
    }
    static void invMOD() {
        inv[0] = 1;
        inv[1] = 1;
        for(int i = 2; i < MAX; i++) {
            inv[i] = MOD - inv[(int)(MOD % i)] * (MOD / i) % MOD;
        }
    }
    static void factInvMOD() {
        factInv[0] = 1;
        for(int i = 1; i < MAX; i++) {
            factInv[i] = factInv[i - 1] * inv[i] % MOD;
        }
    }
    static long combMOD(int n, int k) {
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        return fact[n] * ((factInv[k] * factInv[n - k]) % MOD) % MOD;
    }
}

感想

9月は頑張って問題を解いているんですが、結果は微妙でした。まあ、Codeforcesの方は段々と問題が解けるようになっているので良いか。

今度はC問題が解けると良いですね。