AtCoder による 第四回 アルゴリズム実技検定 の問題を解きました.
A - 中央値
ソートして , , と一致判定するのが楽?
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 - 電卓
の場合分けはいいとして, に小数点を挿入すると誤差が怖くない.
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 - 分身
この辺りから問題のレベルが少し上がる.
まず, , が必要. 加えて, が必要. 逆に, これで十分であることも言える.
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>
を用意して文字列の頻度を数えておく. となる を用意すると, 番目の文字列の頻度 を求めることができる.
このとき, なら "AMBIGUOUS"
. そうでなければ頻度 の文字列は一意に定まるので, 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; } } }