AtCoder Grand Contest 053

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

A - >< again

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

思考過程
  1. kが取り得る値の条件の1つは、Aの隣り合う要素の差の最小値以下であること。
  2. Bの最小の構成は、AGC040-Aと同様に求められる。
  3. k-1回を上記の最小構成にして、残りの1回をAから最小構成\times (k-1)を引いたものにする? →6ケースWA
     
  4. 完全な最小構成ではなく、大きい要素も作らないと、最後の1回が条件を満たさないことがありそう。
  5. 最小構成\times kAを超えないかどうかのチェックも一応追加しておく。(Aを超えない最大値に減らす)
  6. 最初のk-1回をA / kにする? →13ケースWA
     
  7. 駄目なケースが全然わからないので、入力をランダムに生成し、条件を満たさない答えが構成されたらその時の入出力を吐かせるようなプログラムを書いてみる。
  8. 上記5.では、最大k-1回切り捨てられて、最後の1回がその分大きくなりすぎることがあるのが判明。
  9. 最後の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. 何パターンかシミュレーションしてみると、青木君が取るカードは、高橋君が前半から取った場合は中央から1つ後ろへ、後半から取った場合は前へとずれていくような感じ。
  2. 中央2つを見て、左の方が小さければ高橋君が後半から最大値を取るような貪欲・・・はさすがに正当性が感じられない。
  3. 考えやすそうな気がするので、青木君が取るものを最小化する方向で考えていく。
     
  4. そもそも単純に小さい方からN個取ることが可能だったりしないか?
  5. 中央2つの内最低1つは必ず取るのでさすがに無理。
  6. 中央4つの内最低2つは必ず取る。ただし、最も内側の2つを取れば、内側から2番目の2つの内の片方を取るというわけではない。
  7. 結局、中央から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問題は一応それらしい解法(下記)を思いついたので提出までしたが、半分程度しか通らず。

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

 


終結果:ABの2完、95分20秒、217位、パフォーマンス2209
レート変動:1986→2011(+25)


前回のARCで青落ちしたものの、一度で黄色復帰することができ、ABCは193以降Unratedな状態を継続。
今回爆死したらレート変動が富士山のような見た目になりそうとか思っていたりしたが、そうはならず。いいことだけど。

今回は、Aで入力を自動生成することで落ちるケースを探し出す行動ができたのが収穫であり、それに踏み切るまでの遅さも感じたので、今後はもっと安易に提出デバッグに走らないようにしていきたい。
yukicoderとかPASTとか、ペナのコストが安い時はやってしまうけど。