山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 111 の感想

AtCoder Beginner Contest 111

今回はC問題まで解くことができました。B問題はいつもより易しいと思いました。

A - AtCoder Beginner Contest 999

与えられて数字の [tex; 1] と  9 を交換する問題です。文字列として扱うと良いと思いました。

コード

import java.util.Scanner;

public class ProblemA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String n = scan.next();
        scan.close();
        for(int i = 0; i < n.length(); i++) {
            if(n.charAt(i) == '9') {
                System.out.print(1);
            }else if(n.charAt(i) == '1') {
                System.out.print(9);
            }else {
                System.out.print(n.charAt(i));
            }
        }
        System.out.println();
    }
}

B - AtCoder Beginner Contest 111

あまり考えずに全探索してしまいました。解説を見ると  111 の倍数を探せば良いようですね。

コード

import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String n = scan.next();
        scan.close();
        int a = Integer.parseInt(n);
        for(int i = a; i <= 999; i++) {
            String k = Integer.toString(i);
            char c0 = k.charAt(0);
            char c1 = k.charAt(1);
            char c2 = k.charAt(2);
            if(c0 == c1 && c1 == c2) {
                System.out.println(k);
                System.exit(0);
            }
        }
    }
}

C - /\/\/\/

解法は分かったんですが、実装に手こずりました。

数列の要素番号が奇数と偶数のグループに分けて、一番多く出現する数字と二番目に多く出現する数字を得ることで解答できます。

また、出現する数字が被ってはいけないので、二番目に多く出現した数字が必要となります。

つまり、最頻値とその次の値が欲しいわけですね。

かなり汚いコードとなってしまったので、出現回数順にソートするプログラムを書かないといけませんでした。

コード

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

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[]v = new int[n];
        for(int i = 0; i < n; i++) {
            v[i] = scan.nextInt();
        }
        scan.close();
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();
        for(int i = 0; i < n/2; i++) {
            map1.merge(v[2 * i], 1, (val1, val2) -> (val1 + val2));
            map2.merge(v[2 * i + 1], 1, (val1, val2) -> (val1 + val2));
        }
        if(map1.size() == 1 && map2.size() == 1) {
            if(v[0] != v[1]) {
                System.out.println(0);
            }else {
                System.out.println(n/2);
            }
            System.exit(0);
        }
        if(map1.size() == 1) {
            int kMax = -1;
            int max = 0;
            for(int k : map2.keySet()) {
                if(max < map2.get(k)) {
                    kMax = k;
                    max = map2.get(k);
                }
            }
            if(v[0] != kMax) {
                int ans = n/2 -  map2.get(kMax);
                System.out.println(ans);
            }else {
                int t = kMax;
                kMax = -1;
                max = 0;
                for(int k : map2.keySet()) {
                    if(max < map2.get(k) && k != t) {
                        kMax = k;
                        max = map2.get(k);
                    }
                }
                int ans = n/2 - map2.get(kMax);
                System.out.println(ans);
            }
            System.exit(0);
        }
        if(map2.size() == 1) {
            int kMax = -1;
            int max = 0;
            for(int k : map1.keySet()) {
                if(max < map1.get(k)) {
                    kMax = k;
                    max = map1.get(k);
                }
            }
            if(v[1] != kMax) {
                int ans = n/2 - map1.get(kMax);
                System.out.println(ans);
            }else {
                int t = kMax;
                kMax = -1;
                max = 0;
                for(int k : map1.keySet()) {
                    if(max < map1.get(k) && k != t) {
                        kMax = k;
                        max = map1.get(k);
                    }
                }
                int ans = n/2 - map1.get(kMax);
                System.out.println(ans);
            }
            System.exit(0);
        }
        int t0 = 0;
        int t1 = 0;
        int k0 = 0;
        int k1 = 0;
        int kMax = -1;
        int max = 0;
        for(int k : map1.keySet()) {
            if(max < map1.get(k)) {
                kMax = k;
                max = map1.get(k);
            }
        }
        t0 = kMax;
        kMax = -1;
        max = 0;
        for(int k : map1.keySet()) {
            if(max < map1.get(k) && k != t0) {
                kMax = k;
                max = map1.get(k);
            }
        }
        t1 = kMax;
        kMax = -1;
        max = 0;
        for(int k : map2.keySet()) {
            if(max < map2.get(k)) {
                kMax = k;
                max =  map2.get(k);
            }
        }
        k0 = kMax;
        kMax = -1;
        max = 0;
        for(int k : map2.keySet()) {
            if(max < map2.get(k) && k != k0) {
                kMax = k;
                max = map2.get(k);
            }
        }
        k1 = kMax;
        if(k0 != t0) {
            int ans = n - map1.get(t0) - map2.get(k0);
            System.out.println(ans);
            System.exit(0);
        }else {
            int m1 = n - map1.get(t0) - map2.get(k1);
            int m2 = n - map1.get(t1) - map2.get(k0);
            int ans = Math.min(m1, m2);
            System.out.println(ans);
        }
    }
}

感想

C問題はもっと早く解かないといけないと思いました。D問題は部分点のコードすら検討もつかなかったです。

まあ、今回はC問題まで解けたので良かったです。