AtCoder Regular Contest 146

コンテスト前のレート：2017
レート通りのパフォーマンスが得られる順位：361位（800点、40分52秒）

A - Three Cards

問題
問題名までちゃんと見たはずなのに全てのカードを繋げると誤読していた。

思考過程

1. 単純に値の大きい順につ繋げたのでは、の場合ににしたいところがになってしまう。
2. 上記の例では、文字列として大きい順でも同様の結果になり駄目。
3. カードをつ選ぶところまでは、まず桁数が多いことが優先になるので、値の大きい順にでよさそう。
4. つ選んだ後は、全部繋げると思って考えていた時の貪欲でもいいかもしれないが（なおそれは嘘だったと判明）、通りの並べ替えを全部試すのが無難と判断。

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

public class Main {
    static long ans = 0;

    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(" ");
        br.close();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        Arrays.sort(a);

        int[] b = new int[3];
        b[0] = a[n - 3];
        b[1] = a[n - 2];
        b[2] = a[n - 1];
        permutation(b, 0, 0, new int[3]);

        System.out.println(ans);
    }

    static void permutation(int[] org, int used, int idx, int[] wk) {
        if (idx == org.length) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 3; i++) {
                sb.append(wk[i]);
            }
            ans = Math.max(ans, Long.parseLong(sb.toString()));
            return;
        }

        for (int i = 0; i < org.length; i++) {
            if ((used >> i & 1) == 0) {
                wk[idx] = org[i];
                permutation(org, used | 1 << i, idx + 1, wk);
            }
        }
    }
}

ここまで13分34秒＋0ペナ。846位。

B - Plus and AND

問題
下記2.までは20分くらいでわかったが、それ以降でひたすら迷走した。（6.まではそこまで時間かかっていないが、7.がなかなかわからなかった）
一時Cも実装してみてからそれでは駄目だったとなって戻って来たりしていた。

思考過程

1. 最上位の桁のみにした数を作る場合、最も操作回数が少なく済む個の操作回数合計が以下であり、番目の桁のみにした数についても条件を満たすとして、同じ個で満たせるのかどうかがわからない。
2. それならばについて満たすかどうかを調べ、駄目なら上位桁はであるとして桁目を調べる。ということを繰り返せばできそう。
   　
3. 各について、現時点の答えでになっている桁が全てになるようになるまで最低いくつ加算する必要があるかを求めたいが、が大きい場合が厄介。
4. まずとの共通部分(AND)を求め（下記コード中のv1）、それぞれから引く（v2とe1）。
5. この時点でv2がならば手。
6. e1について、v2以下になるまで上位の桁を落としたい。
7. これは、v2より桁少ない全桁の数（f）とANDを取るマスク処理をすれば求められる。

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

public class Main {
    static long ans = 0;

    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]);
        int k = 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 ans = 0;
        for (int i = 30; i >= 0; i--) {
            // 2
            int b = ans + (1 << i);
            PriorityQueue<Integer> que = new PriorityQueue<>();
            for (int e : a) {
                // 4
                int v1 = b & e;
                int v2 = b - v1;
                // 5
                if (v2 == 0) {
                    que.add(0);
                    continue;
                }
                // 4
                int e1 = e - v1;
                // 7
                long f = Integer.highestOneBit(v2) - 1;
                long e2 = e1 & f;

                int val = (int) (v2 - e2);
                que.add(val);
            }
            // 2
            long sum = 0;
            for (int j = 0; j < k; j++) {
                sum += que.poll();
            }
            if (sum <= m) {
                ans = b;
            }
        }
        System.out.println(ans);
    }
}

ここまで98分13秒＋5ペナ。920位。

Cは余事象を数えることは当然考えたが、それが数えられず。

残り15分ほどでDについて適当解法を投げてみようとする。
最初全ての状態から条件を満たすように上げていくのを周させるまではやってみたがさすがにWA。

それを更新されなくなるまで繰り返すだけでACしたら嫌だなと思って終了後に試してみたが、それらしく並べ替えたり可能性がある条件のみを次ループに残したりしてもTLEが取れず。

最終結果：ABの2完800点、123分13秒、962位、パフォーマンス1432
レート変動：2017→1970（-47）

先週のAGCと合わせて-82でまた青から出直し。
黄色になって以来の最低レートが1961なのだが、そろそろ明日のABCで最低レート更新するのではないだろうか・・・。