エイシングプログラミングコンテスト(AtCoder Beginner Contest 202)(Rated範囲外)

コンテスト前のレート:2013
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:300位(1500点、54分30秒)

A - Three Dice

問題

思考過程
  1. 裏面はそれぞれ(7-a), (7-b), (7-c)なので、合計は21-a-b-c
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();
        int c = sc.nextInt();
        sc.close();

        System.out.println(21 - a - b - c);
    }
}

ここまで0分32秒+0ペナ。88位。


B - 180°

問題

思考過程
  1. 問題文の通り実装する。
  2. 実際に変換する必要があるのは、'6'と'9'のみ。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();

        reverse(s);
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '6') {
                s[i] = '9';
            } else if (s[i] == '9') {
                s[i] = '6';
            }
        }
        System.out.println(s);
    }

    // 以下ライブラリ

    static void reverse(char[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            char tmp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = tmp;
        }
    }
}

ここまで2分22秒+0ペナ。242位。


C - Made Up

問題

思考過程
  1. A_i=1の数、A_i=2の数、\cdotsA_i=Nの数を数え、B_{C_j}についても同様に1Nの出現数を数える。
  2. \sum_{k=1}^{N}(A_i=kの数)\times(B_{C_j}=kの数)を求める。
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();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt() - 1;
        }
        sc.close();

        int[] ac = new int[n + 1];
        int[] bc = new int[n + 1];
        for (int i = 0; i < n; i++) {
            ac[a[i]]++;
            bc[b[c[i]]]++;
        }

        long ans = 0;
        for (int i = 0; i < bc.length; i++) {
            ans += (long) ac[i] * bc[i];
        }
        System.out.println(ans);
    }
}

ここまで4分40秒+0ペナ。112位。


D - aab aba baa

問題
最初しばらくわからず、また3完で終わってしまうかと思った。

思考過程
  1. DPかDFSかできそうな方法を考える。
  2. 前からi文字目までが決まっていて残りの'a'がra個、'b'がrb個とすると、作れる文字列は_{ra+rb}C_{ra}通り。
  3. 先頭から順に、次の文字を'a'とした場合の通り数がK以上である場合は'a'、K未満である場合は'b'と決め打ちしていける。 ただし後者の場合は、'a'とした場合の通り数をこれまでの合計に足す必要がある。
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();
        long k = sc.nextLong();
        sc.close();

        int n = a + b;
        int ra = a; // aの残り
        int rb = b; // bの残り
        long base = 0; // これまでの合計
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (ra == 0) {
                sb.append('b');
                rb--;
                continue;
            }
            if (rb == 0) {
                sb.append('a');
                ra--;
                continue;
            }

            long va = nCr(n - i - 1, ra - 1); // 次をaとした場合の通り数
            if (base + va < k) {
                base += va;
                sb.append('b');
                rb--;
            } else {
                sb.append('a');
                ra--;
            }
        }
        System.out.println(sb.toString());
    }

    // 以下ライブラリ

    static long nCr(int n, int r) {
        long val = 1;
        for (int i = 1; i <= r; i++) {
            val = val * (n - i + 1) / i;
        }
        return val;
    }
}

ここまで17分31秒+0ペナ。211位。


E - Count Descendants

問題
どうやってもO(NQ)とかになりそうで、Unratedだからと諦めかけたが、なんとか解けた。

思考過程
  1. 深さごとの頂点のリストを用意したりしても、毎回深さがD_iの頂点を全て調べたのではO(NQ)はかかってしまう。
  2. 問題文は逆に言えば、U_iの配下の内、深さがD_iである頂点の数を求めろと言っている。
  3. 各頂点に深さごとの配下の頂点リストを事前に用意しておくことを考えるが、それだとクエリにはO(1)で答えられるが、用意する部分が時間、空間共にO(N^2)になってしまう。
     
  4. クエリを前から順に処理していくのではなく、DFSをしながら同じU_iに対するクエリを処理していくことを考える。
  5. 配下の頂点全部の個数を得るだけだったら最も基本的な木DPだが、それを深さごとに分けて個数を取得するにはどうしたらいいか。
     
  6. 深さごとの個数をカウントしていくための配列を用意する。
  7. 頂点Xに入ってきた時の状態を退避しておき、配下を調べて親に戻っていく際に、カウントの差分を元にクエリに答えられる。
  8. なお、入ってきた状態を退避しておくのにカウント配列全体をコピーしたのでは、各頂点ごとにコピー処理だけでO(N)かかり、全体でO(N^2)となるため、クエリで使う深さの情報だけを退避する。
  9. これで退避がならしO(Q)となり、全体でO(N+Q)にできる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<List<Integer>> child, qr;
    static int[] u, d, ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        child = new ArrayList<>(n);
        qr = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            child.add(new ArrayList<>());
            qr.add(new ArrayList<>());
        }

        String[] sa = br.readLine().split(" ");
        for (int i = 1; i < n; i++) {
            int p = Integer.parseInt(sa[i - 1]) - 1;
            child.get(p).add(i);
        }

        int q = Integer.parseInt(br.readLine());
        u = new int[q];
        d = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            u[i] = Integer.parseInt(sa[0]) - 1;
            d[i] = Integer.parseInt(sa[1]);
            qr.get(u[i]).add(i); // クエリを頂点ごとに分ける
        }
        br.close();

        ans = new int[q];
        dfs(0, 0, new int[n]); // 深さは最大n-1

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }

    static void dfs(int x, int dep, int[] cnt) {
        List<Integer> qx = qr.get(x);
        // 入ってきた時点の状態を退避
        List<Integer> pre = new ArrayList<>(qx.size());
        for (int i : qx) {
            pre.add(cnt[d[i]]);
        }

        for (int i : child.get(x)) {
            dfs(i, dep + 1, cnt);
        }
        cnt[dep]++;

        // クエリの処理
        for (int i = 0; i < qx.size(); i++) {
            int j = qx.get(i);
            ans[j] = cnt[d[j]] - pre.get(i);
        }
    }
}

ここまで62分39秒+0ペナ。372位。



F問題は正解者数からしてもどうせ無理だろうと思い、あまりやる気はなかったが、一応少しは考えてみてやっぱり全くわからず。
残り10分くらいでもう諦めてこれを書き始めていた。



終結果:ABCDEの5完、62分39秒、378位、パフォーマンス1916相当
レート変動:2013(Unrated)


黄パフォとはいかなかったが久しぶりにABCでまともな結果だったと思う。
ABCがUnratedになって10回ほどになったが、大半が800位以下、下手すると2000位近くとかで、レート通り300位前後だったのが3回しかない状態。

ほんと、ARCが毎週のようにある中でいつまでしぶとく黄色でいられるのやら。