AtCoder Grand Contest 057 - ks2mのブログ

A - Antichain of Integer Strings
- 思考過程
B - 2A + x
- 思考過程

コンテスト前のレート：1961
レート通りのパフォーマンスが得られる順位：419位（1100点、185分23秒）

A - Antichain of Integer Strings

問題
部分文字列の説明まで開いたのに、いつの間にか連続とは限らない部分列で考えていた。

思考過程

$L$ と $R$ の桁数が同じ場合は、 $R-L+1$ 個全てを集合 $A$ に入れることができる。
そうでない場合、とりあえず $R$ と同じ桁数の値は全て選択して問題ないので、 $B=10^x \leq R$ を満たす最大の $B$ を求め、まず $R-B+1$ 個を答えに加算する。
　
$R \geq 2B$ ならば、 $1001$ ～ $1999$ （桁数は適当）の間に $1$ ～ $999$ は全部現れるので、 $R$ より桁数が少ない数は $1$ つも選択できない。
$R \lt 2B$ の場合、 $R=1001, 1002, \cdots$ と増やしてみると $101, 102, \cdots$ が選べなくなり（※この時点では連続とは限らないと勘違いしていた）、 $R=1998, 1997, \cdots$ と減らしてみると $999, 998, \cdots$ が選べるようになりそう。
$2$ 桁少ない数は、 $1$ 桁少ない数を全部選んだら選べなくなるので考えなくてよさそう。
　
証明できていないが、なんとなく単調性がありそうなので、二分探索をして $B-OK$ を答えに加算してみることにする。
二分探索の判定部分は、midをxxxxとして、1xxxxとx0xxxの少なくとも一方が $R$ 以下の場合NGとする。　→サンプルのみAC。REも出ている。
　
1xxxxやx0xxxをint型で扱っていたので、long型にする。　→REはなくなったがサンプル以外全部WAなのは変わらず。
誤読に気が付き、1xxxxとxxxx0で判定するように修正。

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            int l = Integer.parseInt(sa[0]);
            int r = Integer.parseInt(sa[1]);

            int b = 1000000000;
            while (b > 0) {
                if (b <= r) {
                    break;
                }
                b /= 10;
            }
            if (b <= l) {
                pw.println(r - l + 1);
                continue;
            }
            int v1 = r - b + 1;

            int ok = b;
            int ng = l - 1;
            while (Math.abs(ok - ng) > 1) {
                int mid = (ok + ng) / 2;
                String s = String.valueOf(mid);
                long x = Long.parseLong("1" + s);
                long y = Long.parseLong(s + "0");
                if (x <= r || y <= r) {
                    ng = mid;
                } else {
                    ok = mid;
                }
            }
            int v2 = b - ok;

            pw.println(v1 + v2);
        }
        br.close();
        pw.flush();
    }
}

ここまで32分55秒＋2ペナ。393位。

B - 2A + x

問題

思考過程

解を更新できる見込みがなくなるまで、PriorityQueueから最小値を取り出して操作を行うことを繰り返すような流れを考えてみる。
$x$ をいくつにすればよいのかわからないので、 $x=0$ の場合と $x=X$ の場合の値を両方残しておく。
操作を複数回行った後でも、 $x=0$ を続けた場合と $x=X$ を続けた場合の範囲内の値は全て取ることが可能。
　
解を更新できる見込みがなくなるのはいつになるのか？
とりあえずソート後の $A_N$ に最も近付くようにその他の要素を操作すると、例１では $18$ ～ $24$ 、例４では $33$ ～ $46$ の間に全ての要素が収まる。
そこから最小要素を $x=X$ 、最大要素を $x=0$ として操作した場合のことを考えると、最大と最小の差は $2$ 倍して $X$ 減るのが最善。
そのため、ある時点で求まった解が $X$ 未満なら最終的に $0$ にでき、そうでなければそれ以上操作しても悪化するだけであることがわかる。
またこのことから、 $A_N \times 2$ とかの周辺を目指して各要素を操作することをしても、 $A_N$ 周辺より良くなることはないので、 $A_N$ を基準に考えて問題なさそう。
　
各要素について、 $A_N$ 以下の最大値と $A_N$ 以上の最小値のどちらを目指すかをどうやって決めればよいか？
一旦全て $A_N$ 以下の最大値を取るようにしておき、小さい方から順に $A_N$ 以上の最小値に変えていく全探索を行う。（ $x=0$ を続けた場合の値が小さい順が、 $x=X$ を続けた場合の値が小さい順にもなっている扱いにしてしまっていて1ペナ）

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

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 x = 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]);
        }
        br.close();

        TreeSet<Obj> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.min = a[i];
            o.max = a[i];
            set.add(o);
        }

        long fmax = set.last().min; // ソート後のa[n-1]に相当
        while (true) {
            Obj o = set.first();
            if (o.min * 2 > fmax) {
                break;
            }
            set.pollFirst();
            o.min = o.min * 2;
            o.max = o.max * 2 + x;
            if (o.max >= fmax) {
                continue;
            }
            set.add(o);
        }

        Obj[] arr = set.toArray(new Obj[0]);
        MultiTreeSet<Long> set2 = new MultiTreeSet<>();
        for (Obj o : arr) {
            set2.add(o.max);
        }
        long ans = fmax - set2.first();

        for (int i = 0; i < arr.length - 1; i++) {
            Obj o = arr[i];
            set2.remove(o.max);
            long val = o.min * 2 - set2.first();
            ans = Math.min(ans, val);
        }
        if (ans < x) {
            ans = 0;
        }
        System.out.println(ans);
    }

    static class Obj implements Comparable<Obj> {
        long min, max;

        @Override
        public int compareTo(Obj o) {
            if (min != o.min) {
                return Long.compare(min, o.min);
            }
            return Long.compare(max, o.max);
        }
    }

    // 以下ライブラリ（未使用メソッドを削除している）

    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 first() {
            return map.firstKey();
        }
    }
}