AtCoder Beginner Contest 194(Rated範囲外)

ABC

コンテスト前のレート：2029
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：318位（1500点、31分51秒）


今回もまた一瞬適当にD問題辺りからやろうとするが、結局素直にA問題から。

A - I Scream

問題
すごい誤読しやすそうな見た目をしていて、Unratedなら気楽でよかったと思った。

思考過程
  1. 例１の説明を見て、とりあえずA+Bを計算しておく。
  2. あとは問題文の通り上の条件から順に判定していく。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        int c = a + b;
        if (c >= 15 && b >= 8) {
            System.out.println(1);
        } else if (c >= 10 && b >= 3) {
            System.out.println(2);
        } else if (c >= 3) {
            System.out.println(3);
        } else {
            System.out.println(4);
        }
    }
}

ここまで2分44秒＋0ペナ。510位。


B - Job Assignment

問題
O(N^2)でよいことに全く気付いておらず、手間取りすぎ。

思考過程
  1. AとBについて上位2人まで見ることがあり、2位を管理するのは面倒なので、PriorityQueueを用意しておく。
  2. A_iとB_iが同じ人かわからないと困るので、情報はペア（オブジェクト）で持っておく。
    　
  3. A_1とB_1（以降、添え字は何番目に小さいかを表すものとする）が別人の場合は、A_1とB_1の大きい方が答え。
  4. A_1とB_1が同じ人の場合は、以下の内最小のものが答え。
    • A_1とB_2の大きい方
    • A_2とB_1の大きい方
    • A_1+B_1
import java.util.PriorityQueue;
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();
        PriorityQueue<Obj> q1 = new PriorityQueue<>((o1, o2) -> o1.a - o2.a);
        PriorityQueue<Obj> q2 = new PriorityQueue<>((o1, o2) -> o1.b - o2.b);
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.a = sc.nextInt();
            o.b = sc.nextInt();
            q1.add(o);
            q2.add(o);
        }
        sc.close();

        Obj o1 = q1.poll();
        Obj o2 = q2.poll();
        int ans = Math.max(o1.a, o2.b);
        if (o1 == o2) {
            Obj o12 = q1.poll();
            Obj o22 = q2.poll();
            ans = Math.min(Math.max(o1.a, o22.b), Math.max(o12.a, o2.b));
            ans = Math.min(ans, o1.a + o2.b);
        }
        System.out.println(ans);
    }

    static class Obj {
        int a, b;
    }
}

ここまで12分19秒＋0ペナ。1775位。


C - Squared Error

問題
苦手意識のある、_NC_2通り全探索したいけどO(N^2)では間に合わない系統の問題。

思考過程
  1. ソートをしておけば、各iに対するjをまとめて1回で計算するようなことができるのではないかと思ってとりあえずソートしてみる（が意味なかった）。
    　
  2. 問題文の式について、\sumの中身を展開してみると、{A_i}^2 - 2A_iA_j + {A_j}^2となる。
  3. {A_i}^2と{A_j}^2の部分については、二次元表を書いて数えてみると、{A_1}^2～{A_N}^2が全体でN-1回ずつ足されることがわかる。
  4. -2A_iA_jの部分は、A_jの和を保持しながら計算することで、O(N)にできる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        Arrays.sort(a); // 1
        // 3
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += a[i] * a[i];
        }
        ans *= n - 1;

        // 4
        long sum = 0;
        for (int i = n - 2; i >= 0; i--) {
            sum += a[i + 1];
            ans -= 2 * a[i] * sum;
        }
        System.out.println(ans);
    }
}

ここまで22分43秒＋0ペナ。1369位。


D - Journey

問題
確率という単語が目に入っただけで後回しにせず、そのまま最初に解けば、最大瞬間風速4位にはなれていそうだった。

思考過程
  1. 未訪問の頂点が選ばれるまでの回数の期待値を求める。ということをN-1回行う。
  2. 未訪問頂点が選ばれる確率は、「未訪問頂点の数 / N」であり、期待値は確率の逆数。
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();
        sc.close();

        double ans = 0;
        for (int i = n - 1; i > 0; i--) {
            ans += (double) n / i;
        }
        System.out.println(ans);
    }
}

ここまで25分16秒＋0ペナ。529位。


E - Mex Min

問題
ここ2ヶ月青diff以下を1問も落としていなかったのに、まさかの緑diffを落とす。
残り時間全部E問題に使ったわけではなく、F問題で逆転を狙うために30分くらいは残して諦めたのもあるけど。

余計なことをしてバグらせていたのと、WAやREを出していたコーナーケースが何なのか見つけ出せなかった。（答えがNになる場合だった。）

思考過程
  1. 出現数を持っておく配列と「現在の出現数0の最小値：val」を用意し、これを管理しながら進めることでO(N)またはO(NlogN)で解こうとする。
    　
  2. 最初は0から順に調べていき、最初の出現数0の値をvalとする。
  3. 配列を更新していく間に、出現数0のものが新たに出てきたり消えたりした時にするため、新しいvalを高速に求めるためには、前後の出現数0の位置も管理しておく必要があるのではと思った。
  4. 前後の出現数0の位置を管理するために、出現数0の値の集合を持つTreeSetも用意する。
    　
  5. コンテスト内最後の提出がこれだが、どうやら40行目でvalがnになっていて配列外参照していたらしい。（コンテスト中は、RE発生箇所は43行目よりは後だろうと疑っていなかった。）
    　
  6. コンテスト後になって、新しいvalはSet内の最小値を取ればいいだけであることがわかり、別に必要なかった前後の出現数0の管理部分を丸ごと削除する。
  7. それでもまだREが取れず、テストケース名を見てやっと答えがNになる場合が怪しいことがわかり、その対処をする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        // 1
        int[] cnt = new int[n];
        for (int i = 0; i < m; i++) {
            cnt[a[i]]++;
        }

        // 4
        TreeSet<Integer> set = new TreeSet<>();
        set.add(n); // 7
        for (int i = 0; i < n; i++) {
            if (cnt[i] == 0) {
                set.add(i);
            }
        }
        int ans = set.first();

        for (int i = m; i < n; i++) {
            int x = a[i];
            if (cnt[x] == 0) {
                set.remove(x);
            }
            cnt[x]++;

            int y = a[i - m];
            if (cnt[y] == 1) {
                set.add(y);
                ans = Math.min(ans, y);
            }
            cnt[y]--;
        }
        System.out.println(ans);
    }
}

　

F - Digits Paradise in Hexadecimal

問題
ある程度惜しいところまではできていたと思うが、時間内には解き切れず。
詳細は省略するが、先頭0周りの処理が色々おかしかった。
下記6.でfor文2つに分けたことにより'9'が漏れたりとかも。

結局EとF両方手を出して両方ともあと少し（と言えるかは若干怪しいが）できなかったという感じ。

思考過程
  1. 「dp[i][j]:=i文字目まで見てj種類の場合の通り数」で桁DPすることを基本方針として考える。
  2. j種類のところを、これまでに使った文字の集合にしないと遷移できないのでは？と思うが、それだと遷移を抜きにしてもO(|N|2^K)かかるので無理。
    　
  3. 遷移の仕方を詰めていくと、桁DPのNより小さいことが確定済みの方は、次の値として'0'～'F'の16種類全部取れるので、その内種類数が増えない遷移がj通り、種類数が1増える遷移が16-j通りとなる。
  4. ただし、種類数が0→1になる遷移は、最初の1文字目の時は確定済みになっていないのでなし。2文字目以降では'1'～'F'の15通り。
    　
  5. 桁DPのNより小さいことが未確定の方は常に1通りで、これまでに登場した文字のSetだけ持っておけば、Setのsizeを元に確定済みの方へと遷移できそう。
    　
  6. （以降、Nのi文字目をS_iとする。）未確定から確定済みへの遷移は、0 \leq c \lt S_iの各cについて、Setに含まれていればj=sizeへ、含まれていなければj=size+1への遷移を1通りずつ加算する。
  7. ただし、最初の1文字目だけは、文字種0の状態から'0'は選べないので、'0'の分は加えない。
    　
  8. 最後に、未確定状態を表すSetのsizeがちょうどkならば1通りを加算する。
import java.util.HashSet;
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);
        char[] s = sc.next().toCharArray();
        int k = sc.nextInt();
        sc.close();

        int n = s.length;
        int mod = 1000000007;
        Set<Character> set = new HashSet<>();
        long[][] dp = new long[n + 1][17];
        for (int i = 0; i < n; i++) {
            // 6
            char end = (char) Math.min('9' + 1, s[i]);
            for (char c = '0'; c < end; c++) {
                // 7
                if (c == '0' && i == 0) {
                    continue;
                }
                if (set.contains(c)) {
                    dp[i + 1][set.size()]++;
                } else {
                    dp[i + 1][set.size() + 1]++;
                }
            }
            end = (char) Math.min('F', s[i]);
            for (char c = 'A'; c < end; c++) {
                if (set.contains(c)) {
                    dp[i + 1][set.size()]++;
                } else {
                    dp[i + 1][set.size() + 1]++;
                }
            }
            set.add(s[i]);

            // 4
            if (i > 0) {
                dp[i + 1][1] += 15;
            }
            for (int j = 1; j <= k; j++) {
                // 3
                dp[i + 1][j] += dp[i][j] * j;
                dp[i + 1][j] += dp[i][j - 1] * (16 - (j - 1));
                dp[i + 1][j] %= mod;
            }
        }
        long ans = dp[n][k];
        // 8
        if (set.size() == k) {
            ans++;
            ans %= mod;
        }
        System.out.println(ans);
    }
}

　


最終結果：ABCDの4完、25分16秒、1987位、パフォーマンス1102相当
レート変動：2029（Unrated）


こんな結果になるくらいなら、明日のAGC052で青落ちしておくべきだと思う。
1692以下くらいで落ちる見込み。（1704以下かも。端数処理がどうなっているのかわかってない。）