AtCoder Regular Contest 144

コンテスト前のレート：1987
レート通りのパフォーマンスが得られる順位：403位（1300点、73分12秒）

A - Digit Sum of 2x

問題

思考過程

1. サンプルを見ると基本的にはになりそう。
2. で繰り上がりが発生するととなるので、繰り上がりが発生しない時がとなりこれが最大となる。
   　
3. 繰り上がりが発生しないようにするためには、は～のみから構成される。
4. 合計がに達しない間を並べ続け、最後だけ余りの～にする。
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());
        br.close();

        int m = n * 2;
        System.out.println(m);
        StringBuilder sb = new StringBuilder();
        while (n > 4) {
            sb.append(4);
            n -= 4;
        }
        System.out.print(n);
        System.out.println(sb.toString());
    }
}

ここまで4分13秒＋0ペナ。300位。

B - Gift Tax

問題

思考過程

1. をソートするなりPriorityQueueに入れるなりして、最小要素に、最大要素にを損しなくなるまで（実際は回ずつではなく何倍かして効率的に）行う。というようなことをしたくなるが、かなり大変そう。
2. 答えを決め打ちすれば各要素に何回操作できるかがわかるので、答えの二分探索を行う。
3. が決め打ちした答えより小さい場合は回する必要があり、の場合は回できる。
4. の必要回数がの可能回数以下であればは達成可能。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int ok = 1;
        int ng = 1000000001;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            long x = 0;
            long y = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] < mid) {
                    x += (mid - a[i] + p - 1) / p;
                }
                if (a[i] > mid) {
                    y += (a[i] - mid) / m;
                }
            }
            if (x <= y) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        System.out.println(ok);
    }
}

ここまで10分07秒＋0ペナ。169位。

C - K Derangement

問題

思考過程

1. 中央の要素に設定可能な値がなくなるので、の場合は不可。そうでなければ少なくとも偶数の場合「5 6 7 8 1 2 3 4」、奇数の場合「4 5 6 7 1 2 3」のような並べ方が存在する。
   　
2. の場合は「2 1 4 3 」、の場合は「3 4 1 2 7 8 5 6 」といったように、個ずつ区切って後半個の後に前半個を繋げた並べ方を繰り返すのが基本形になりそう。
3. ただし、個に満たないグループでは上記1.の通り構成不可になってしまうため、最後のグループは個以上個未満となるようにする。
4. 余りを含めたグループは、例２で「4 5 6 7 8 1 2 3」になっているように、「4 5 6 1 2 3」よりは損するので、最初ではなく最後に置く。
   　
5. 最後以外の個ずつのグループは上記2.の通りに並べればよく、最後のグループの並べ方が問題。（以下最終グループの要素を～とする）
6. ～の後～という順にすればよい？　→21/97ケースWA
   　
7. を増やしていくと、「4 5 6 1 8 9 10 2 3 7」、「4 5 6 1 2 9 10 11 3 7 8」、のように数列の番目以降にから何個かを入れる余地が出てくる。
8. あとはこれをどう実装するかだが、最初の個は～で確定として、後続の～を並べていく際、それが～の内未使用のものの中に存在していたら、先に未使用内の最小値を使っていくことにする。

まず～を並べて、その内の先頭個と末尾個は確定、残った部分を未使用値の小さい順に埋めていく。という方がわかりやすかったかも。
「4 5 6 x x 9 10 11 x x x」を作って、xには残った1 2 3 7 8を埋めていく形。

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

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

        int k2 = k * 2;
        if (k2 > n) {
            System.out.println(-1);
            return;
        }

        List<Integer> list = new ArrayList<>();
        int n2 = n;
        while (n2 >= k2) {
            list.add(k2);
            n2 -= k2;
        }
        if (n2 > 0) {
            list.set(list.size() - 1, k2 + n2);
        }

        List<Integer> ans = new ArrayList<>(n);
        int b = 0;
        for (int e : list) {
            int start = b + 1;
            int end = b + e;
            int d = e - k;
            // 例：e=11, k=3だと、setには1, 2, 3, 7, 8が入る
            TreeSet<Integer> set = new TreeSet<>();
            for (int i = start; i <= start + d - 1; i++) {
                if (i < start + k || i >= start + k2) {
                    set.add(i);
                }
            }
            for (int i = start + k; i <= end; i++) {
                if (set.contains(i)) {
                    ans.add(set.pollFirst());
                } else {
                    ans.add(i);
                }
            }
            for (int i : set) {
                ans.add(i);
            }
            b = end;
        }

        StringBuilder sb = new StringBuilder();
        for (int i : ans) {
            sb.append(i).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで35分43秒＋1ペナ。76位。

Dは問題理解に時間がかかり、理解した後もさっぱりだったので、Eの方に残り時間の7割ほどを使っていた。
とりあえずEを実装してみるも、サンプルで駄目なポイントを認識して解決方法がわからず、Dに戻ってもどうすればいいのか何も見当も付かず、残り時間10分ほどの時点で諦め。
Dは結局解説を見てもまともに読む気もしない感じで、やっぱり解ける見込みはなかった。

最終結果：ABCの3完1300点、40分43秒、191位、パフォーマンス2331
レート変動：1987→2026（+39）

青→黄7回目。
なんとかまた黄色に復帰することができたが、青でいる時間の方が長くなってきているので、いつまでもつことやら・・・。