UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)(Rated範囲外)

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

A - Distinct Strings

問題

思考過程

1. 文字であれば、サンプルの通り、文字が種類なら通り、種類なら通り、種類なら通りとなり、反例もないので文字の種類数だけ調べればよい。
2. 文字の種類数を知りたいときに真っ先に思い付く方法は、Setに入れてサイズを取得すること。

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();
        sc.close();

        Set<Character> set = new HashSet<>();
        set.add(s[0]);
        set.add(s[1]);
        set.add(s[2]);
        int a = set.size();
        if (a == 1) System.out.println(1);
        if (a == 2) System.out.println(3);
        if (a == 3) System.out.println(6);
    }
}

ここまで1分52秒＋0ペナ。837位。

B - Star or Not

問題

思考過程

1. 次数がの頂点があるかどうかを調べる。
2. 入力が木であることが保証されているので、を特に区別することもなくまとめて各値の出現回数をカウントし、であるものが存在すれば"Yes"。

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[] c = new int[n];
        for (int i = 0; i < n - 1; i++) {
            c[sc.nextInt() - 1]++;
            c[sc.nextInt() - 1]++;
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            if (c[i] == n - 1) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}

ここまで3分36秒＋0ペナ。373位。

C - Calendar Validator

問題

思考過程

1. 各について、右は、下はの関係になっていない箇所があれば"No"。　→行またぎを検知できておらずWA
2. の列目以降にの列目に当たる数（で割って余る数）がある場合も"No"とする。これは上記1.が通っている前提ならば、行目だけ調べれば十分。

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 m = sc.nextInt();
        int[][] b = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                b[i][j] = sc.nextInt();
            }
        }
        sc.close();

        // 1
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (b[i - 1][j] + 7 != b[i][j]) {
                    System.out.println("No");
                    return;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (b[i][j - 1] + 1 != b[i][j]) {
                    System.out.println("No");
                    return;
                }
            }
        }
        // 2
        for (int i = 1; i < m; i++) {
            if (b[0][i] % 7 == 1) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで8分53秒＋1ペナ。179位。

D - Play Train

問題

思考過程

1. LinkedListのような構造を思い浮べ、各電車について前に連結されている電車と後ろに連結されている電車の情報を管理することを考える。
2. そのような情報があれば、とりあえずクエリは前後に辿っていくことで答えられそう。
   　
3. 実装を始めながらクエリの処理について考えてみると、クエリはを適切に設定するだけ、クエリは存在しないことを表す初期値に戻すだけであった。
4. クエリは先頭から順番に出力しないといけないので、前に辿りながらDequeの前方に追加していき、後ろに辿りながらDequeの後方に追加していくことで、そのような順番を実現する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

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 q = Integer.parseInt(sa[1]);

        int[] l = new int[n];
        int[] r = new int[n];
        Arrays.fill(l, -1);
        Arrays.fill(r, -1);

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            int x = Integer.parseInt(sa[1]) - 1;
            if (t == 1) {
                int y = Integer.parseInt(sa[2]) - 1;
                r[x] = y;
                l[y] = x;

            } else if (t == 2) {
                int y = Integer.parseInt(sa[2]) - 1;
                r[x] = -1;
                l[y] = -1;

            } else {
                Deque<Integer> que = new ArrayDeque<>();
                que.add(x);
                // 前へ
                int now = x;
                while (true) {
                    now = l[now];
                    if (now == -1) {
                        break;
                    } else {
                        que.addFirst(now);
                    }
                }
                // 後ろへ
                now = x;
                while (true) {
                    now = r[now];
                    if (now == -1) {
                        break;
                    } else {
                        que.addLast(now);
                    }
                }

                StringBuilder sb = new StringBuilder();
                sb.append(que.size());
                while (!que.isEmpty()) {
                    sb.append(' ').append(que.pollFirst() + 1);
                }
                pw.println(sb.toString());
            }
        }
        pw.flush();
        br.close();
    }
}

ここまで16分16秒＋1ペナ。154位。

E - フ

問題
区間スケジューリング問題の解き方がうろ覚えで、貪欲でよいところをDPした。

思考過程

1. 各フの字は、傾き～の区間を占有しているとみなすことができるので、そのような区間個の区間スケジューリング問題を解けばよい。
2. 問題は区間をdouble型で扱ってよいかだが、とりあえずWA覚悟でやってみて案の定WA。
3. という判定をしたいところを、に直す。

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());
        Obj[] 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();

        Arrays.sort(arr, (o1, o2) -> Long.compare(o1.y * (o2.x - 1), o2.y * (o1.x - 1)));
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            Obj o = arr[i];
            int idx = binarySearch(arr, o) + 1;
            dp[i + 1] = Math.max(dp[i], dp[idx] + 1);
        }
        System.out.println(dp[n]);
    }

    static int binarySearch(Obj[] array, Obj o) {
        int ok = -1;
        int ng = array.length;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            Obj o2 = array[mid];
            if (o2.y * o.x <= (o.y - 1) * (o2.x - 1)) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }

    static class Obj {
        long x, y;
    }
}

区間スケジューリング部分を貪欲に直した提出
ここまで39分32秒＋2ペナ。126位。

残り時間はほとんどF問題に使ったが解けず。
公式解説の嘘解法例1をベースに、の中で最長のものと同じ文字数を超えるまでは何個かつなげる全探索をする必要があるのではないかなどと考えていた。

最終結果：ABCDEの5完1500点、49分32秒、222位、パフォーマンス2184相当
レート変動：2038（Unrated）

ABCは直近3回連続200位台で、まあ解けるべき問題は解けているかなという感じ。
F～G問題辺りで解けなかったものの学習は進んでいない。