大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

コンテスト前のレート：2017
レート通りのパフォーマンスが得られる順位：399位（1500点、44分26秒）

A - Larger Score

問題

思考過程

1. となるとを選んで入れ替えることが、回の操作でできる。
2. の最小値は、各に対して条件を満たす最小のを高速に求めてminを取っていくことを考える。
   　
3. 事前に番目以降の要素をMap＜A_j、j＞の形で持っておくと、のhigherKeyを探すことで、の場合にを得るということができるようになる。
4. なお、が増えればも増える単調増加になるような要素のみを格納するようにすることで、となる最小のを探せば最小のが得られることになる。

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

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

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = k; i < n; i++) {
            Integer x = map.ceilingKey(a[i]);
            if (x == null) {
                map.put(a[i], i);
            }
        }

        int ans = n;
        for (int i = 0; i < k; i++) {
            Integer x = map.higherKey(a[i]);
            if (x != null) {
                ans = Math.min(ans, map.get(x) - i);
            }
        }
        if (ans == n) {
            ans = -1;
        }
        System.out.println(ans);
    }
}

ここまで7分33秒＋0ペナ。153位。

B - 01 Generation

問題
下記思考過程3.の判定を後回しにしていたら忘れて1回RE。

思考過程

1. 書き出して数列の変化を観察してみると、まず先頭は必ず。
2. また、初めて同じ値が連続する箇所以降は操作Bによって追加された要素でしかあり得ない。
3. そのような箇所がなく、全体が交互になっている場合は操作Aのみで達成できる。
4. 後ろの方の操作Bによって追加された部分の値の変化回数が、前の方の操作Aで追加された部分の値の変化回数を上回っている場合は不可能で、逆にそうでなければ可能。

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

        // 先頭が1
        if (a[0] == 1) {
            System.out.println("No");
            return;
        }

        // 初めて同じ値が連続する箇所
        int f = -1;
        for (int i = 1; i < n; i++) {
            if (a[i - 1] == a[i]) {
                f = i - 1;
                break;
            }
        }
        // 全体が0,1交互の場合
        if (f == -1) {
            System.out.println("Yes");
            return;
        }

        // 操作A範囲の値変化回数
        int l = 0;
        for (int i = f - 1; i >= 0; i--) {
            if (a[i] != a[i + 1]) {
                l++;
            }
        }
        // 操作B範囲の値変化回数
        int r = 0;
        for (int i = f; i < n - 1; i++) {
            if (a[i] != a[i + 1]) {
                r++;
            }
        }

        if (l >= r) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで21分44秒＋1ペナ。265位。

C - Rotate and Play Game

問題

思考過程

1. スコアとして常に大きい方から半分の合計を得ることが達成可能かどうかを考えてみる。
2. 大きい方から半分以内に該当する要素を、それ以外をに変更し、さらにそれを周分並べ、その内連続した個を選ぶということにして観察する。
3. の並びが偏っている時はが多い部分から始めればOKだし、交互の場合も問題ないので、始点を適切に選べば常に達成はできそう。
4. の個数の累積和を取って、indexの切り上げを引いてより大きくなる箇所がなければ達成可能。
   　
5. あとは始点を全探索できればいいのだが、単純にやればになってしまうところをなんとか差分計算等で計算量を落とせないものか。
6. 累積和配列については、番目から始めたい場合はを引けばよい。
7. indexの切り上げを引く部分については、ひとまず奇数番目スタートのみ調べていくとすれば、毎回ずつ引く値を減らしていけば帳尻が合う。
8. 上記6, 7の差分を長さの区間全体に適用した上で、より大きくなる箇所があるかどうかを調べたいが、これはセグ木で区間最大値を取得してから差分を考慮すればよいことになる。
9. 交互でも交互でも達成可能であることから、奇数番目スタートのみ調べただけでも十分そうなので、偶数番目スタートまでは実装せずに提出。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

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

        // aの降順
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o2.a - o1.a);
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i + 1;
            o.a = a[i];
            que.add(o);
        }

        int n1 = n / 2;
        int n2 = n * 2;
        Integer[] b = new Integer[n2 + 1];
        Arrays.fill(b, 0);
        long s = 0;
        // 大きい方から半分を処理
        for (int i = 0; i < n1; i++) {
            Obj o = que.poll();
            b[o.i]++;
            b[o.i + n]++;
            s += o.a;
        }

        // b：累積和から要素数÷2の切り上げを引いた値
        // c：累積和のbk
        for (int i = 1; i <= n2; i++) {
            b[i] += b[i - 1];
        }
        int[] c = new int[n2 + 1];
        for (int i = 1; i <= n2; i++) {
            c[i] = b[i];
            b[i] -= (i + 1) / 2;
        }
        // bを元にセグ木を作成
        SegTree<Integer> st = new SegTree<>(b, 0, (v1, v2) -> Math.max(v1, v2));

        int d1 = 0; // 思考過程6の差分調整用
        int d2 = 0; // 思考過程7の差分調整用
        for (int i = 1; i < n; i += 2) {
            d1 = c[i - 1];
            if (st.prod(i, i + n) - d1 + d2 <= 0) {
                System.out.println((i - 1) + " " + s); // -1が漏れて1回WA
                return;
            }
            d2++;
        }
        // 万が一ここでREになるようなら偶数番目スタートも実装する予定だった
        throw new RuntimeException();
    }

    static class Obj {
        int i, a;
    }
}

// 以下ACLを移植したSegTree

提出
ここまで69分47秒＋2ペナ。417位。

Dは問題名を見てAGC031-Cを見に行ったりもしていて、多少のヒントは得られた気がしたが詰め切れず。
一応と偶数が不可というところまではたどり着けていた程度。

時間いっぱいDFSする犯罪も考えて、実際それもやりかけたのだが、各値からの遷移先が通りあり、実際に辺を張るとそれだけでTLEになりそうな量であることから、諦めてしまっていた。
適当にランダムで遷移するようにすればよかったのだが・・・。

最終結果：ABCの3完1500点、79分47秒、555位、パフォーマンス1837
レート変動：2017→2000（-17）

ぎりぎり黄色に留まったのが良かったのか悪かったのか。
ARCも今回で4連敗だが、ABCはそれ以上にずっと負けっぱなしなので、青落ちしたら今度こそ当分黄色に戻ってこれないと思うし、仕事が忙しい状況が続いていて精進する気も全く起こらなくなっているので、もうしばらくはぬるま湯に浸かっていたい感じ。
なおUnrated参加をするつもりは基本的にない。