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

コンテスト前のレート:2065
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:301位(1500点、31分48秒)


今回はD、C、B、A、E、Fの順に解こうとするのを貫いてみた。

A - Health M Death

問題

思考過程
  1. H \% M0かどうかで判定する。
import java.util.Scanner;

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

        if (h % m == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

DCBAと解いた時点で31分04秒+0ペナ。333位。
(A問題だけだと0分38秒)


B - Many Oranges

問題
公式解説O(1)の方法でやった。

思考過程
  1. 全部Bとした場合が個数最小。W \div Bをして、余りが出た場合は1個増やすしかないので切り上げする。
  2. 全部Aとした場合が個数最大。W \div Aをして、余りが出た場合は個数は増やせず適当に重くすることになるので切り捨てする。
     
  3. 起こり得ないかどうかの判定がよくわからないが、とりあえずサンプルを実行してみる。
  4. 例1が合わない。Wをグラム単位に合わせる必要があった。
  5. 例3の結果がmin \gt maxになったので、その場合に"UNSATISFIABLE"にすればいいのではないかと推測する。
  6. Unratedだし間違っててもいいやととりあえず提出したら通った。
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 w = sc.nextInt() * 1000; // 4
        sc.close();

        int min = (w + b - 1) / b; // 1
        int max = w / a; // 2
        if (min > max) { // 5
            System.out.println("UNSATISFIABLE");
        } else {
            System.out.println(min + " " + max);
        }
    }
}

DCBと解いた時点で30分26秒+0ペナ。378位。
(B問題だけだと3分42秒)


C - Comma

問題

思考過程
  1. i桁の数がいくつあるかを求め、それにコンマの数 (i-1) \% 3 を掛ける方針でいく。
  2. i桁の数は、基本的には10^i - 10^{i-1}個ある。例えばi=3なら、1000 - 100 = 900個。
  3. 最後だけはNを超える可能性があるため、Nとのminを取る。 が、これでは微妙に合わない。
     
  4. 上記2.が999 - 99 = 900個というイメージになるよう調整する。
import java.util.Scanner;

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

        long ans = 0;
        long a = 10;
        long b = 1;
        for (int i = 0; i < 17; i++) {
            long d = Math.min(a - 1, n) - b + 1;
            d = Math.max(d, 0);
            long v = i / 3;
            v *= d;
            ans += v;
            a *= 10;
            b *= 10;
        }
        System.out.println(ans);
    }
}

DCと解いた時点で26分44秒+0ペナ。305位。
(C問題だけだと14分41秒)


D - Shipping Center

問題
そんなに時間はかからずに貪欲だろうと思ったが、実装で手間取った。

思考過程
  1. 価値の大きい荷物から見ていき、荷物の大きさ以上で最小の箱を使うという貪欲でよいか?
  2. ある荷物をあえて選ばなかったときに、選べる数が増える(選ばなかった荷物より価値の小さい荷物2つを選べる)ようなことがあるかを考えてみて、なさそうだと思う。
     
  3. ceilingメソッドで箱を特定したいので、使える箱だけをTreeSetに入れたいが、値が重複したら困るので、自作しているMultiSetのようなものを使う。
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.w = sc.nextInt();
            o.v = sc.nextInt();
            arr[i] = o;
        }
        int[] x = new int[m];
        for (int i = 0; i < m; i++) {
            x[i] = sc.nextInt();
        }

        Arrays.sort(arr, (o1, o2) -> o2.v - o1.v); // vの降順

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt();
            MultiTreeSet<Integer> set = new MultiTreeSet<>();
            for (int j = 0; j < l; j++) {
                set.add(x[j]);
            }
            for (int j = r; j < m; j++) {
                set.add(x[j]);
            }

            int ans = 0;
            for (Obj o : arr) {
                Integer k = set.ceiling(o.w); // w以上で最小の値
                if (k != null) {
                    ans += o.v;
                    set.remove(k);
                }
            }
            System.out.println(ans);
        }
        sc.close();
    }

    static class Obj {
        int w, v;
    }

    // 以下ライブラリ

    // TreeSetと同じ感覚で使えて同一値を複数持てるもの
    // 長いので使われるメソッドのみ掲載
    static class MultiTreeSet<T> {
        TreeMap<T, Integer> map = new TreeMap<>();
        int size = 0;

        void add(T e) {
            map.put(e, map.getOrDefault(e, 0) + 1);
            size++;
        }

        void remove(T e) {
            if (e != null && map.containsKey(e)) {
                int val = map.get(e);
                if (val == 1) {
                    map.remove(e);
                } else {
                    map.put(e, val - 1);
                }
                size--;
            }
        }

        T ceiling(T e) {
            return map.ceilingKey(e);
        }
    }
}

提出
Dだけ解いた時点で12分03秒+0ペナ。329位。
D問題だけで見れば20番目にACしているが、上19人の内12人ほどは、普通に前から4問解いた上でこれより早いという・・。



E問題は、公式解説と似たようなことを、Tが連続する部分とAが連続する部分ごとにやろうとしてバグらせた気がするが、この方針自体も怪しかったのかどうか・・・。

F問題は、偶数が最大1個しか選べないので、奇数の36個で半分全列挙のようなことをするのだろうかなどと思ったりしたが、あまりできる気がせず、そもそも5分くらいしか時間を取らなかったので、何もまともに詰められず。



終結果:ABCDの4完、31分04秒、860位、パフォーマンス1552相当
レート変動:2065(Unrated)


前回のABCよりは解けなかった問題の難易度は高いけど、2回連続E問題が解けずに4完止まり。
Unratedなのが申し訳ないくらい。

やっぱりまだ黄色の実力があるとはあまり思えないし、ちょうど今月ARCが3回もあるので、さっさと青に戻った方がいいのではないだろうか。