AtCoder Grand Contest 053 - ks2mのブログ

A - >< again
- 思考過程
B - Taking the middle
- 思考過程

コンテスト前のレート：1986
レート通りのパフォーマンスが得られる順位：317位（1100点、159分16秒）

A - >< again

問題
下記6.までで40分かけても解けず、先にB問題へ。
Bを15分ほどで解いて、その時点の順位表がC問題10人程度、D問題以降0人だったので、C以降が解ける可能性はまずないとみて、一応Cの問題を読むだけはしたがAに戻ってくる。
均等に分配するということが何故30分かけても出てこなかったのか・・・。

思考過程

$k$ が取り得る値の条件の $1$ つは、 $A$ の隣り合う要素の差の最小値以下であること。
$B$ の最小の構成は、AGC040-Aと同様に求められる。
$k-1$ 回を上記の最小構成にして、残りの $1$ 回を $A$ から最小構成 $\times (k-1)$ を引いたものにする？　→6ケースWA
　
完全な最小構成ではなく、大きい要素も作らないと、最後の $1$ 回が条件を満たさないことがありそう。
最小構成 $\times k$ が $A$ を超えないかどうかのチェックも一応追加しておく。（ $A$ を超えない最大値に減らす）
最初の $k-1$ 回を $A / k$ にする？　→13ケースWA
　
駄目なケースが全然わからないので、入力をランダムに生成し、条件を満たさない答えが構成されたらその時の入出力を吐かせるようなプログラムを書いてみる。
上記5.では、最大 $k-1$ 回切り捨てられて、最後の $1$ 回がその分大きくなりすぎることがあるのが判明。
最後の $1$ 回が他と同じになるまで、残りの $k-1$ 回分のところに $1$ ずつ分配する。

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

        // 7.ランダム入力実験跡（制約満たさない可能性もあるが、確率低そうなので無視）
//      while (true) {
//          int n = (int) (Math.random() * 100 + 1);
//          char[] s = new char[n];
//          int[] a = new int[n + 1];
//          a[0] = (int) (Math.random() * 10001);
//          for (int i = 0; i < n; i++) {
//              if (Math.random() < 0.5) {
//                  s[i] = '<';
//                  a[i + 1] = (int) (Math.random() * (10001 - a[i])) + a[i];
//                  a[i + 1] = Math.max(a[i + 1], a[i] + 1);
//              } else {
//                  s[i] = '>';
//                  a[i + 1] = (int) (Math.random() * a[i]);
//              }
//          }
//          solve(n, s, a);
//      }
    }

    static void solve(int n, char[] s, int[] a) {
        // 2
        int[] b = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (s[i] == '<') {
                b[i + 1] = b[i] + 1;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '>') {
                b[i] = Math.max(b[i], b[i + 1] + 1);
            }
        }

        // 1
        int k = 1000000;
        for (int i = 0; i < n; i++) {
            k = Math.min(k, Math.abs(a[i] - a[i + 1]));
        }
        // 5
        for (int j = 0; j <= n; j++) {
            if (b[j] > 0) {
                k = Math.min(k, a[j] / b[j]);
            }
        }

        // 6
        int[][] c = new int[k][n + 1];
        for (int j = 0; j <= n; j++) {
            c[0][j] = a[j] / k;
        }
        for (int i = 1; i < k - 1; i++) {
            for (int j = 0; j <= n; j++) {
                c[i][j] = c[0][j];
            }
        }
        for (int j = 0; j <= n; j++) {
            c[k - 1][j] = a[j] - c[0][j] * (k - 1);
            // 9
            int x = 0;
            while (c[0][j] < c[k - 1][j]) {
                c[x][j]++;
                c[k - 1][j]--;
                x++;
            }
        }

        // 出力
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(k);
        for (int i = 0; i < k; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j <= n; j++) {
                sb.append(c[i][j]).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            pw.println(sb.toString());
        }
        pw.flush();
    }
}

BAと解いた時点で75分20秒＋4ペナ。186位。

B - Taking the middle

問題
わかってしまえば実装は簡単。

思考過程

何パターンかシミュレーションしてみると、青木君が取るカードは、高橋君が前半から取った場合は中央から $1$ つ後ろへ、後半から取った場合は前へとずれていくような感じ。
中央 $2$ つを見て、左の方が小さければ高橋君が後半から最大値を取るような貪欲・・・はさすがに正当性が感じられない。
考えやすそうな気がするので、青木君が取るものを最小化する方向で考えていく。
　
そもそも単純に小さい方から $N$ 個取ることが可能だったりしないか？
中央 $2$ つの内最低 $1$ つは必ず取るのでさすがに無理。
中央 $4$ つの内最低 $2$ つは必ず取る。ただし、最も内側の $2$ つを取れば、内側から $2$ 番目の $2$ つの内の片方を取るというわけではない。
結局、中央から $2$ つPriorityQueueに追加して最小値を $1$ つ取り出す、ということを繰り返せばよさそう。

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

        long sum = 0;
        for (int i = 0; i < n2; i++) {
            sum += a[i];
        }

        long ao = 0;
        PriorityQueue<Integer> que = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            que.add(a[n - 1 - i]);
            que.add(a[n + i]);
            ao += que.poll();
        }
        System.out.println(sum - ao);
    }
}

Bだけ解いた時点で56分04秒＋0ペナ。193位。

C問題は数分考えて全くできる気がせず。

D問題は一応それらしい解法（下記）を思いついたので提出までしたが、半分程度しか通らず。

$i+1$ 番目の人が $i+1$ 問を $X$ 分で解いていて条件を満たしており、 $i+1$ 問の中で所要時間最小は $Y$ 分とする。
$i$ 番目の人が $(X-Y-2)$ ～ $(X-Y)$ 分で $i$ 問解くことができなければ"No"、できるなら $i$ 問の中での所要時間最小を $Z$ 分として、 $Z$ を引いた後の $i-1$ 問分の時間が最大となる場合を次の $(X-Y)$ として $i-1$ 番目の人へ。