AtCoder Beginner Contest 203(Rated範囲外)

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

A - Chinchirorin

問題

思考過程

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();
        int c = sc.nextInt();
        sc.close();

        if (a == b) {
            System.out.println(c);
        } else if (a == c) {
            System.out.println(b);
        } else if (b == c) {
            System.out.println(a);
        } else {
            System.out.println(0);
        }
    }
}

ここまで1分15秒＋0ペナ。315位。

B - AtCoder Condominium

問題

思考過程

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

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                ans += i * 100 + j;
            }
        }
        System.out.println(ans);
    }
}

ここまで2分17秒＋0ペナ。78位。

C - Friends and Travel costs

問題

思考過程

1. の昇順にペアソートする。
2. 現在地や所持金などを必要に応じて管理しながら、前から順に処理していきたい。
3. 最初の所持金や受け取ったお金をすぐ最終到達点に変換してしまえば、人目を調べる時、であれば村にたどり着けると判定できたり、をそのまま答えにできたりする。

import java.util.Arrays;
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 k = sc.nextInt();
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.a = sc.nextLong();
            o.b = sc.nextInt();
            arr[i] = o;
        }
        sc.close();

        Arrays.sort(arr, (o1, o2) -> Long.compare(o1.a, o2.a));
        long x = k;
        for (Obj o : arr) {
            if (x < o.a) {
                break;
            }
            x += o.b;
        }
        System.out.println(x);
    }

    static class Obj {
        long a, b;
    }
}

ここまで7分27秒＋0ペナ。269位。

D問題は解けず。
範囲を動かしていって差分計算をすることばかり考えていて、二分探索とか全く思いつかなかった。

E - White Pawn

問題

思考過程

1. 到達可能な座標の集合を持ちながら、黒のポーンの座標が小さい順に処理していけないか考える。
2. 一瞬黒のポーン個ごとに倍に増えていくのではないかと思ったが、そんなことはなく、高々ずつしか増えないため、答えは最大。集合の要素数がに収まるので、集合を持つことは可能。
3. ただし、毎回新しい集合に入れ直していたらとなってしまうため、黒のポーンに当たる箇所だけ更新していくことを考える。
   　
4. 座標が同じ黒のポーンについて、まとめて処理していく。
5. 基本的には、真っ直ぐ当たった場合は集合から取り除き、斜めの場合は追加すればいいが、黒のポーンがつ隣り合っている場合に処理の仕方を間違えると、先に取り除いてしまったがために、本来斜めに行けるのに判定に失敗するといったことが起こり得る。
6. 一旦追加リストと削除リストに溜めておき、同一座標について全て処理が終わってからまとめて反映させることで、上記の誤りを回避する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

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]);
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.x - o2.x);
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.x = Integer.parseInt(sa[0]);
            o.y = Integer.parseInt(sa[1]);
            que.add(o);
        }
        br.close();

        Set<Integer> set = new HashSet<>();
        set.add(n);
        while (!que.isEmpty()) {
            Obj o = que.poll();
            // x座標が同じ黒のポーンリスト
            List<Obj> list = new ArrayList<>();
            list.add(o);
            while (!que.isEmpty() && que.peek().x == o.x) {
                list.add(que.poll());
            }

            List<Integer> add = new ArrayList<>();
            List<Integer> rem = new ArrayList<>();
            for (Obj o2 : list) {
                if (set.contains(o2.y - 1) || set.contains(o2.y + 1)) {
                    add.add(o2.y);
                } else {
                    rem.add(o2.y);
                }
            }
            for (Integer i : rem) {
                set.remove(i);
            }
            for (Integer i : add) {
                set.add(i);
            }
        }
        System.out.println(set.size());
    }

    static class Obj {
        int x, y;
    }
}

ABCEと解いた時点で35分35秒＋0ペナ。66位。

F - Weed

問題
DとFどちらに集中するか迷ったが、なんとなくFがやれそうな気がしたのでFを解いてみることにして、残り3分でAC。

思考過程

1. まずは昇順ソートしておく。
2. 答えの操作回数の方は、最大でも回。
3. （回も操作しない）の場合は実装上不都合があるので除いておく。
   　
4. 青木君の操作の後残った中で最大のものをとすると、～の内なるべく大きいものが残っているのが最適っぽいので、以下でが大きい順に本が残っているとする。
5. 高橋君の操作については、を始点としてシミュレーションしていき、抜いた本数が初めて本以上となった時点での操作回数と抜いた本数を求める。
6. 回のシミュレーションは程度でできるため（始点に選ぶ要素の値が毎回半分以下になるので。あと二分探索の分）、これをについて全探索し、操作回数が最小→抜いた本数が最大の優先度で最良の値を求める。　→34/53ケースWA
   　
7. 高橋君の操作において、回の操作は必ず連続した区間になるが、回行う場合は、最大個の区間に分けるのが最適になる可能性もある。
8. とりあえず、上記5～6.で行った全探索を少し変形して、「の要素に歯抜けはないとして、高橋君が番目を始点として回操作を行った時に抜ける草の本数」を全部求めておく。
9. 上記8.のデータを元に、「高橋君が回目は番目を始点として、回目以降は前回の終点の次以降のどこを始点にしてもよいという条件で、回操作を行った時に抜ける草の本数」をする。
10. DPの遷移は、番目を始点とした操作を行わない場合と行う場合のmaxを取る。
    　
11. 出来上がったDPテーブルをが小さい順に確認していき、が初めて以上となったについて、の最大値を求める。

import java.util.Arrays;
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 k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        // 3
        if (n == k) {
            System.out.println("0 " + k);
            return;
        }

        // 1
        Arrays.sort(a);
        // 8
        int[][] dp = new int[n][31];
        for (int i = 0; i < n; i++) {
            int cnt1 = 0; // 操作回数
            int x = i; // 始点
            while (true) {
                cnt1++;
                int idx = binarySearch(a, a[x] / 2);
                idx--;
                x = idx;
                dp[i][cnt1] = i - idx;
                if (idx == -1) {
                    break;
                }
            }
            for (int j = cnt1; j < 30; j++) {
                dp[i][j + 1] = dp[i][j];
            }
        }

        // 9
        int[][] dp2 = new int[n + 1][31];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < 31; j++) {
                // 10
                dp2[i + 1][j] = Math.max(dp2[i][j], dp[i][1] + dp2[i - dp[i][1] + 1][j - 1]);
            }
        }

        // 11
        int v = n - k; // 2
        int max = 0;
        int ans1 = v;
        boolean flg = false;
        for (int j = 1; j <= v; j++) {
            if (flg) {
                break;
            }
            for (int i = 1; i <= n; i++) {
                if (dp2[i][j] >= n - k) {
                    flg = true;
                    ans1 = j;
                }
                max = Math.max(max, dp2[i][j]);
            }
        }
        System.out.println(ans1 + " " + (n - max));
    }

    // arrayの中で、valより大きい最小の要素のインデックスを二分探索で取得
    static int binarySearch(int[] array, int val) {
        int ok = array.length;
        int ng = -1;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (array[mid] > val) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }
}

ABCEFと解いた時点で97分05秒＋2ペナ。145位。

最終結果：ABCEFの5完1700点、107分05秒、159位、パフォーマンス2297相当
レート変動：2080（Unrated）

とりあえず、中央値→二分探索という選択肢を覚えておこう・・・。