AtCoder Beginner Contest 184

コンテスト前のレート：1693
レート通りのパフォーマンスが得られる順位：687位（2100点、144分13秒）

A - Determinant

問題

思考過程

1. 問題文の通り、を出力する。

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();
        int c = sc.nextInt();
        int d = sc.nextInt();
        sc.close();

        System.out.println(a * d - b * c);
    }
}

ここまで0分37秒＋0ペナ。385位。

B - Quizzes

問題

思考過程

1. から始めてシミュレーションする。
2. 'x'の時は、マイナスにはならないということなので、の場合のみ減らす。

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 x = sc.nextInt();
        char[] s = sc.next().toCharArray();
        sc.close();

        for (int i = 0; i < n; i++) {
            if (s[i] == 'o') {
                x++;
            } else {
                if (x > 0) {
                    x--;
                }
            }
        }
        System.out.println(x);
    }
}

ここまで1分53秒＋0ペナ。174位。

C - Super Ryuma

問題
一目見てなんか大変そうだった。実際数分ではできそうになく、先にDをやりかけたが、Dもすぐにできる自信がなかったので、結局順番通りにやった。

思考過程

1. ひらがなの「く」の字のように移動すれば、どんなマスにも手で少なくとも隣にはたどり着けるので、最長でも手。
2. 少ない手数でたどり着けるケースから潰していって、残ったケースを手とする方針でいく。
   　
3. 同一マスの場合、手。
4. 問題文に書いてある式を満たす場合、手。
5. 手以上のケースは、まず差の絶対値を取ることで、から右上に行く場合のみを考えればよいようにする。
6. 手で行けるマスは、手で行けるマスから見て問題文の式を満たすマス。
   手で行けるマスは、近場では～のマスととなので、これら全てで式を満たすか試す。
7. 上記6で拾えない遠いマス（手目がよりも遠い斜めマスの場合）は、斜め移動のみで行けるマス全てが手で行けるマス。
8. ここまでで、手のケースを挙げ尽くしたので、残りは手。

import java.util.Scanner;

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

        // 思考過程3. 同一マス
        if (r1 == r2 && c1 == c2) {
            System.out.println(0);
            return;
        }
        // 思考過程4. 式を満たすマス
        if (r1 + c1 == r2 + c2 || r1 - c1 == r2 - c2 ||
                Math.abs(r1 - r2) + Math.abs(c1 - c2) <= 3) {
            System.out.println(1);
            return;
        }

        // 思考過程5. 右上のみ見る
        int dx = Math.abs(r1 - r2);
        int dy = Math.abs(c1 - c2);
        // 思考過程6. 1手で行けるマスから見て条件を満たすマス
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i + j == dx + dy || i - j == dx - dy ||
                        Math.abs(i - dx) + Math.abs(j - dy) <= 3) {
                    System.out.println(2);
                    return;
                }
            }
        }
        if (0 + 3 == dx + dy || 0 - 3 == dx - dy ||
                Math.abs(0 - dx) + Math.abs(3 - dy) <= 3) {
            System.out.println(2);
            return;
        }
        if (3 + 0 == dx + dy || 3 - 0 == dx - dy ||
                Math.abs(3 - dx) + Math.abs(0 - dy) <= 3) {
            System.out.println(2);
            return;
        }
        // 思考過程7. 斜め移動のみで行けるマス
        if ((dx + dy) % 2 == 0) {
            System.out.println(2);
            return;
        }
        // 思考過程8. その他
        System.out.println(3);
    }
}

ここまで17分32秒＋0ペナ。604位。

D - increment of coins

問題
こういう確率とか期待値が絡んだDPはなかなか自信が持てない。
一応EDPCなどで類題を見ているので、それらしくやってみる。

思考過程

1. 「：金貨枚、銀貨枚、銅貨枚の時の答え」を定義する。
2. は、
   金貨を選ぶ確率　
   銀貨を選ぶ確率　
   銅貨を選ぶ確率　
   となる。最後のは、つのどの状態に遷移するにしても回操作するから。
3. それぞれを選ぶ確率については、例２の式を参考にする。
4. これをメモ化再帰する。
5. のいずれかがの場合はとし、そこで再帰を止める。
6. サンプルが全部合ったのでとりあえず提出し、AC。

import java.util.Scanner;

public class Main {
    static double[][][] dp = new double[101][101][101];
    static boolean[][][] v = new boolean[101][101][101];

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

        System.out.println(dfs(a, b, c));
    }

    static double dfs(int a, int b, int c) {
        if (v[a][b][c]) {
            return dp[a][b][c];
        }
        v[a][b][c] = true;
        if (a == 100 || b == 100 || c == 100) {
            return dp[a][b][c] = 0;
        }
        double ret = 1;
        ret += dfs(a + 1, b, c) * a / (a + b + c);
        ret += dfs(a, b + 1, c) * b / (a + b + c);
        ret += dfs(a, b, c + 1) * c / (a + b + c);
        return dp[a][b][c] = ret;
    }
}

ここまで23分54秒＋0ペナ。216位。

E - Third Avenue

問題
ダイクストラをしていたが、辺のコストは全て1だったのでBFSでよかったことに、公式解説を読んで気が付いた。

思考過程

1. 通常の上下左右に移動できるグリッド上の最短経路問題に加え、a～zのマスの場合は、同じ文字のマスにも辺が張られているというだけ。
2. 同じ文字のマスリスト（実装上は無駄にセットになっているが）をあらかじめ作っておく。
3. 方向の遷移に加え、同じ文字のマスリストにも遷移を試みるようにする。　→4ケースTLE
4. 同じ文字のマスリストへの遷移は、スタートから最も近いマスからの回しかする必要がないので、回以上使わないようにしておく。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        char[][] a = new char[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = br.readLine().toCharArray();
        }
        br.close();

        int sx = 0;
        int sy = 0;
        int gx = 0;
        int gy = 0;
        List<Set<Integer>> list = new ArrayList<>(26);
        for (int i = 0; i < 26; i++) {
            list.add(new HashSet<>());
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (a[i][j] == 'S') {
                    sx = i;
                    sy = j;
                } else if (a[i][j] == 'G') {
                    gx = i;
                    gy = j;
                } else if (a[i][j] == '.') {
                } else if (a[i][j] == '#') {
                } else {
                    int c = a[i][j] - 'a';
                    list.get(c).add(i * w + j);
                }
            }
        }

        int[] d = new int[h * w];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[sx * w + sy] = 0;
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        Node first = new Node(sx * w + sy, 0);
        que.add(first);

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!que.isEmpty()) {
            Node cur = que.poll();
            int cx = cur.v / w;
            int cy = cur.v % w;
            if (cur.d > d[cur.v]) {
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (0 <= nx && nx < h && 0 <= ny && ny < w &&
                        a[nx][ny] != '#') {
                    int next = nx * w + ny;
                    int alt = d[cur.v] + 1;
                    if (alt < d[next]) {
                        d[next] = alt;
                        que.add(new Node(next, alt));
                    }
                }
            }
            if ('a' <= a[cx][cy] && a[cx][cy] <= 'z') {
                for (int next : list.get(a[cx][cy] - 'a')) {
                    if (d[cur.v] + 1 < d[next]) {
                        d[next] = d[cur.v] + 1;
                        que.add(new Node(next, d[cur.v]));
                    }
                }
                list.get(a[cx][cy] - 'a').clear(); // ここがなくてTLE
            }
        }
        if (d[gx * w + gy] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(d[gx * w + gy]);
        }
    }

    static class Hen {
        int v, c;

        public Hen(int v, int c) {
            this.v = v;
            this.c = c;
        }
    }

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

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

        public int compareTo(Node o) {
            return d - o.d;
        }
    }
}

ここまで46分02秒＋1ペナ。323位。

F - Programming Contest

問題
初めの2回は誤りなので仕方ないが、半分全列挙に気付いた後も4回もTLEしてしまい、ひたすら苦しんだ。
制約がならもう少し楽に通ったんじゃないだろうか・・・。

思考過程

1. ナップサックDPのようなことをやりたくなる。ただし、の配列は持てないので、出てきた値の集合を管理していくことにする。
2. 遷移はざっくり言えば、→のようになる。の場合は捨てる。　→3ケースTLE
3. 残りの合計を足しても現在の最大値に届かない値も捨てるようにしてみる。　→2ケースTLE
4. 落ちたケースが少ないので小手先の改善に走ろうとしてしまったが、そもそもこれではなので全然駄目そう。
   　
5. 最初の提出を半分全列挙に変更する。　→1ケースTLE
6. 一方ソートあり、もう一方ソートなしで、ソートする側のサイズをにしてみる。　→2ケースTLE
7. 途中まで両方ソートなし（HashSet）で、最後にTreeSetに移してみる。　→2ケースTLE
8. 上記7を取り込んでもう一度サイズをに戻してみる。　　→2ケースTLE
9. 定数倍が重いのかも。最悪ケースを考えると、重複排除されるHashSetである意味がないので、Listに変えてみる。　→1979msでぎりぎりAC

他の人のソースを見ると、最初からサイズの配列を用意しており、確かにそっちの方が最悪ケースで軽そうだと思った。
なお、思考過程6は、過去に別の問題で半分からかしたら通ったことがあったことから来た発想。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.TreeSet;

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

        int n2 = n / 2;
        List<Integer> list = new ArrayList<>();
        list.add(0);
        for (int i = 0; i < n2; i++) {
            List<Integer> wk = new ArrayList<>();
            wk.addAll(list);
            for (int o : list) {
                int v = o + a[i];
                if (v <= t) {
                    wk.add(v);
                }
            }
            list = wk;
        }

        List<Integer> list2 = new ArrayList<>();
        list2.add(0);
        for (int i = n2; i < n; i++) {
            List<Integer> wk = new ArrayList<>();
            wk.addAll(list2);
            for (int o : list2) {
                int v = o + a[i];
                if (v <= t) {
                    wk.add(v);
                }
            }
            list2 = wk;
        }

        TreeSet<Integer> set = new TreeSet<>();
        set.addAll(list);
        int ans = 0;
        for (int i : list2) {
            int j = set.floor(t - i);
            ans = Math.max(ans, i + j);
        }
        System.out.println(ans);
    }
}

ここまで73分42秒＋7ペナ。451位。
思考過程5のところで通っていれば、65分50秒＋3ペナだったのだが・・・。

最終結果：ABCDEFの全完、108分42秒、620位、パフォーマンス1742
レート変動：1693→1698（+5）

80分50秒ならパフォ1921だったので、今回は本当に定数倍に泣かされた。
まあ本質的には解けていたと思うのでヨシ。

あとはCとEの実装が遅すぎ。