AtCoder Beginner Contest 215(Rated範囲外)

コンテスト前のレート:2101
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:292位(2000点、65分59秒)

A - Your First Judge

問題

思考過程
  1. 完全に一致するかどうかは、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)

問題

思考過程
  1. 条件を満たさなくなるまで、回数をカウントしながら2倍し続ける。
  2. 満たさなくなるまで2倍する都合上、1回余計に2倍するので、カウンターの初期値を-1としておく。
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

問題

思考過程
  1. O(|S|!)で問題ない制約。
  2. Sをソートして、順列全列挙して、K番目が答え? →例2が合わない
  3. 重複排除が必要だったので、順列全列挙した結果をTreeSetに入れ、K番目を答える。
  4. 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

問題

思考過程
  1. Aの各要素の素因数をどれも含まない数値を答えればよい。
  2. まずは、Aの全要素を素因数分解して、含まれてはいけない素因数のSetを作る。
  3. 1は必ず条件を満たすので、2Mを全部素因数分解して、出てきた素因数が上記2.のSetに含まれないかどうかを調べる。
     
  4. 計算量はよくわからないけど、とりあえずエラトステネスの篩は使っておいて、あとは愚直に上記2~3.の通りやるとすれば、O(Nx+My)xyはよくわからないけど適当にlogの2乗くらいまでの想定)で多分大丈夫?で投げてみて大丈夫だった。
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

問題
大まかな方針は割とすぐに出てきていたのに、なかなかスムーズに実装できず。

思考過程
  1. dp[i][j][k]:=i番目まで見て、それまでに出場した種類の集合がjで、最後に出場した種類がkの通り数」をすると、1000 \times 1024 \times 10なので、遷移が軽ければ大丈夫そう。
  2. i番目に出場する場合に相当する遷移では、jが増える方向にしか遷移しないので、降順に処理すればiを持たなくてもできそう。またその場合、出場する場合の遷移だけ実装すればよくなる。
     
  3. S_i \in jの場合、dp[j][S_i]2倍にする。(i-1番目までで最後にS_iを選んでいるパターンに、i番目でS_iを選ぶパターンを追加する)
  4. jが上記以外の場合、全てのkから、dp[j | S_i][S_i]へと遷移する。(k \in jでない場合のdp[j][k]0なので、特に場合分けせず足して問題なし)
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

問題

思考過程
  1. 小さい方の最大値ということで、答えの二分探索を考えてみる。
  2. あらかじめ点をx座標でソートしておくと、決め打ちした答えを満たすかどうかは、ある点iに対して、x座標がx_i + ans以上の範囲に、y座標がy_i + ans以上またはy_i - ans以下である点が存在するかどうかを調べることになる。
  3. これは、y座標の最大値と最小値を管理するセグ木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問になって高度典型の教材が増えても、それを学べるレベルにまだ達していない状態。