AtCoder Grand Contest 059

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

A - My Last ABC Problem

問題

思考過程
  1. とりあえず"ABCABCABC"に対して色々操作を試してみる。
  2. 置き換える範囲の取り方によって、隣接する文字が異なる箇所が1箇所減らせたり2箇所減らせたりする。
  3. 同じ2種類の文字が隣接している箇所(例えば"AB"と"AB"や、"AB"と"BA")を操作範囲の境界に選んだ場合は、その2種類を入れ替えることによって2箇所減らせる。(例えば右記の中央3文字を操作して、"ABCAB"→"AACBB")
  4. それ以外の場合はおそらく1箇所しか減らせなさそう?
     
  5. "AB"or"BA"、"BC"or"CB"、"AC"or"CA"が現れる箇所の個数について累積和を求めておく。
  6. 各クエリの区間について、それぞれの個数\div 2\% 2を足す。
  7. それだけだとサンプルの4ケース目が3になってしまうので、最初と最後の文字が同じ場合は-1すればよい? →サンプル以外全部WA
     
  8. 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. 都合よく多数含まれている色が存在する場合は、\{1, 2, 1, 3, 1, 4, 1, 5\}のように1色で他を挟めば、挟まれる色は1色としか隣接しないので最適だと思われる。
  2. 値が小さいものほど個数が多く、英字は1個しかない色だとして、1だけでは挟み切れない場合は、\{1, a, 1, b, \cdots, 1, 2, c, \cdots, 2, 3, d, \cdots, 3\}のようにする? →6/52しか通らず
     
  3. もう一度最初から、最も多い色をベースとしてその間に他の色を入れていくことを考える。
  4. 1個しかない色についてはやっぱりなるべく同色2つに挟まれたい。無理な場合は最後にまとめて並べる。
  5. 2個しかない色については、\{1, 2, 3, 4, \cdots, 4, 3, 2, 1, 1, 1, \cdots\}のように特定の区間にまとめて使うと、より内側の色にとってはあってもなくても変わらない。
  6. 上記で233個以上あるとすると、\{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個分新たに挟める箇所が増える。
  7. 挟める箇所が余っている場合は、2個の色や3個の色も1個扱いのグループに移す。その方が隣接を2色から1色に減らせるので。
     
  8. サンプルを試すとそもそも数字がN個出力されなかったりしている。
  9. 1個扱いグループに移したものを1回だけでなく個数分出力する。
  10. 3個以上ある色が1色もない場合、実装が悪くベース色の処理を通らなくて破綻しているので2個のグループから13個以上扱いのグループに移す。
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位以内に入れた場合に気が向けば。