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

ABC

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

A - Water Pressure

問題

思考過程
  1. D \div 100を求める。
  2. 切り捨てずに小数で答える必要があるため、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

問題

思考過程
  1. 入力をMap＜候補者名、得票数＞の形で管理する。
  2. 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

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

思考過程
  1. クエリごとに毎回カウントするのはTLE。各身長に該当する人数について上からの累積和を事前に求めておけば、高速に答えられる。
  2. 入力のAをTreeMap＜身長、該当人数＞の形にし、上からの累積和を求める。
  3. そうすると、マップでキーが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. (1, 2), (2, 3)のような入力があったとすると、「1-2-3」という並びができ、両端の"1"と"3"の隣にはまだ指定のものを置くことができるが、"2"の隣に"1", "3"以外のものを置くのは無理。
  2. 入力のA, Bを問わず1回登場した値は連結成分の端に位置することになり、端にあるものが登場すると内部に位置することになり、内部にあるものが登場した時点で"No"となる。
  3. それ以外は"Yes"？　→15/38ケースWA
    　
  4. 全体が1つの円環となるようなケースも"No"だった。　→まだ13/38ケースWA
    　
  5. 連結成分が複数の場合でも、どれか1つの連結成分が円環になっているだけで"No"だった。
  6. 上記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とだいたい同じだった。

思考過程
  1. 同じ金額を払うなら、なるべく大きい金額の硬貨を使った方がよい。
  2. ちょうどX円を払うとした場合、上記1.の貪欲をすると金額A_iの硬貨をC_i枚使うことになるとする。
  3. すると、小さい方からi番目の硬貨を使う枚数は、お釣りがないようにC_i枚とするか、B_i = \frac{A_{i+1}}{A_i}として、i+1番目の硬貨を1枚多く使ってお釣りでB_i - C_i枚使うかとなる。
    　
  4. あとは下から以下のようなDPを行い、DP0[N]が答え。
    • DP0[i]:=i種類目についてC_i枚払う時に、下からi種類目までで使う最小合計枚数
    • DP1[i]:=i種類目についてB_i - C_i枚お釣りをもらう時に、下からi種類目までで使う最小合計枚数
  5. 書き上がったコードでは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

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

思考過程
  1. 高橋君にi番目を渡した時に青木君に渡せるもの（j番目とする）がいくつあるかを、各iごとに求める形にできないか考える。
  2. Aの昇順にペアソートすると、高橋君にとっての嬉しさが満たされる条件がj \leq iとなり、青木君にとっての嬉しさが満たされる条件がB_j \geq B_iとなる。
  3. これは、BITまたはセグメント木を使ってB_iに+1とB_i以上の範囲の合計取得を繰り返していけば求められる。
  4. ただし、B_i \leq 10^9のため事前に座標圧縮が必要。　→例３が34になる
    　
  5. Aに重複が存在する場合、その中でBを降順にする。　→例３が36になる
    　
  6. 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

提出
ここまで52分41秒＋2ペナ。111位。



残り時間はGとHを半々くらい考えていたが全然わからず。
GはO(NK^2)のDPくらいしか思い付かず。
Hは最小費用流になったりしないかと思ったりしたが、簡単にその形にできそうには思えないまま終了。



最終結果：ABCDEFの6完2000点、62分41秒、170位、パフォーマンス2225相当
レート変動：2051（Unrated）


最近はDかEまで早くてその次で大ブレーキということが多い気がしていたが、今回はEとFが早かったのは良かった。
Cで解説を見るまで累積和やFのような座圧＆BITしか思い付いていなかったのがひどい。
あとDとFでコーナーケースの気付かなさも。

Cで実装重くしたとはいえ、それでも5分でできてはいるので、DでWA出した時から順位表を見始めて1000位前後をさまよっていた時は、みんな早すぎと思っていた。