AtCoder Regular Contest 129

コンテスト前のレート：2018
レート通りのパフォーマンスが得られる順位：277位（1200点、76分09秒）

A - Smaller XOR

問題

思考過程

1. とりあえずこういう形の問題は、をの場合の答えとして、で求めたい。
   　
2. という条件については、適当になどとしてみてとしてどのような値が可能かを考える。（一旦の条件は考えない）
3. 前の桁から調べていき、まず初めの桁の部分について側がだとの当該桁もとなり、条件を満たさない。
4. の桁目をとする場合、の当該桁はとなり、以降の桁は通り任意に選べる。
5. の桁目をとする場合は、上桁がとなるので、上桁をないものとして以降の桁で同様の数え上げを繰り返せる。
   　
6. ここにの条件を取り込むことを考える。
7. 上記4.の桁目の処理で数え上げている値は、～の範囲の値全てとなるので、この範囲かつ以下である値の数を加算するように変更する。

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(" ");
        long n = Long.parseLong(sa[0]);
        long l = Long.parseLong(sa[1]) - 1;
        long r = Long.parseLong(sa[2]);
        br.close();

        System.out.println(calc(r, n) - calc(l, n));
    }

    static long calc(long x, long m) {
        long ret = 0;
        char[] s = Long.toBinaryString(m).toCharArray();
        int n = s.length;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                int a = n - i;
                int a1 = n - i - 1;
                long r = (1L << a) - 1;
                long l = (1L << a1) - 1;
                ret += Math.max(Math.min(r, x) - l, 0);
            }
        }
        return ret;
    }
}

ここまで12分26秒＋0ペナ。291位。

B - Range Point Distance

問題
3分くらいで解いている人が何人もいたので、単純に考えることにした。

思考過程

1. 感覚的には、は区間が個ある内の真ん中辺りにしたい。
2. そうすると、はになる。
3. 結局～の間の中央にを指定することになるので、累積、累積を管理しながらを求めればよい。

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 n = Integer.parseInt(br.readLine());
        int[] l = new int[n];
        int[] r = new int[n];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            l[i] = Integer.parseInt(sa[0]);
            r[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        int lmax = 0;
        int rmin = 1000000000;
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            lmax = Math.max(lmax, l[i]);
            rmin = Math.min(rmin, r[i]);
            pw.println(Math.max((lmax - rmin + 1) / 2, 0));
        }
        pw.flush();
    }
}

ここまで18分56秒＋0ペナ。158位。

残り時間はCに1時間、Dに40分ほど使った。
Cは例２を見てという形にしたくなるが、干渉しないようにを定めることができなかった。

1時間経過する頃にはCを通しても旨味はなくなってきていたので、Dを通すことで逆転を狙おうとするが、何もわからず。

最終結果：ABの2完700点、18分56秒、528位、パフォーマンス1590
レート変動：2018→1982（-36）

来週のABC229がついにABC192以来のRatedABCとなってしまった。
（黄色になって以来これまで二度青に落ちているが、二度ともARCorAGCが連続しているところで、間にRatedABCが入る前に黄色復帰していた）

これで果たしてどこまで落ちていくか・・・。