AtCoder Beginner Contest 211(Rated範囲外)

ABC

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

A - Blood Pressure

問題

思考過程
  1. 問題文の通り計算する。
  2. 誤差とか書かれているのが見えたので、double型で計算する。
import java.util.Scanner;

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

        System.out.println((a - b) / 3 + b);
    }
}

ここまで0分49秒＋0ペナ。222位。


B - Cycle Hit

問題

思考過程
  1. 入力をSetに入れて、要素数が4であるかどうかを調べる。
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);
        Set<String> set = new HashSet<>();
        set.add(sc.next());
        set.add(sc.next());
        set.add(sc.next());
        set.add(sc.next());
        sc.close();

        if (set.size() == 4) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分37秒＋0ペナ。30位。


C - chokudai

問題
典型90-008と全く同じ問題。
典型90問は、コンテストが終わってからStreak繋ぎに使い始めていたこともあり、ほんの4日前にこれをやったばかりであった。

思考過程
  1. "c"の出現数、"ch"の出現数、"cho"の出現数、\cdotsを保持しておく変数を用意しておき、Sを前から調べていって例えば'o'が出てきたところで、cho += ch; のような計算をすればよい。というよくある数え上げ。
  2. ただ、これを8個も並べるのは面倒なので、今回はfor文を使ってみる。
  3. 判定用の文字配列をわざわざ面倒な作り方してしまった。
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();

        int n = s.length;
        char[] a = {'c', 'h', 'o', 'k', 'u', 'd', 'a', 'i'}; // 3
        int mod = 1000000007;
        long[] dp = new long[8];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 8; j++) {
                if (s[i] == a[j]) {
                    if (j == 0) {
                        dp[j]++;
                    } else {
                        dp[j] += dp[j - 1];
                        dp[j] %= mod;
                    }
                }
            }
        }
        System.out.println(dp[7]);
    }
}

ここまで4分55秒＋0ペナ。76位。


D - Number of Shortest paths

問題
これも2日前にPAST7-Kという類題を見たばかり。
Mの入力を受け取る部分をsa[0]にしていて2分くらい溶かした。

思考過程
  1. まず、最短経路を求めるので、BFSをする。
  2. ある頂点に最短経路として遷移する際、遷移先の経路数に、遷移元までの経路数を加算する。
  3. 「最短経路として遷移する」の判定は、遷移先が未訪問であるか、「遷移先の距離=遷移元の距離+1」であるか。
  4. 未訪問の場合の値設定を先にやってしまえば、後者の判定のみでできる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

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]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            list.get(a).add(b);
            list.get(b).add(a);
        }
        br.close();

        int mod = 1000000007;
        int[] d = new int[n]; // 距離保持、訪問判定用
        long[] dp = new long[n]; // 経路数
        Queue<Integer> que = new ArrayDeque<>();
        que.add(0);
        d[0] = 1;
        dp[0] = 1;
        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int i : list.get(cur)) {
                if (d[i] == 0) {
                    que.add(i);
                    d[i] = d[cur] + 1;
                }
                if (d[i] == d[cur] + 1) {
                    dp[i] += dp[cur];
                    dp[i] %= mod;
                }
            }
        }
        System.out.println(dp[n - 1]);
    }
}

ここまで12分24秒＋0ペナ。141位。



E問題は解けず。
いくつか実装方法変えてみて、いずれも例３でTLE（手元実行時点で10秒以上終わらず）。
素直にメモ化すればよかったっぽい。

F問題はまともに考える気が起こらず、残り時間はほとんどE問題に使っていた。



最終結果：ABCDの4完1000点、12分24秒、602位、パフォーマンス1730相当
レート変動：2114（Unrated）


結局Unratedになって以来の6問制ABCは、レート以上のパフォを勝ちとして、2勝17敗というひどいボロ負けっぷりで終わった。
その前の5連勝で黄色に逃げ込めていなければ、今頃一体どうなっていたのか・・・。

次回以降8問制になったときにもうちょっと安定して黄パフォ出せるようになりたい。