パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)(Rated範囲外)

A - Water Pressure
- 思考過程
B - Election
- 思考過程
C - Counting 2
- 思考過程
D - Neighbors
- 思考過程
E - Minimal payments
- 思考過程
F - Jealous Two
- 思考過程

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

A - Water Pressure

思考過程

$D \div 100$ を求める。
切り捨てずに小数で答える必要があるため、 $100.0$ で割ることでdouble型になるようにする。

import java.util.Scanner;

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

        System.out.println(d / 100.0);
    }
}

ここまで0分56秒＋0ペナ。533位。

B - Election

問題

思考過程

入力をMap＜候補者名、得票数＞の形で管理する。
Mapの全エントリを調べ、得票数が最大のものを探す。

import java.util.HashMap;
import java.util.Map;
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();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        sc.close();

        int max = 0;
        String ans = null;
        for (String s : map.keySet()) {
            int val = map.get(s);
            if (val > max) {
                max = val;
                ans = s;
            }
        }
        System.out.println(ans);
    }
}

ここまで2分43秒＋0ペナ。249位。

C - Counting 2

問題
ただ二分探索をするだけでよかったのに面倒なことをしてしまった。

思考過程

クエリごとに毎回カウントするのはTLE。各身長に該当する人数について上からの累積和を事前に求めておけば、高速に答えられる。
入力の $A$ をTreeMap＜身長、該当人数＞の形にし、上からの累積和を求める。
そうすると、マップでキーが $x_i$ 以上で最小であるエントリの値がそのまま答えになる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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 q = Integer.parseInt(sa[1]);

        sa = br.readLine().split(" ");
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sa[i]);
            map.put(a, map.getOrDefault(a, 0) + 1);
        }

        int[] x = new int[q];
        for (int i = 0; i < q; i++) {
            x[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        map.put(1000000001, 0);
        Integer[] arr = map.keySet().toArray(new Integer[0]);
        for (int i = arr.length - 2; i >= 0; i--) {
            Integer k1 = arr[i];
            Integer k2 = arr[i + 1];
            int val = map.get(k1) + map.get(k2);
            map.put(k1, val);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            pw.println(map.ceilingEntry(x[i]).getValue());
        }
        pw.flush();
    }
}

ここまで7分57秒＋0ペナ。920位。

D - Neighbors

問題
これも回りくどい実装した。

思考過程

$(1, 2), (2, 3)$ のような入力があったとすると、「1-2-3」という並びができ、両端の"1"と"3"の隣にはまだ指定のものを置くことができるが、"2"の隣に"1", "3"以外のものを置くのは無理。
入力の $A, B$ を問わず $1$ 回登場した値は連結成分の端に位置することになり、端にあるものが登場すると内部に位置することになり、内部にあるものが登場した時点で"No"となる。
それ以外は"Yes"？　→15/38ケースWA
　
全体が $1$ つの円環となるようなケースも"No"だった。　→まだ13/38ケースWA
　
連結成分が複数の場合でも、どれか $1$ つの連結成分が円環になっているだけで"No"だった。
上記2.で同一連結成分の端同士を連結しようとしたかどうかは、UnionFindを使って連結前に既に同一連結成分かどうかを調べれば十分。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
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]);
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            a[i] = Integer.parseInt(sa[0]) - 1;
            b[i] = Integer.parseInt(sa[1]) - 1;
        }
        br.close();

        boolean[] used = new boolean[n]; // 既に内部にあるかどうか
        Set<Integer> set = new HashSet<>(); // 端にあるもの
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < m; i++) {
            // 既に内部か、円環になる場合
            if (used[a[i]] || used[b[i]] || uf.same(a[i], b[i])) {
                System.out.println("No");
                return;
            }

            if (set.contains(a[i])) {
                set.remove(a[i]);
                used[a[i]] = true;
            } else {
                set.add(a[i]);
            }
            if (set.contains(b[i])) {
                set.remove(b[i]);
                used[b[i]] = true;
            } else {
                set.add(b[i]);
            }

            uf.union(a[i], b[i]);
        }
        System.out.println("Yes");
    }

    // 以下ライブラリ

    static class UnionFind {
        int[] parent, size;
        int num = 0; // 連結成分の数

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            num = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
                size[py] += size[px];
                num--;
            }
        }

        int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }

        /**
         * xとyが同一連結成分か
         */
        boolean same(int x, int y) {
            return find(x) == find(y);
        }
    }
}

ここまで20分31秒＋2ペナ。687位。

E - Minimal payments

問題
ものすごく既視感があったのだが、後から探したらABC155-Eとだいたい同じだった。

思考過程

同じ金額を払うなら、なるべく大きい金額の硬貨を使った方がよい。
ちょうど $X$ 円を払うとした場合、上記1.の貪欲をすると金額 $A_i$ の硬貨を $C_i$ 枚使うことになるとする。
すると、小さい方から $i$ 番目の硬貨を使う枚数は、お釣りがないように $C_i$ 枚とするか、 $B_i = \frac{A_{i+1}}{A_i}$ として、 $i+1$ 番目の硬貨を $1$ 枚多く使ってお釣りで $B_i - C_i$ 枚使うかとなる。
　
あとは下から以下のようなDPを行い、が答え。
- $DP0[i]:=$ $i$ 種類目について $C_i$ 枚払う時に、下から $i$ 種類目までで使う最小合計枚数
- $DP1[i]:=$ $i$ 種類目について $B_i - C_i$ 枚お釣りをもらう時に、下から $i$ 種類目までで使う最小合計枚数
書き上がったコードでは $N=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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        long x = Long.parseLong(sa[1]);
        sa = br.readLine().split(" ");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sa[i]);
        }
        br.close();

        if (n == 1) {
            System.out.println(x);
            return;
        }

        long x2 = x;
        long[] c = new long[n];
        for (int i = n - 1; i >= 0; i--) {
            c[i] = x2 / a[i];
            x2 %= a[i];
        }

        long[] b = new long[n - 1];
        for (int i = 0; i < n - 1; i++) {
            b[i] = a[i + 1] / a[i];
        }

        long[] dp0 = new long[n];
        long[] dp1 = new long[n];
        dp0[0] = c[0];
        dp1[0] = b[0] - c[0];
        for (int i = 1; i < n - 1; i++) {
            dp0[i] = Math.min(c[i] + dp0[i - 1], c[i] + 1 + dp1[i - 1]);
            dp1[i] = Math.min(b[i] - c[i] + dp0[i - 1], b[i] - c[i] - 1 + dp1[i - 1]);
        }
        long ans = c[n - 1] + Math.min(dp0[n - 2], dp1[n - 2] + 1);
        System.out.println(ans);
    }
}

ここまで36分24秒＋2ペナ。157位。

F - Jealous Two

問題
例３がなければ確実にペナ出してた。

思考過程

高橋君に $i$ 番目を渡した時に青木君に渡せるもの（ $j$ 番目とする）がいくつあるかを、各 $i$ ごとに求める形にできないか考える。
$A$ の昇順にペアソートすると、高橋君にとっての嬉しさが満たされる条件が $j \leq i$ となり、青木君にとっての嬉しさが満たされる条件が $B_j \geq B_i$ となる。
これは、BITまたはセグメント木を使って $B_i$ に $+1$ と $B_i$ 以上の範囲の合計取得を繰り返していけば求められる。
ただし、 $B_i \leq 10^9$ のため事前に座標圧縮が必要。　→例３が34になる
　
$A$ に重複が存在する場合、その中で $B$ を降順にする。　→例３が36になる
　
$A$ の値が同じものに対して $B$ も同じであるものが $M$ 個存在する場合、さらに追加で $_MC_2$ 通り。というか、そのようなものが直前に $cnt$ 個続いていたら、 $cnt$ 通りを答えに追加。

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

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

        int[] b2 = zaatu(b);
        for (int i = 0; i < n; i++) {
            arr[i].b = b2[i];
        }
        Arrays.sort(arr, (o1, o2) -> {
            if (o1.a != o2.a) {
                return o1.a - o2.a;
            }
            return o2.b - o1.b;
        });

        FenwickTree ft = new FenwickTree(n + 2);
        long ans = 0;
        long cnt = 0;
        for (int i = 0; i < n; i++) {
            Obj o = arr[i];
            ft.add(o.b, 1);
            ans += ft.sum(o.b, n + 2);
            if (i > 0) {
                Obj o2 = arr[i - 1];
                if (o2.a == o.a && o2.b == o.b) {
                    cnt++;
                    ans += cnt;
                } else {
                    cnt = 0;
                }
            }
        }
        System.out.println(ans);
    }

    static class Obj {
        int a, b;
    }

    // 以下ライブラリ

    static int[] zaatu(long[] a) {
        TreeMap<Long, Integer> map = new TreeMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], null);
        }
        Long[] arr = map.keySet().toArray(new Long[0]);
        int cnt = 0;
        for (Long i : arr) {
            cnt++;
            map.put(i, cnt);
        }
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = map.get(a[i]);
        }
        return b;
    }
}

// 以下ACLを移植したFenwickTree