AtCoder Grand Contest 061

コンテスト前のレート：1910
レート通りのパフォーマンスが得られる順位：465位（500点、104分50秒）

A - Long Shuffle

問題

思考過程

1. とりあえず実験する。まで手作業で求めてみたら、ではとなり、規則性がありそう。
2. さすがにこれ以上は手作業だときついので愚直を実装してまで出力してみると、以下のようになった。
   
3. 背景黄はの倍数、背景橙はぱっと目に付いたの箇所。の倍数ではなくべきのところで完全に上記1.のようになるらしい。
   　
4. よく見ると偶数の行は両側から見ていくと合計がになっている。が奇数の時はの行を箇所調べれば求められ、偶数の時はの場合に再帰すればよい？　→WA
5. よく見ると行目の左半分と行目は全然一致していなかった。
   　
6. より小さいに再帰していく考え方はそのままで、どうやったらちゃんと再帰できるかを考える。
7. とりあえず比較的単純な並びになっているがの倍数だけ考えることにし、そうでない場合はへの再帰を最大回行うことにする。
8. の部分に注目すると、図の黒枠部分はの部分と全く同じで、緑枠部分はを引けば全く同じ、赤枠部分はなので、この通りに場合分けして再帰させることにする。
9. 場合分けの条件を何度も書き間違えながらも、図の範囲の結果が愚直と完全に一致したことを確認して提出し、無事AC。

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 t = Integer.parseInt(br.readLine());
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            long n = Long.parseLong(sa[0]);
            long k = Long.parseLong(sa[1]);

            System.out.println(dfs(n, k));
        }
        br.close();
    }

    static long dfs(long n, long k) {
        if (n < k) {
            return k;
        }
        if (n == 2) {
            if (k == 1) {
                return 2;
            } else {
                return 1;
            }
        }

        // nが4の倍数でない場合
        if (n % 4 != 0) {
            if (k == 1) {
                return 2;
            } else {
                long a = dfs(n - 1, k - 1);
                long b = dfs(n - 1, a + 1);
                return b;
            }
        }

        // 以下、nが4の倍数の場合

        // 赤と緑の境目を求める
        long a = 4;
        while (a * 2 <= n) {
            a *= 2;
        }
        // nが2べきの場合
        if (n == a) {
            if (k % 2 == 1) {
                return k + 1;
            } else {
                return k - 1;
            }
        }
        // 緑枠部分の場合
        if (k > a) {
            return a + dfs(n - a, k - a);
        }
        // 赤枠部分の場合
        if (n - a < k) {
            return k;
        }
        // 黒枠部分の場合
        return dfs(n - a, k);
    }
}

ここまで92分57秒＋1ペナ。405位。

その後はB～Dの問題を読んで、Bをやることに決める。
が奇数の場合は構築できたが、偶数がやの場合でも手作業で簡単には作れなかったのでとりあえず一律"No"にしてみたらさすがに駄目。
その後手作業では作れたが、に近いやり方で機械的にを作ることができないまま終了。

最終結果：Aの1完500点、97分57秒、436位、パフォーマンス1956
レート変動：1910→1914（+4）

とりあえず普通の結果にはなったのでまあヨシ。
ちゃんと比較していれば1ペナは防げたのでそれだけはもったいなかった。