AtCoder Regular Contest 117

コンテスト前のレート:2011
レート通りのパフォーマンスが得られる順位:362位(1200点、62分20秒)

A - God Sequence

問題
実装もっと上手くできなかったものか。と思ったけどそこまで時間かかったわけではなかったらしい。

思考過程
  1. 1A-1-Bを用意して、ABの少ない方の最後の1つで帳尻を合わせる。
  2. 実装は、まず1からmin(A, B)-1まで、正負両方を答えの数列に追加する。
  3. 多い方について、残りを数列に追加しつつ、合計を求める。
  4. 少ない方の最後の要素を、上記3.の合計分とする。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        // 2
        int m = Math.min(a, b) - 1;
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            list.add(i);
            list.add(-i);
        }

        if (a >= b) {
            // 3
            int sum = 0;
            for (int i = m + 1; i <= a; i++) {
                list.add(i);
                sum += i;
            }
            // 4
            list.add(-sum);
        } else {
            // 3
            int sum = 0;
            for (int i = m + 1; i <= b; i++) {
                list.add(-i);
                sum += i;
            }
            // 4
            list.add(sum);
        }

        StringBuilder sb = new StringBuilder();
        for (int i : list) {
            sb.append(i).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで4分11秒+0ペナ。155位。


B - ARC Wrecker

問題

思考過程
  1. ビルの順番は関係ないので、とりあえずソートしてみる。
  2. 例2が2^5のように見え、各階について消すか消さないかの2択で、2^{max(A_i)}ではないかと思ったが、例3が合わない。
  3. 例3であれば、例えば159階から265階の間に注目すれば、消す数が同じであれば、どの階を消しても最終的な景観は同じ。つまり、左記の間で消す数だけが問題。
  4. ソート後の各ビル間について、消す階数は0(A_i-A_{i-1})(A_i-A_{i-1}+1)通りあるので、\prod_{i=1}^N(A_i-A_{i-1}+1)を求める。(A_0=0とする)
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        Arrays.sort(a);
        int mod = 1000000007;
        long ans = 1;
        for (int i = 1; i <= n; i++) {
            int d = a[i] - a[i - 1] + 1;
            ans *= d;
            ans %= mod;
        }
        System.out.println(ans);
    }
}

ここまで11分39秒+0ペナ。244位。


C - Tricolor Pyramid

問題
計30分ほど考えて解けず。
似た問題に覚えがあって、AGC043-Bを見直していたりしたので、各色を数値で置き換えたり、最下段の各要素が寄与する回数が二項係数になるという発想まではあったのに、公式解説の2-1.の表とその結果導出される式だけが出てこなかった。


D - Miracle Tree

問題
定数倍TLE地獄で24分損した。
結局効果があったのは下記12なのか14なのか15なのか、どれも効果がなくてただのジャッジの誤差なのか。

思考過程
  1. まず、一直線のパスグラフを考えてみると、端から順に1, 2, \cdotsと割り当てればよい。
  2. 直径を本線として、それに枝を生やしてみたらどうなるか?
  3. 枝部分に値を書き込んでから本線に戻ったとすると、枝部分の葉に書き込んだ値からも本線までの距離分足した値から続けるしかなさそう。適当にそれまで書き込んだ値を入れ替えたりしてみようとしても、より良い答えは見つからない。
     
  4. 結局、DFSで辺を移動した回数を保持しておきながら、まだ書き込まれていない頂点に来たら、保持している値を書き込むということをする。
  5. ただ、手元で作っていたサンプルでは、DFSで辿る順番を変えると、結果が変わってしまう。
  6. 見たところ、最終的に到達する葉の深さが浅い辺から通っていくのがよさそうであった。(実際は、直径の端点の一方から始めて、もう一方に最後に行きさえすれば、他の順番は関係なかった)
     
  7. 直径の端点の一方を探すためのBFSをする。
  8. 直径の端点の一方を根とした時の各頂点の深さを求め、各辺について、選んだ時の最終到達点の深さがわかるようにしておくための木DPをする。
  9. 上記8.の情報を元に、上記4, 6.の通りのことをする。 →1ケースTLE
     
  10. 計算量は問題ないはずだが、もしかして再帰でDFS2回やっているのが重い?
  11. よく見れば2066msで、本当にギリギリのTLEっぽいので、定数倍改善できそうなところを探す。
  12. 浅い辺から選ぶところで、リスト全体をソートするよりPriorityQueueに入れた方が早いかもと変えてみる。 →2154msになった
     
  13. 何回も提出していればその内通るかもしれないが、無駄にペナ重ねたくもない・・・。
  14. 出力は1回だけど、もしかしたらSystem.outよりPrintWriterの方が早いかもと変えてみる。
  15. 上記7.で、BFS後に最遠の頂点を探すのではなく、BFSのキューに最後に入れられた頂点にすることで、forループを1回減らしてみる。 →1967msでAC
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    static int n, now;
    static List<List<Hen>> list;
    static int[] e;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        n = Integer.parseInt(sa[0]);
        list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            sa = br.readLine().split(" ");
            Hen h = new Hen();
            h.a = Integer.parseInt(sa[0]) - 1;
            h.b = Integer.parseInt(sa[1]) - 1;
            list.get(h.a).add(h);
            list.get(h.b).add(h);
        }
        br.close();

        // 7
        int[] d = new int[n];
        Queue<Integer> que = new ArrayDeque<>();
        que.add(0);
        d[0] = 1;
        int idx = 0;
        while (!que.isEmpty()) {
            int x = que.poll();
            for (Hen h : list.get(x)) {
                int nx = h.a;
                if (nx == x) {
                    nx = h.b;
                }
                if (d[nx] == 0) {
                    d[nx] = d[x] + 1;
                    que.add(nx);
                    idx = nx; // 15:コメント部分の代わり
                }
            }
        }
        // 15
//      int max = 0;
//      for (int i = 0; i < n; i++) {
//          if (d[i] > max) {
//              idx = i;
//              max = d[i];
//          }
//      }

        e = new int[n];
        dfs(idx, -1, 1); // 8
        dfs2(idx, -1); // 9

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

    // 8
    static int dfs(int x, int p, int d) {
        int ret = d;
        for (Hen h : list.get(x)) {
            int nx = h.a;
            if (nx == x) {
                nx = h.b;
            }
            if (nx != p) {
                h.d = dfs(nx, x, d + 1);
                ret = Math.max(ret, h.d);
            }
        }
        return ret;
    }

    // 9
    static void dfs2(int x, int p) {
        // 4
        now++; // 辺を進んだカウント
        if (e[x] == 0) {
            e[x] = now;
        }
        // 12
        List<Hen> ch = list.get(x);
        PriorityQueue<Hen> que = new PriorityQueue<>((o1, o2) -> o1.d - o2.d);
        for (Hen h : ch) {
            que.add(h);
        }

        while (!que.isEmpty()) {
            Hen h = que.poll();
            int nx = h.a;
            if (nx == x) {
                nx = h.b;
            }
            if (nx != p) {
                dfs2(nx, x);
            }
        }
        now++; // 辺を戻ったカウント
    }

    static class Hen {
        int a, b, d;
    }
}

ABDと解いた時点で58分06秒+2ペナ。284位。



Eは数分考えてすぐ諦め。

Fは比較的考えやすそうな見た目をしている気がして特攻してみたが、やはり解けず。
答えの二分探索か、貪欲+αかを考えてみるも上手くいかず。



終結果:ABDの3完1200点、68分06秒、380位、パフォーマンス1987
レート変動:2011→2008(-3)


D問題が一発で通っていれば44分10秒で、297位、パフォ2106だった。
100そこそこの差で済んだならまだマシだったか。

最近どこかでハマって、以下の処理AとBがかなり軽い場合、可能なら

    for (int i = 0; i < n; i++) {
        // 処理A
    }
    for (int i = 0; i < n; i++) {
        // 処理B
    }

とするより、

    for (int i = 0; i < n; i++) {
        // 処理A
        // 処理B
    }

とした方がほぼ半分の実行時間で済む(for文自体もそれなりに重い)らしいことを実験していたりしたので、もしかしたらD問題でそれが功を奏したのかもしれない。

まあちゃんと考察できていれば、ソートする必要もなくてlogを消せたはずなので、そこまでできていなくても通って儲けたくらいに思っておいた方がいいんだろうな・・・。