大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）

A - Gold and Silver
- 思考過程
B - Balls of Three Colors
- 思考過程
C - Max Dot
- 思考過程

コンテスト前のレート：2005
レート通りのパフォーマンスが得られる順位：336位（1400点、99分47秒）

A - Gold and Silver

問題
思考過程1.の操作の繰り返しだけで本当によいのか不安で仕方なかったが、通ったのでヨシ。

思考過程

数列内の単調減少が続く部分の最初で銀に変えて、最後で金に戻したい。
実装は、単調減少が始まったインデックスを保持しておき、増加に転じたところで、単調減少列の長さが $2$ 以上ならば上記1.を実行する。
最後が増加せず終わっていたら処理されない作りになっていたので、最後を別途処理する。

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());
        String[] 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[] v = new int[n];
        int p = 0; // 単調減少の開始位置
        for (int i = 1; i < n; i++) {
            if (a[i - 1] < a[i]) {
                if (i > p + 1) {
                    // 1
                    v[p] = 1;
                    v[i - 1] = 1;
                }
                p = i;
            }
        }
        // 3
        if (n - 1 > p) {
            v[p] = 1;
            v[n - 1] = 1;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(v[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで9分35秒＋0ペナ。135位。

B - Balls of Three Colors

問題

思考過程

例えば赤を残す場合、緑と青を同数にできる必要がある。
残す色を変えて3通り試し、その内最良のものを答えればよいので、以下赤を残す場合を考える。
　
操作を行った時の各色の数の変化を調べると、 $-1, -1, +2$ となっており、緑と青の差は $3$ ずつしか縮まらない。
よって、まず差が $3$ の倍数でない場合は不可能。
　
操作の回数は、差を縮める操作を行った後の $($ 緑の数 $+$ 青の数 $) \div 2$ 。
差を縮める操作は、差 $\div 3$ 回。
差を縮める操作を $1$ 回行うごとに、緑 $+$ 青が $1$ ずつ増えていく。
以上を総合すると、答えは $($ 元の緑の数 $+$ 青の数 $+$ 差を縮める操作回数 $) \div 2 +$ 差を縮める操作回数。

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 t = Integer.parseInt(br.readLine());
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            int r = Integer.parseInt(sa[0]);
            int g = Integer.parseInt(sa[1]);
            int b = Integer.parseInt(sa[2]);

            long ans = Long.MAX_VALUE;
            ans = Math.min(ans, calc(r, g, b));
            ans = Math.min(ans, calc(g, b, r));
            ans = Math.min(ans, calc(b, r, g));
            if (ans == Long.MAX_VALUE) {
                ans = -1;
            }
            System.out.println(ans);
        }
        br.close();
    }

    static long calc(int a, int b, int c) {
        int d = Math.abs(b - c);
        if (d % 3 == 0) {
            long v1 = b + c;
            long v2 = d / 3; // 差を縮める操作回数
            long v3 = v1 + v2; // 差を縮める操作後の緑＋青
            long val = v3 / 2 + v2;
            return val;
        } else {
            return Long.MAX_VALUE;
        }
    }
}

ここまで23分07秒＋0ペナ。91位。

C - Max Dot

問題

思考過程

$A_i$ が大きいほど $x_i$ を大きくしたいので、 $A_i$ の大きい順に処理していけばよい？と思ったりもするが、最大値の後ろが $1$ ばかりで、前が次点ばかりのような場合は、最大値以降の各 $x_i$ を $S \div ($ 最大値から末尾までの要素数 $)$ ずつにするより、もう少し前まで振り分けた方が得しそう。
　
結局まずは、末尾から各要素までの平均を求めて、平均が最大となる箇所から末尾まで、 $S \div$ 要素数（と $M$ の $min$ ）ずつ振り分ける。
余りが出たら、前回の処理で平均が最大となった箇所の前までで、前回までの余りを新しい $S$ として、同様の問題を解く。

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

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 m = Integer.parseInt(sa[1]);
        int s = 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();

        double[] d = new double[n];
        double rem = s; // 前回操作の余り
        int idx = n; // 前回操作で平均が最大となった箇所
        while (idx > 0) {
            PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> Double.compare(o2.avg, o1.avg));
            long[] sum = new long[idx + 1];
            int cnt = 0;
            for (int i = idx - 1; i >= 0; i--) {
                sum[i] = sum[i + 1] + a[i];
                Obj o = new Obj();
                o.i = i;
                cnt++;
                o.avg = (double) sum[i] / cnt;
                que.add(o);
            }

            Obj o = que.poll();
            int c1 = idx - o.i;
            double d1 = Math.min(m, (double) rem / c1);
            for (int i = o.i; i < idx; i++) {
                d[i] = d1;
            }
            rem -= d1 * c1;
            idx = o.i;
        }

        double ans = 0;
        for (int i = 0; i < n; i++) {
            ans += d[i] * a[i];
        }
        System.out.println(ans);
    }

    static class Obj {
        int i;
        double avg;
    }
}

ここまで66分14秒＋0ペナ。126位。

残り時間はだいたいDとEに半分ずつ使ったがどちらも解けず。

Dは、 $A_x \neq A_y$ かつ $A_y \neq A_z$ の条件がなければ、両端以外を残す残さないが自由に選べて、 $2^{N-2}$ 通りになりそうで、そこから不可能なケースを引いていけないかと思ったが、その数え方はよくわからず。
一応、同じ値が連続したところが壁になるので、壁ごとに小分けして最後に総積を取ればよさそうくらいまではわかったが。