ZONeエナジー プログラミングコンテスト(Unrated)

コンテスト前のレート：2008
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：404位（1500点、71分39秒）


今回は配点が入れ替わってるC問題からとも思ったが、日和ってD問題から。
なおDは7人目にACしているが、FAとは2分以上差がある。
Dの後は基本的に前から順にやった。

A - UFO襲来

問題

思考過程
  1. "ZONe"を空文字に一括置換し、減った文字数\div 4を求める。
import java.util.Scanner;

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

        s = s.replaceAll("ZONe", "");
        System.out.println((12 - s.length()) / 4);
    }
}

DAと解いた時点で6分43秒＋0ペナ。15位。
（Aだけだと1分15秒）


B - 友好の印

問題

思考過程
  1. 二次元平面上で点(D, H)と(d_i, h_i)を通る直線が、Y軸上のどこを通るかをN回求め、その最大値が答え。
  2. 相似形の性質を考えて、求めたい点は(0, H)から、(H-h_i) \times \frac{D}{D-d_i}だけ下にある。
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 d = sc.nextInt();
        int h = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        sc.close();

        double ans = 0;
        for (int i = 0; i < n; i++) {
            double val = (double) (h - y[i]) * d / (d - x[i]);
            ans = Math.max(ans, h - val);
        }
        System.out.println(ans);
    }
}

DABと解いた時点で11分20秒＋0ペナ。83位。



C問題は解けず。
とりあえず答えの二分探索をしたが、二分探索内で判定問題を解くのがO(N^2)だとTLEしてしまった。


D - 宇宙人からのメッセージ

問題

思考過程
  1. 同じ文字が連続したら取り除く処理は、S[i]とStackの先頭が同じかどうかを調べることで行える。
  2. さらに、反転中かどうかを管理しておけば、Stackの操作は、Dequeの前を見るか後ろを見るかに置き換えられる。
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();

        Deque<Character> que = new ArrayDeque<>();
        boolean flg = true;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == 'R') {
                flg = !flg;
            } else if (!que.isEmpty()) {
                // 先頭or末尾の文字を得る
                char c;
                if (flg) {
                    c = que.peekLast();
                } else {
                    c = que.peekFirst();
                }
                // Sのi文字目と比較
                if (c == s[i]) {
                    // 同じなら削除
                    if (flg) {
                        que.pollLast();
                    } else {
                        que.pollFirst();
                    }
                } else {
                    // 異なるなら追加
                    if (flg) {
                        que.addLast(s[i]);
                    } else {
                        que.addFirst(s[i]);
                    }
                }
            } else {
                // Dequeが空なら必ず追加
                if (flg) {
                    que.addLast(s[i]);
                } else {
                    que.addFirst(s[i]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!que.isEmpty()) {
            if (flg) {
                sb.append(que.pollFirst());
            } else {
                sb.append(que.pollLast());
            }
        }
        System.out.println(sb.toString());
    }
}

Dだけ解いた時点で5分28秒＋0ペナ。141位。


E - 潜入

問題
想定解法は知らん。

思考過程
  1. ただのダイクストラをやればいいだけ？
  2. 問題文の3つ目の移動まで実装した後に、4つ目を見てTLEしそうと思ったが、他の解法がすぐには思いつきそうにないのでとりあえずTLE覚悟で投げたら1829msでぎりぎり通ってしまった。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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 r = Integer.parseInt(sa[0]);
        int c = Integer.parseInt(sa[1]);
        int rc = r * c;
        int[][] a = new int[r][c - 1];
        for (int i = 0; i < r; i++) {
            sa = br.readLine().split(" ");
            for (int j = 0; j < c - 1; j++) {
                a[i][j] = Integer.parseInt(sa[j]);
            }
        }
        int[][] b= new int[r - 1][c];
        for (int i = 0; i < r - 1; i++) {
            sa = br.readLine().split(" ");
            for (int j = 0; j < c; j++) {
                b[i][j] = Integer.parseInt(sa[j]);
            }
        }
        br.close();

        int s = 0;
        long[] d = new long[rc];
        Arrays.fill(d, Long.MAX_VALUE);
        d[s] = 0;
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        Node first = new Node(s, 0);
        que.add(first);

        while (!que.isEmpty()) {
            Node cur = que.poll();
            if (cur.d > d[cur.v]) {
                continue;
            }
            int cx = cur.v / c;
            int cy = cur.v % c;
            if (cy < c - 1) {
                long alt = d[cur.v] + a[cx][cy];
                int next = cur.v + 1;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
            }
            if (cy > 0) {
                long alt = d[cur.v] + a[cx][cy - 1];
                int next = cur.v - 1;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
            }
            if (cx < r - 1) {
                long alt = d[cur.v] + b[cx][cy];
                int next = cur.v + c;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
            }
            for (int i = 1; i <= cx; i++) {
                long alt = d[cur.v] + i + 1;
                int next = cur.v - c * i;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
            }
        }
        System.out.println(d[rc - 1]);
    }

    static class Node implements Comparable<Node> {
        int v;
        long d;

        public Node(int v, long d) {
            this.v = v;
            this.d = d;
        }

        public int compareTo(Node o) {
            return Long.compare(d, o.d);
        }
    }
}

ここまで66分50秒＋0ペナ。479位。



F問題は解けず。
25分かけて一度は提出までしたが、31/43しか通らず。
なお、さらに数分考えてその提出が完全に嘘であることはなんとなくわかったが、残り5分ではどうにもできず。



最終結果：ABCEの4完、66分50秒、688位、パフォーマンス1704相当
レート変動：2008（Unrated）


やっぱり自分の適性レートはまだ1700～1800台くらいなんじゃないだろうか。
まあ自分の弱点が次から次へとUnratedのABC級で出てくれるのは助かる。