第四回 アルゴリズム実技検定 (バーチャル参加) [A-F]

AtCoder による 第四回 アルゴリズム実技検定 の問題を解きました.

f:id:suisen_kyopro:20201110204452p:plain

A - 中央値

問題文

ソートして  A,  B,  C と一致判定するのが楽?

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int[] s = new int[]{a, b, c};
        Arrays.sort(s);
        if (s[1] == a) {
            pw.println('A');
        } else if (s[1] == b) {
            pw.println('B');
        } else {
            pw.println('C');
        }
    }

B - 電卓

問題文

 Y=0 の場合分けはいいとして,  100X/Y に小数点を挿入すると誤差が怖くない.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int x = sc.nextInt();
        int y = sc.nextInt();
        if (y == 0) {
            pw.println("ERROR");
            return;
        } else {
            int res = x * 100 / y;
            int p0 = res % 10;
            int p1 = res / 10 % 10;
            int p2 = res / 100;
            pw.print(p2).print('.').print(p1).println(p0);
        }
    }

C - 隣接カウント

問題文

やるだけ. 配列外参照にだけ注意 (入力を受け取るときに周りを '.' で囲っても良い).

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] s = sc.charArrays(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int c = s[i][j] == '#' ? 1 : 0;
                for (int d = 0; d < 8; d++) {
                    int ni = i + Const.dx8[d];
                    int nj = j + Const.dy8[d];
                    if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
                    if (s[ni][nj] == '#') {
                        c++;
                    }
                }
                pw.print(c);
            }
            pw.println();
        }
    }

D - 分身

問題文

この辺りから問題のレベルが少し上がる.

まず,  x\geq (最左の忍者よりも左にあるマスの数),  y\geq (最右の忍者よりも右にあるマスの数) が必要. 加えて,  x+y\geq (隣り合う忍者の間の距離の最大値) が必要. 逆に, これで十分であることも言える.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        char[] s = sc.nextChars();
        int max = 0;
        for (int i = 0; i < n;) {
            while (i < n && s[i] == '#') {
                i++;
            }
            if (i == n) break;
            int c = 0;
            while (i < n && s[i] == '.') {
                i++;
                c++;
            }
            max = Math.max(max, c);
        }
        int l = 0;
        while (s[l] == '.') {
            l++;
        }
        int r = n - 1;
        while (s[r] == '.') {
            r--;
        }
        r = n - 1 - r;
        if (l + r >= max) {
            pw.print(l).print(' ').println(r);
        } else {
            pw.print(l).print(' ').println(max - l);
        }
    }

E - アナグラム

問題文

全ての並び替えを全探索する. Java には next_permutation が標準にないのでライブラリとして持っておくべき.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        char[] s = sc.nextChars();
        for (int[] p : Permutation.ofAscending(n)) {
            char[] t = new char[n];
            for (int i = 0; i < n; i++) {
                t[i] = s[p[i]];
            }
            if (Arrays.equals(s, t)) continue;
            CharArrays.reverse(t);
            if (Arrays.equals(s, t)) continue;
            CharArrays.reverse(t);
            pw.println(t);
            return;
        }
        pw.println("None");
    }

F - 構文解析

問題文

問題名で身構えてしまうけど, 中身を読んで安心.

まず, HashMap<String, Integer> を用意して文字列の頻度を数えておく.  c_i=頻度が i である文字列の数 となる  c を用意すると,  K 番目の文字列の頻度  x を求めることができる.

このとき,  c_x\gt 1 なら "AMBIGUOUS". そうでなければ頻度  x の文字列は一意に定まるので, Map を走査して見つければ OK.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        String[] s = sc.strings(n);
        HashMap<String, Integer> map = new HashMap<>();
        for (String t : s) {
            map.putIfAbsent(t, 0);
            map.put(t, map.get(t) + 1);
        }
        int[] c = new int[100001];
        for (var e : map.values()) {
            c[e]++;
        }
        int ans = 0;
        int cnt = 0;
        for (int i = 100000; i >= 1; i--) {
            cnt += c[i];
            if (cnt >= k) {
                if (c[i] > 1) {
                    pw.println("AMBIGUOUS");
                    return;
                } else {
                    ans = i;
                    break;
                }
            }
        }
        for (var e : map.entrySet()) {
            if (e.getValue() == ans) {
                pw.println(e.getKey());
                return;
            }
        }
    }