AtCoder Regular Contest 139

コンテスト前のレート：2000
レート通りのパフォーマンスが得られる順位：293位（800点、65分48秒）

A - Trailing Zeros

問題

思考過程

1. としてあり得る最小値以外をあえて選んで得することはないので、条件を満たす最小値を求める処理を回行う。
2. まず、がより小さいならば、はでよい。（この場合分けは多分いらなかった）
   　
3. それ以外の場合は、まずより下の位を全部にする。
4. の位がの場合は、に変えればOK。
5. の位がの場合は、を足す。

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

        long a = 0;
        for (int i = 0; i < n; i++) {
            long b = 1L << t[i];
            if (b > a) {
                a = b;
            } else {
                long x = a;
                for (int j = 0; j < t[i]; j++) {
                    if ((x >> j & 1) == 1) {
                        x -= 1L << j;
                    }
                }
                if ((x >> t[i] & 1) == 0) {
                    x += 1L << t[i];
                } else {
                    x += 1L << t[i] + 1;
                }
                a = x;
            }
        }
        System.out.println(a);
    }
}

ここまで9分42秒＋0ペナ。326位。

Bは公式解説と似たような全探索の方針までは考えていたが、探索範囲がおかしかったらしい。
開始1時間経過しても解けなかった辺りで飛ばしてCへ。

C - One Three Nine

問題

思考過程

1. 、として、～を全部作れそうな方法を考える。
2. 基本的に(1, 1～3), (2, 1～4), (3, 2～5), (4, 3～6), ・・・の形でだいたい作れそうだが10ケース前後は通らない。
3. 提出デバッグを繰り返した結果、のケースのみ上手くいっていないことを突き止める。
4. では必ず個は作れないかと思いきや、(5, 5)では(5, 3)を加えて帳尻合わせができたりする。
   　
5. 帳尻合わせの実装をしている辺りで時間切れ。
6. あと10分くらい、(8, 8)くらいまで確認している時間があれば偶数という条件も推測ができて、通せたかもしれなかった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

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 m = Integer.parseInt(sa[1]);
        br.close();

        int x = Math.min(n, m);
        int y = Math.max(n, m);
        List<Integer> lx = new ArrayList<>();
        List<Integer> ly = new ArrayList<>();
        for (int i = 1; i < x; i++) {
            int end = Math.min(i + 2, y);
            for (int j = Math.max(i - 1, 1); j <= end; j++) {
                lx.add(i);
                ly.add(j);
            }
        }
        for (int j = Math.max(x - 1, 1); j <= y; j++) {
            lx.add(x);
            ly.add(j);
        }

        if (x == y && x % 2 == 1 && x > 1) {
            lx.add(x);
            ly.add(y - 2);
            int val = x + (y - 2) * 3;
            for (int i = lx.size() - 2; i >= 0; i--) {
                if (lx.get(i) + ly.get(i) * 3 == val) {
                    lx.set(i, lx.get(i) + 1);
                    ly.set(i, ly.get(i + 1) - 1);
                    val = lx.get(i) + ly.get(i) * 3;
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        pw.println(lx.size());
        if (n > m) {
            List<Integer> tmp = lx;
            lx = ly;
            ly = tmp;
        }
        for (int i = 0; i < lx.size(); i++) {
            pw.println(lx.get(i) + " " + ly.get(i));
        }
        pw.flush();
    }
}

最終結果：Aの1完300点、9分42秒、628位、パフォーマンス1527
レート変動：2000→1961（-39）

黄色になって以来4回目の青落ち。
これまでの3回はすぐに黄色復帰できていたが、最近の成績からすると、次のAGC057で大当たりしない限り、今度はもう数ヶ月単位で戻れない可能性の方が高い気がする。