AtCoder Beginner Contest 188

コンテスト前のレート：1834
レート通りのパフォーマンスが得られる順位：461位（1600点、169分59秒）もしくは462位（1500点、14分18秒）

A - Three-Point Shot

問題

思考過程

1. との小さい方大きい方 であるかどうかを判定する。

import java.util.Scanner;

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

        int a = Math.min(x, y);
        int b = Math.max(x, y);
        if (a + 3 > b) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分05秒＋0ペナ。438位。

B - Orthogonality

問題

思考過程

1. 何も考えずに問題文の通りの判定を行う。

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i] * b[i];
        }
        if (sum == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで2分31秒＋0ペナ。375位。

C - ABC Tournament

問題

思考過程

1. 愚直にシミュレーションすることを考える。
2. 回戦のリストを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));
        int n = Integer.parseInt(br.readLine());
        int n2 = 1 << n;
        List<Obj> list = new ArrayList<>(n2);
        String[] sa = br.readLine().split(" ");
        for (int i = 0; i < n2; i++) {
            Obj o = new Obj();
            o.i = i + 1;
            o.a = Integer.parseInt(sa[i]);
            list.add(o);
        }
        br.close();

        while (list.size() > 2) {
            List<Obj> wk = new ArrayList<>();
            for (int i = 0; i < list.size(); i+=2) {
                if (list.get(i).a > list.get(i + 1).a) {
                    wk.add(list.get(i));
                } else {
                    wk.add(list.get(i + 1));
                }
            }
            list = wk;
        }
        if (list.get(0).a > list.get(1).a) {
            System.out.println(list.get(1).i);
        } else {
            System.out.println(list.get(0).i);
        }
    }

    static class Obj {
        int i, a;
    }
}

ここまで8分23秒＋0ペナ。384位。

D - Snuke Prime

問題
何故かと誤読して時間を浪費した。

思考過程

1. すぬけプライムに全く加入しない場合の各日の合計金額を、いもす法を使って求め、各日について、いもす法の計算結果との小さい方を選択していけばよい。
2. よく見たら、普通に日数分の長さの配列を用意するのは、制約が大きいので無理。（例２を実行して気付く）
3. 配列ではなくTreeMapを使い、やの部分のみの情報を持つことにする。
4. いもす法は概ね同じような要領でできるが、集計時は各日について小さい方を選ぶだけでなく、それにマップのキーとキーの間の長さを掛ける必要がある。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeMap;

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 C = Integer.parseInt(sa[1]);
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            a[i] = Integer.parseInt(sa[0]) - 1;
            b[i] = Integer.parseInt(sa[1]);
            c[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        TreeMap<Integer, Long> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            map.put(a[i], map.getOrDefault(a[i], 0L) + c[i]);
            map.put(b[i], map.getOrDefault(b[i], 0L) - c[i]);
        }
        map.put(Integer.MAX_VALUE, 0L); // 番兵

        // いもす法
        Integer[] arr = map.keySet().toArray(new Integer[0]);
        for (int i = 1; i < arr.length; i++) {
            map.put(arr[i], map.get(arr[i]) + map.get(arr[i - 1]));
        }

        long ans = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            // 小さい方 × 区間の長さ を集計
            long v = Math.min(C, map.get(arr[i]));
            ans += v * (arr[i + 1] - arr[i]);
        }
        System.out.println(ans);
    }
}

ここまで21分24秒＋0ペナ。369位。

E - Peddler

問題
雑すぎて3ペナ。
主なミスは、下記ソース内の★1で配列cをINFではなく配列aの値で初期化していたり、★2でc[nx]とのminを取り忘れたりなど。

思考過程

1. 各町について、町に持ってくることができる最安の金を求め、の最大値を求めたい。
2. 町番号の小さい方から大きい方にしか移動できないので、前から順に見ていける。
3. である各からにを配るDPを行う。
4. 最低一度は配られた町についてのみ、を求め、その最大値を求める。

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

        int[] c = new int[n];
        Arrays.fill(c, Integer.MAX_VALUE); // ★1
        boolean[] b = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int nx : list.get(i)) {
                c[nx] = Math.min(c[nx], Math.min(c[i], a[i])); // ★2
                b[nx] = true;
            }
        }

        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (b[i]) {
                ans = Math.max(ans, a[i] - c[i]);
            }
        }
        System.out.println(ans);
    }
}

ここまで40分01秒＋3ペナ。507位。

F - +1-1x2

問題

思考過程

1. の場合は、する以外の選択肢がないので、が答え。それ以外のケースを考える。
2. 似たような過去問をやった覚えがあり、その時と同様にから始めてをするメモ化再帰をしてみる。しかし、無限ループしてしまいどうにも上手くいかない。
   　
3. 比較的最近のAGCの問題だった覚えがあったので、実際にその過去問（AGC044-A）を探し当て、解説が英語だったので自分の提出を見直してみる。
4. 今回の問題では倍とだけなので、上記提出の～行目をコピーしてきて今回向けに直していく。
5. 今回はコストが全部なので、そこを読み替える。オーバーフロー対策のif文も不要。だがそれだけだとまだ無限ループ。
   　
6. 過去問では初期値がなのに対し、今回は初期値が。現在値がを下回った時点で、あとはするしかないので、との差分を答えとする。
7. やっと無限ループはなくなったが、例１が9→8→4→2→3のようになってしまい、まだ合わない。
8. 答えの初期値をINFではなく、現在値ととの差分とする。これなら4→2→3を4→3にできる。
9. サンプルに加え、適当な大きい数でもTLEしなさそうなことを確認して提出。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static long x, y;
    static Map<Long, Long> map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        x = Long.parseLong(sa[0]);
        y = Long.parseLong(sa[1]);
        br.close();

        // 思考過程1
        if (x >= y) {
            System.out.println(x - y);
            return;
        }

        map = new HashMap<>();
        long ans = dfs(y); // 思考過程2
        System.out.println(ans);
    }

    static long dfs(long c) {
        if (map.containsKey(c)) {
            return map.get(c);
        }
        // 思考過程6
        if (c <= x) {
            return x - c;
        }

        long ret = c - x; // 思考過程8
        if (c % 2 == 0) {
            ret = Math.min(ret, dfs(c / 2) + 1);
            ret = Math.min(ret, dfs(c / 2) + c / 2);
        } else {
            ret = Math.min(ret, dfs(c / 2) + 2);
            ret = Math.min(ret, dfs(c / 2 + 1) + 2);
            ret = Math.min(ret, dfs(c / 2) + c / 2 + 1);
        }
        map.put(c, ret);
        return ret;
    }
}

ここまで67分03秒＋3ペナ。199位。

最終結果：ABCDEFの全完、82分03秒、236位、パフォーマンス2098
レート変動：1834→1863（+29）

今回は細かい実装ミスが目立ったことで、CDがやや時間かかりすぎで、Eは致命的に時間かかりすぎになってしまった。
Fはしっかり解けたとは言えないが、コンテストがない日は必ずくじかつを行うようにし始めてそろそろ2ヶ月が経過しており、過去問をちゃんと引き出しにできている成果の現れかなとは思う。

緑～青diffは全て埋まっている状態で、新規の黄diff以上を通したはこの半年間で10問程度。
昨年10月にはさすがに無精進の影響か、レートが激減したのだが、11月以降も高難易度について無精進なのは変わらず、くじかつだけ毎日やるようにしたら一気に回復したので、復習は馬鹿にならないな・・・という感じ。

AtCoderをやり始めてちょうど2年が経ち、やはりあまり使っていないことを色々忘れ始めて来ているのだと思う。

仕事が忙しい限りは、高難易度問題をじっくりやる気はなかなか起きないので、まだ当分は復習と弱点補強で青diff以下を落としにくいようにしていく方針。