新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

参加記録:AtCoder Regular Contest #033

[参加記録] AtCoder Regular Contest #033

コンテストURL


Welcome to AtCoder Regular Contest 033 - AtCoder Regular Contest 033 | AtCoder

結果

  • A問題、B問題の200点。
    • CがひたすらTLE…といういつものパターン。

プログラム

A問題
  • N文字の文字列の部分文字列の個数を求める。なお同じ文字は絶対に現れない。
    • 1からNの総和でOK。
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans += i;
        }

        System.out.println(ans);
        scan.close();
    }
}
B問題
  • 数字の配列AとBについて、(AとB両方に含まれる数字の数 / AかBのどちらかに含まれる数字の数)を求める。
    • containsはHashSetが速い!という噂を聞いていたのでおもむろにHashSetに入れたら通った。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int Na = scan.nextInt();
        int Nb = scan.nextInt();
        Set<Integer> A = new HashSet<Integer>();
        Set<Integer> B = new HashSet<Integer>();

        for (int i = 0; i < Na; i++) {
            A.add(scan.nextInt());
        }
        for (int i = 0; i < Nb; i++) {
            B.add(scan.nextInt());
        }

        int andNum = 0;

        for (int num : A) {
            if (B.contains(num)) {
                andNum++;
            }
        }

        System.out.println((double) (andNum) / (Na + Nb - andNum));
        scan.close();
    }
}
C問題
  • Q個のクエリが与えられ、i番目のクエリとしてT[i]とX[i]が与えられる。
    • T[i]が1のとき、集合SにX[i]を加える。
    • T[i]が2のとき、集合SでX[i]番目に小さい数を出力し、またSから取り除く。
    • 上を参考にしつつ書いてみる。
    • ほぼ解説のプログラムの写経ですが、お陰でなんとか理解できたかな…?
import java.util.Scanner;
 
public class Main {
 
    // 実際のクエリの個数より少し多めに取っておく(BITの添字の関係)
    public static final int QUERY_NUM = 2000010;
 
    public static void main(String[] args) {
        new Main().calc();
    }
 
    public void calc() {
        Scanner scan = new Scanner(System.in);
 
        int Q = scan.nextInt();
        int[] T = new int[Q];
        int[] X = new int[Q];
        for (int i = 0; i < Q; i++) {
            T[i] = scan.nextInt();
            X[i] = scan.nextInt();
        }
 
        BIT bit = new BIT(QUERY_NUM);
 
        for (int i = 0; i < Q; i++) {
            // クエリTi = 1の場合、Sに数Xiを追加する。
            if (T[i] == 1) {
                // BIT[X[i]]に1を足す。
                // これにより、BIT.sum(i)でi以下の数が何個存在するかを求められる。
                bit.update(X[i], 1);
            } 
            // クエリTi = 2の場合、
            // SからXi番目に小さい数を表示し、Sから削除する。
            else {
                // 現在、BIT[a]には、a以下の数字が何個あるかが入っている。
                // X[i]が3のとき、3番目に小さい数を求めて削除する必要がある。
                // たとえば追加された数が{2, 3, 5, 9}ならば、
                //          i: 1 2 3 4 5 6 7 8 9
                // BIT.sum(i): 0 1 2 2 3 3 3 3 4
                // というような数が返ってくる。
                // ここで、二分探索によってsum(i)が3となる最小のiを求める。
                // (上記の例では5が答えとなる)
                int min = 1;
                int max = QUERY_NUM - 1;
 
                while (max > min + 1) {
                    int mid = (min + max) / 2;
                    
                    // mid以下の数字がX[i]より小さい場合、
                    // 探索範囲をmax方面へ広げる必要がある。
                    if (bit.sum(mid) < X[i]) {
                        min = mid;
                    }
                    // mid以下の数字がX[i]より大きいの場合、
                    // 探索範囲をmin方面へ狭める必要がある。
                    // また、mid以下の数字がX[i]と等しい場合でも、
                    // そのような中でも最も小さいmidを求める必要がある。
                    else {
                        max = mid;
                    }
                }
                // 最終的にはmaxが答えになる
                int ret = max;
                
                // 答えを出力
                System.out.println(ret);
                // BITから答えを削除。
                // 現在は含まれている個数を入れているので、
                // -1すればOK
                bit.update(ret, -1);
            }
        }
 
        scan.close();
 
    }
 
    /**
     * Binary Indexed Tree。 
     * N個の配列Vを持ち、 V[a]に値wを加える関数addと、 
     * v[1] + v[2] + ... +v[a]の求める関数sumを持つ。
     * 
     * N = 8のとき、以下の様な構造を持つ(配列の添字に注意。) 
     *              a1+a2+...+a8
     *               /         \ 
     *         a1+a2+a3+a4 a5+a6+a7+a8
     *            / \          / \ 
     *       a1+a2 a3+a4   a5+a6 a7+a8 
     *       / \    / \     / \    / \ 
     *     a1 a2   a3 a4   a5 a6   a7 a8
     * 
     * 上記の通り、それぞれの頂点は、全ての子の和を持つ。
     * 
     * 実装的には、N個の配列Vを持ち、以下に該当する値を格納する。
     * 
     *                 V[8] 
     *              /       \ 
     *           V[4]         X 
     *           / \        /  \ 
     *       V[2]   X     V[6]   X 
     *       / \    / \   / \    / \ 
     *     V[1] X V[3] X V[5] X V[7] X
     * 
     * たとえば、add(5, w)は、V[5], V[6], V[8]にwを足す。 
     * sum(1, 6)は、V[4] + V[6]を返す。
     */
    class BIT {
        private int N;
        private int[] v;
 
        public BIT(int N) {
            this.N = N;
            v = new int[N];
        }
 
        public void update(int a, int w) {
            // 自分とその親に値wを足していく。
            // 注:i += i & -iの意味
            // 数iの立っているbitの中で最も下位のbitを得る。
            // v[i]の管理する区間はiの最も下位の立っているbitと同じ。
            for (int i = a; i <= N; i += i & -i) {
                v[i] += w;
            }
        }
 
        public int sum(int a) {
            int ret = 0;
            // 自分と自分より左にいる数を合計していく。
            for (int i = a; i > 0; i -= i & -i) {
                ret += v[i];
            }
            return ret;
        }
    }
}
  • そして意気揚々と提出したらTLEでリアルで叫んでしまった。
    • 入出力 - てきとーな日記を参考に入出力を変えたら無事AC。
    • Javaの標準入出力ライブラリは遅いというのは聞いていたけどここまでとは・・・
    • 今後は自作ScannerとPrintWriterを使おう。といっても問題が解けなきゃ意味ないけど。。。