C - 検索

問題概略
K個の文字列にヒットして、N-K個の文字列にはヒットしない最小の文字列を出力せよ

制約
10^5

解法
まず、考えうる最高の長さの文字列を探す。
具体的には必要なものの最長の共通部分を二分法で探していく。(1個目と2個目、2と3という風にo(n log n)で出来る)
次にその文字列に対して、いらない文字列との共通部分が無いような最長の長さを二分法で求める。
おしまい

    public static void main(String[] args) {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        K = ni();
        A = niad(K);
        st = new String[N];
        for (int i = 0; i < N; i++) {
            st[i] = next();
        }
        boolean[] notNeed = new boolean[N];
        Arrays.fill(notNeed, true);
        for (int i = 0; i < K; i++) {
            notNeed[A[i]] = false;
        }
        for (int i = 0; i < N; i++) {
            if (notNeed[i]) gomi.add(st[i]);
            else need.add(st[i]);
        }
        long startTime = System.currentTimeMillis();
        //検索から省きたいものがない場合空文字
        if (gomi.size() == 0) {
            System.out.println("");
            return;
        }

        //最高の場合の文字列を探す
        String max = need.get(0);
        for (String s : need) {
            int len = getStartOfSame(0, min(max.length(), s.length()), max, s);
            if (len == 0) {
                System.out.println("-1");
                return;
            }
            max = max.substring(0, len);
        }
        int minLen = binarysearch(max.length() - 1, -1, max);
        if (minLen == 0) {
            System.out.println("-1");
            return;
        }
        System.out.println(max.substring(0, minLen));
        long endTime = System.currentTimeMillis();
        System.err.println(endTime - startTime);
    }

    public static boolean solve2(long v, String ls, String rs) {
        return ls.substring(0, (int) v + 1).equals(rs.substring(0, (int) v + 1));
    }

    //最大の長さを返す 添字を渡される
    static int getStartOfSame(long ok, long ng, String ls, String rs) {
        //int ok = 0; //解が存在する
        //int ng = N; //解が存在しない
        while (Math.abs(ok - ng) > 1) {
            long mid;
            if (ok < 0 && ng > 0 || ok > 0 && ng < 0) mid = (ok + ng) / 2;
            else mid = ok + (ng - ok) / 2;

            if (solve2(mid, ls, rs)) {
                ok = mid;
            }
            else {
                ng = mid;
            }
        }
        //0なら一文字も合わない可能性がある
        if (ok == 0) {
            if (ls.charAt(0) != rs.charAt(0)) return 0;
        }
        return (int) ok + 1;
    }

   
}