AtCoder Beginner Contest 212(Rated範囲外)

コンテスト前のレート：2101
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：256位（2000点、82分43秒）

A - Alloy

問題
サンプル試すのを手抜いたら、GoldとSilverを逆に出力していて1ペナ。

思考過程

1. の制約から、一方がであることを判定すれば、もう一方がより大きい判定は不要。
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();

        if (a == 0) {
            System.out.println("Silver");
        } else if (b == 0) {
            System.out.println("Gold");
        } else {
            System.out.println("Alloy");
        }
    }
}

ここまで1分46秒＋1ペナ。1075位。

B - Weak Password

問題
連番の判定に手間取ってしまった。

思考過程

1. 同じ数字と連番の判定を同時にやろうとすると、例２のようなものでミスりそう。
2. 同じ数字の判定は、桁数も少ないので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();

        if (s[0] == s[1] && s[1] == s[2] && s[2] == s[3]) {
            System.out.println("Weak");
            return;
        }

        boolean w = true;
        for (int i = 1; i < s.length; i++) {
            int a = s[i - 1] - '0';
            int b = s[i] - '0';
            if (a + 1 == b || (a == 9 && b == 0)) {
            } else {
                w = false;
            }
        }
        if (w) {
            System.out.println("Weak");
        } else {
            System.out.println("Strong");
        }
    }
}

ここまで5分30秒＋1ペナ。637位。

C - Min Difference

問題

思考過程

1. 各について、の中から「以下の最大値」と「以上の最小値」を取得して差の最小値を調べたい。
2. 上記の値は、BをTreeSetに入れておけば、floorとceilingメソッドを使って簡単に取得できる。

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]);
        }

        sa = br.readLine().split(" ");
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < m; i++) {
            set.add(Integer.parseInt(sa[i]));
        }
        br.close();

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            Integer e = set.floor(a[i]);
            if (e != null) {
                ans = Math.min(ans, Math.abs(a[i] - e));
            }
            e = set.ceiling(a[i]);
            if (e != null) {
                ans = Math.min(ans, Math.abs(a[i] - e));
            }
        }
        System.out.println(ans);
    }
}

ここまで8分45秒＋1ペナ。372位。

D - Querying Multiset

問題

思考過程

1. 操作を愚直に行うのは当然TLE。
2. 各ボールの初期値と、操作の合計値を持っておくくらいでクエリに答えられる方法を考える。
3. 操作の内容から、袋にはPriorityQueueを使いたい。
4. 操作の時に、を引いておけば、操作で最小のものを正しく取り出せる。
5. 操作の際にはを足し直す必要があった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        PriorityQueue<Long> que = new PriorityQueue<>();
        long b = 0;

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            if (sa[0].equals("1")) {
                que.add(Long.parseLong(sa[1]) - b);
            } else if (sa[0].equals("2")) {
                b += Long.parseLong(sa[1]);
            } else {
                pw.println(que.poll() + b);
            }
        }
        pw.flush();
    }
}

ここまで18分23秒＋1ペナ。534位。

E - Safety Journey

問題
は制約が厳しいのでは・・・。
なんとか一発で1978msで通り、無駄にTLEで苦しまなくて済んだ。

思考過程

1. 乗が通りそうな制約なので、とりあえず「日目に都市にいる通り数」を考える。
2. 実装し始めてから、通りの遷移を書いていたのではで駄目なことに気付く。
   　
3. ここでの制約を見直すと、以下。
4. 日目から日目への遷移を、から通れない道の分だけ引くようにすれば、全体でにできる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

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

        int mod = 998244353;
        long[][] dp = new long[k + 1][n];
        dp[0][0] = 1;
        for (int i = 0; i < k; i++) {
            long sum = 0;
            for (int j = 0; j < n; j++) {
                sum += dp[i][j];
            }
            for (int j = 0; j < n; j++) {
                long rem = 0;
                for (int j2 : list.get(j)) {
                    rem += dp[i][j2];
                }
                dp[i + 1][j] = (sum - rem) % mod;
            }
        }
        System.out.println(dp[k][0]);
    }
}

ここまで29分36秒＋1ペナ。270位。

F問題以降は解けず。

Fはあみだくじをイメージしていて、スタートが一番上ともゴールが一番下とも限らないことから、（にlogが付くかも）とかから縮められる気が全くせず、早々に諦めたが、GもHも結局解けず、ラスト10分くらいで戻ってくる。

メモ化しながら愚直をやれば、同じバスを何度も調べなくなり、になるのでは？　と思ったりもしたが、その頃にはもう実装できる時間は残っておらず。
解説とも全然違ったが、本当に駄目なのかどうか後日試してみることにする。

Gはとが半々ずつ？とかエスパーすることばかり考えていてやっぱり全然駄目だった。

HはEの第一感と全く同じ形の「山個の累積XORがの通り数」でしか思いつかず。

最終結果：ABCDEの5完1500点、34分36秒、461位、パフォーマンス1855相当
レート変動：2101（Unrated）

原始根の性質だとか、アダマール変換だとか、全く知らないものが出てきているので、やっぱりABCをちゃんと全部埋めることで覚えていく必要はあるんだろうなとは思う。
でないと、こういう知らないとどうしようもない問題は一生解けないままだし。

なんてことをこの半年くらいずっと毎回のように言ってて、未だに何もできていないまま。
ABCで負け続けている最大の要因だとは思っているが、Unratedになったことでなかなか本気にもなれず。
今の足りない知識量でも、ARCやAGCで青落ちを免れ続けていることが逆に良くないのかもしれない。