AtCoder Grand Contest 059 - ks2mのブログ

A - My Last ABC Problem
- 思考過程
B - Arrange Your Balls
- 思考過程

コンテスト前のレート：2020
レート通りのパフォーマンスが得られる順位：380位（700点、100分40秒）

A - My Last ABC Problem

思考過程

とりあえず"ABCABCABC"に対して色々操作を試してみる。
置き換える範囲の取り方によって、隣接する文字が異なる箇所が $1$ 箇所減らせたり $2$ 箇所減らせたりする。
同じ $2$ 種類の文字が隣接している箇所（例えば"AB"と"AB"や、"AB"と"BA"）を操作範囲の境界に選んだ場合は、その $2$ 種類を入れ替えることによって $2$ 箇所減らせる。（例えば右記の中央 $3$ 文字を操作して、"ABCAB"→"AACBB"）
それ以外の場合はおそらく $1$ 箇所しか減らせなさそう？
　
"AB"or"BA"、"BC"or"CB"、"AC"or"CA"が現れる箇所の個数について累積和を求めておく。
各クエリの区間について、それぞれの個数 $\div 2$ と $\% 2$ を足す。
それだけだとサンプルの $4$ ケース目が $3$ になってしまうので、最初と最後の文字が同じ場合は $-1$ すればよい？　→サンプル以外全部WA
　
$3$ 種類とも奇数個なら余り分を $+3$ ではなく $+2$ にすればよい？　→上記7.と変わらないような気もするが、一応提出してみたらよくわからないけどACになったのでヨシ

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

        int[] ab = new int[n];
        int[] bc = new int[n];
        int[] ca = new int[n];
        for (int i = 1; i < n; i++) {
            if (s[i - 1] == 'A' && s[i] == 'B' ||
                    s[i - 1] == 'B' && s[i] == 'A') {
                ab[i]++;
            }
            if (s[i - 1] == 'C' && s[i] == 'B' ||
                    s[i - 1] == 'B' && s[i] == 'C') {
                bc[i]++;
            }
            if (s[i - 1] == 'A' && s[i] == 'C' ||
                    s[i - 1] == 'C' && s[i] == 'A') {
                ca[i]++;
            }
            ab[i] += ab[i - 1];
            bc[i] += bc[i - 1];
            ca[i] += ca[i - 1];
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            int cab = ab[r[i]] - ab[l[i]];
            int cbc = bc[r[i]] - bc[l[i]];
            int cca = ca[r[i]] - ca[l[i]];
            int v1 = cab / 2 + cbc / 2 + cca / 2;
            int v2 = cab % 2 + cbc % 2 + cca % 2;
            if (v2 == 3) {
                v2--;
            }
            pw.println(v1 + v2);
        }
        pw.flush();
    }
}

ここまで47分22秒＋1ペナ。168位。

B - Arrange Your Balls

問題
色が $k$ 種類あるとして、ソートすればペアを $k$ 個にできることにも気付いていなかった。
各色が $2$ 種類と隣接するから $2k$ になると勘違いしていた。

思考過程

都合よく多数含まれている色が存在する場合は、 $\{1, 2, 1, 3, 1, 4, 1, 5\}$ のように $1$ 色で他を挟めば、挟まれる色は $1$ 色としか隣接しないので最適だと思われる。
値が小さいものほど個数が多く、英字は $1$ 個しかない色だとして、 $1$ だけでは挟み切れない場合は、 $\{1, a, 1, b, \cdots, 1, 2, c, \cdots, 2, 3, d, \cdots, 3\}$ のようにする？　→6/52しか通らず
　
もう一度最初から、最も多い色をベースとしてその間に他の色を入れていくことを考える。
$1$ 個しかない色についてはやっぱりなるべく同色 $2$ つに挟まれたい。無理な場合は最後にまとめて並べる。
$2$ 個しかない色については、 $\{1, 2, 3, 4, \cdots, 4, 3, 2, 1, 1, 1, \cdots\}$ のように特定の区間にまとめて使うと、より内側の色にとってはあってもなくても変わらない。
上記で $2$ や $3$ が $3$ 個以上あるとすると、 $\{1, 2, 3, 4, \cdots, 4, 3, a, 3, 2, b, 2, c, 2, 1, 1, 1, \cdots\}$ のようにすると、 $2$ 個の場合と比べて損せず、 $a, b, c$ の辺りに $1$ 個しかない色を挟む余地を増やせる分得する形になっている。　ある色が $v$ 個あるとすると、 $v-2$ 個分新たに挟める箇所が増える。
挟める箇所が余っている場合は、 $2$ 個の色や $3$ 個の色も $1$ 個扱いのグループに移す。その方が隣接を $2$ 色から $1$ 色に減らせるので。
　
サンプルを試すとそもそも数字が $N$ 個出力されなかったりしている。
$1$ 個扱いグループに移したものを $1$ 回だけでなく個数分出力する。
$3$ 個以上ある色が $1$ 色もない場合、実装が悪くベース色の処理を通らなくて破綻しているので $2$ 個のグループから $1$ つ $3$ 個以上扱いのグループに移す。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

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());
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            int n = Integer.parseInt(br.readLine());
            String[] sa = br.readLine().split(" ");
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                int c = Integer.parseInt(sa[i]);
                map.put(c, map.getOrDefault(c, 0) + 1);
            }

            Queue<Obj> que1 = new ArrayDeque<>();
            Queue<Obj> que2 = new ArrayDeque<>();
            PriorityQueue<Obj> que3 = new PriorityQueue<>((o1, o2) -> o1.v - o2.v);
            int cnt = 2; // 挟める箇所数（最も多い色は-2する必要ないことを考慮）
            for (int k : map.keySet()) {
                Obj o = new Obj();
                o.c = k;
                o.v = map.get(k);
                if (o.v == 1) {
                    que1.add(o);
                } else if (o.v == 2) {
                    que2.add(o);
                } else {
                    que3.add(o);
                    cnt += o.v - 2;
                }
            }
            cnt -= que1.size();

            // 10. 3個以上が1色もない場合
            if (!que2.isEmpty() && que3.isEmpty()) {
                que3.add(que2.poll());
            }

            // 7. 余裕がある場合は1個扱いに移す
            while (cnt > 0 && !que2.isEmpty()) {
                que1.add(que2.poll());
                cnt--;
            }
            while (cnt > 0 && !que3.isEmpty()) {
                Obj o = que3.peek();
                cnt -= o.v - 1;
                if (cnt >= 0) {
                    que1.add(que3.poll());
                }
            }

            List<Integer> list = new ArrayList<>();
            dfs(list, 0, que1, que2, que3);

            // 4. 挟めなかった余りはまとめて最後に
            while (!que1.isEmpty()) {
                Obj o1 = que1.poll();
                while (o1.v > 0) {
                    list.add(o1.c);
                    o1.v--;
                }
            }

            StringBuilder sb = new StringBuilder();
            for (int i : list) {
                sb.append(i).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            pw.println(sb.toString());
        }
        pw.flush();
        br.close();
    }

    static void dfs(List<Integer> list, int end,
            Queue<Obj> que1, Queue<Obj> que2, Queue<Obj> que3) {
        if (!que3.isEmpty()) {
            // 6
            Obj o = que3.poll();
            list.add(o.c);
            o.v--;
            dfs(list, 1, que1, que2, que3);

            // 2個目以降は間に1個グループのものを挟む
            while (o.v > end) {
                list.add(o.c);
                o.v--;
                if (!que1.isEmpty()) {
                    Obj o1 = que1.poll();
                    while (o1.v > 0) {
                        list.add(o1.c);
                        o1.v--;
                    }
                }
            }
            // ベース色以外の場合
            if (o.v > 0) {
                list.add(o.c);
                o.v--;
            }

        } else if (!que2.isEmpty()) {
            // 5. {1, 2, 3, 4, 3, 2, 1}の形
            Obj o = que2.poll();
            list.add(o.c);
            dfs(list, 1, que1, que2, que3);
            list.add(o.c);

        } else if (!que1.isEmpty()) {
            // 4. 呼び出し元で同色2つに挟まれる
            Obj o1 = que1.poll();
            while (o1.v > 0) {
                list.add(o1.c);
                o1.v--;
            }
        }
    }

    static class Obj {
        int c, v;
    }
}

ここまで121分47秒＋4ペナ。177位。

残り時間はCに20分、Dに30分ほど使い、残り10分切った辺りで諦めといったところ。
どちらも必要条件をいくつか挙げることはできるが詰め切るのは難しそうくらいからあまり進まず。

最終結果：ABの2完1200点、141分47秒、215位、パフォーマンス2346
レート変動：2020→2057（+37）

レート推移のグラフはどう見ても緩やかに落ちていっているのだが、次のAGCでも勝てれば、なんとか年間Highestまで復帰できる可能性も出てきた。
（Highestは昨年6月時点の2129、2022年内では1月時点の2074）

ところで、ABC、ARC、AGCについてはおそらく2年以上欠かさずにこういった記事を書いてきましたが、コンテスト参加以外無精進になって1年ほど経つくらいにはモチベも低下してきており、読者も少ない中これ以上執筆に時間を費やし続けることにあまり意味を見出せなくなってきたので、ひとまず書くものを絞っていこうと思います。

具体的には、まずはABCについて書くのをやめます。既に昨日のABC280からストップしています。
ARCとAGCについては、思考過程を残しておくことに多少の意味はあると思うので、まだ当面は継続予定。ただそれも細かく書けば時間がかかり過ぎるし、雑になれば過程にならなくなるしでどれだけバランス取って続けていられるかわかりませんが。
AHCはおおよそ50位以内に入れた場合に気が向けば。