AtCoder Beginner Contest 215(Rated範囲外)
- A - Your First Judge
- B - log2(N)
- C - One More aab aba baa
- D - Coprime 2
- E - Chain Contestant
- F - Dist Max 2
コンテスト前のレート:2101
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:292位(2000点、65分59秒)
A - Your First Judge
思考過程
- 完全に一致するかどうかは、Stringのequalsメソッドで判定できる。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); String s = sc.next(); sc.close(); if (s.equals("Hello,World!")) { System.out.println("AC"); } else { System.out.println("WA"); } } }
ここまで1分02秒+0ペナ。806位。
B - log2(N)
思考過程
- 条件を満たさなくなるまで、回数をカウントしながら倍し続ける。
- 満たさなくなるまで倍する都合上、回余計に倍するので、カウンターの初期値をとしておく。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); sc.close(); int k = -1; long a = 1; while (a <= n) { a *= 2; k++; } System.out.println(k); } }
ここまで2分06秒+0ペナ。213位。
C - One More aab aba baa
思考過程
- で問題ない制約。
- をソートして、順列全列挙して、番目が答え? →例2が合わない
- 重複排除が必要だったので、順列全列挙した結果をTreeSetに入れ、番目を答える。
- TreeSetを使うことで事前のソートは必要なくなったので、一応余計な処理は消しておく。
import java.util.LinkedHashSet; import java.util.Scanner; import java.util.TreeSet; public class Main { static TreeSet<String> ans = new TreeSet<>(); public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); char[] s = sc.next().toCharArray(); int k = sc.nextInt(); sc.close(); permutation(s, new LinkedHashSet<>()); for (int i = 1; i < k; i++) { ans.pollFirst(); } System.out.println(ans.pollFirst()); } static void permutation(char[] target, LinkedHashSet<Integer> set) { if (set.size() == target.length) { StringBuilder sb = new StringBuilder(); for (int i : set) { sb.append(target[i]); } ans.add(sb.toString()); return; } for (int i = 0; i < target.length; i++) { if (!set.contains(i)) { set.add(i); permutation(target, set); set.remove(i); } } } }
ここまで7分04秒+0ペナ。705位。
D - Coprime 2
思考過程
- の各要素の素因数をどれも含まない数値を答えればよい。
- まずは、の全要素を素因数分解して、含まれてはいけない素因数のSetを作る。
- は必ず条件を満たすので、~を全部素因数分解して、出てきた素因数が上記2.のSetに含まれないかどうかを調べる。
- 計算量はよくわからないけど、とりあえずエラトステネスの篩は使っておいて、あとは愚直に上記2~3.の通りやるとすれば、(とはよくわからないけど適当にlogの乗くらいまでの想定)で多分大丈夫?で投げてみて大丈夫だった。
import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } sc.close(); Eratosthenes era = new Eratosthenes(100000); // 2 Set<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { Map<Integer, Integer> soinsu = era.bunkai(a[i]); set.addAll(soinsu.keySet()); } // 3 List<Integer> list = new ArrayList<>(); list.add(1); for (int i = 2; i <= m; i++) { Map<Integer, Integer> soinsu = era.bunkai(i); boolean flg = true; for (Integer k : soinsu.keySet()) { if (set.contains(k)) { flg = false; break; } } if (flg) { list.add(i); } } PrintWriter pw = new PrintWriter(System.out); pw.println(list.size()); for (int i : list) { pw.println(i); } pw.flush(); } // 以下ライブラリ static class Eratosthenes { int[] div; public Eratosthenes(int n) { if (n < 2) return; div = new int[n + 1]; div[0] = -1; div[1] = -1; int end = (int) Math.sqrt(n) + 1; for (int i = 2; i <= end; i++) { if (div[i] == 0) { div[i] = i; for (int j = i * i; j <= n; j+=i) { if (div[j] == 0) div[j] = i; } } } for (int i = end + 1; i <= n; i++) { if (div[i] == 0) div[i] = i; } } public Map<Integer, Integer> bunkai(int x) { Map<Integer, Integer> soinsu = new HashMap<>(); while (x > 1) { Integer d = div[x]; soinsu.put(d, soinsu.getOrDefault(d, 0) + 1); x /= d; } return soinsu; } public boolean isSosuu(int x) { return div[x] == x; } } }
ここまで12分14秒+0ペナ。211位。
E - Chain Contestant
問題
大まかな方針は割とすぐに出てきていたのに、なかなかスムーズに実装できず。
思考過程
- 「番目まで見て、それまでに出場した種類の集合がで、最後に出場した種類がの通り数」をすると、なので、遷移が軽ければ大丈夫そう。
- 番目に出場する場合に相当する遷移では、が増える方向にしか遷移しないので、降順に処理すればを持たなくてもできそう。またその場合、出場する場合の遷移だけ実装すればよくなる。
- の場合、を倍にする。(番目までで最後にを選んでいるパターンに、番目でを選ぶパターンを追加する)
- が上記以外の場合、全てのから、へと遷移する。(でない場合のはなので、特に場合分けせず足して問題なし)
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); char[] s = sc.next().toCharArray(); sc.close(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = s[i] - 'A'; } int mod = 998244353; int m = 1024; int m2 = 10; int[][] dp = new int[m][m2]; dp[0][0] = 1; for (int i = 0; i < n; i++) { for (int j = m - 1; j >= 0; j--) { if ((j >> a[i] & 1) == 1) { dp[j][a[i]] *= 2; dp[j][a[i]] %= mod; } else { for (int k = m2 - 1; k >= 0; k--) { // ↓ここを j | a[i] にしていてしばらくハマる int next = j | (1 << a[i]); dp[next][a[i]] += dp[j][k]; dp[next][a[i]] %= mod; } } } } long ans = 0; for (int i = 1; i < m; i++) { for (int j = 0; j < m2; j++) { ans += dp[i][j]; } } ans %= mod; System.out.println(ans); } }
ここまで34分25秒+0ペナ。296位。
F - Dist Max 2
思考過程
- 小さい方の最大値ということで、答えの二分探索を考えてみる。
- あらかじめ点を座標でソートしておくと、決め打ちした答えを満たすかどうかは、ある点に対して、座標が以上の範囲に、座標が以上または以下である点が存在するかどうかを調べることになる。
- これは、座標の最大値と最小値を管理するセグ木つを用意しておけばよい。
左側の点を起点に右側の相方を探そうとしたら、思考停止でセグ木を貼ることになったが、公式解説を見たら、右側を起点に左側の相方を探せば、セグ木なんて使わなくても、ABC-Bレベルの最も単純な最大値や最小値を求める方法でよいことがわかった。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.function.BinaryOperator; import java.util.function.Predicate; public class Main { static int n; static Obj[] arr; static SegTree<Integer> st1, st2; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); arr = new Obj[n]; for (int i = 0; i < n; i++) { String[] sa = br.readLine().split(" "); Obj o = new Obj(); o.x = Integer.parseInt(sa[0]); o.y = Integer.parseInt(sa[1]); arr[i] = o; } br.close(); // x座標の昇順 Arrays.sort(arr, (o1, o2) -> o1.x - o2.x); // 最大値用セグ木 st1 = new SegTree<>(n, 0, (v1, v2) -> Math.max(v1, v2)); // 最小値用セグ木 st2 = new SegTree<>(n, 1000000007, (v1, v2) -> Math.min(v1, v2)); for (int i = 0; i < n; i++) { Obj o = arr[i]; st1.set(i, o.y); st2.set(i, o.y); } int ok = 0; int ng = 1000000001; while (Math.abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (judge(mid)) { ok = mid; } else { ng = mid; } } System.out.println(ok); } // 答えをmidに決め打ちした時の判定問題 static boolean judge(int mid) { for (int i = 0; i < n; i++) { Obj o = arr[i]; int idx = binarySearch(arr, o.x + mid); int max = st1.prod(idx, n); if (max - o.y >= mid) { return true; } int min = st2.prod(idx, n); if (o.y - min >= mid) { return true; } } return false; } // array[i].x >= xである最小のi static int binarySearch(Obj[] array, int x) { int ok = array.length; int ng = -1; while (Math.abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (array[mid].x >= x) { ok = mid; } else { ng = mid; } } return ok; } static class Obj { int x, y; } } // 以下ACLを移植したSegTree
提出
ここまで61分02秒+0ペナ。212位。
GとHは何もわからず。
最終結果:ABCDEFの6完2000点、61分02秒、272位、パフォーマンス2127相当
レート変動:2101(Unrated)
ABC192(初めて青→黄になった回)以来の6完。
ABC212からF問題の難易度が徐々に下がってきており、傾斜は良くなってきていると思う。
自分が平均6.3完できるくらいの難易度で安定してくれると良さそうな気はするのだが。
AtCoderの変革の恩恵を最大限に受けるには、自分の成長ペースが追い付いていないなと感じる今日この頃。
自分が水色になると同時にABCが4問から6問になったのは非常にうれしかったが、
ARCが復活するより自分が黄色になる方が半年くらい遅く、
ABCが8問になって高度典型の教材が増えても、それを学べるレベルにまだ達していない状態。