AtCoder Regular Contest 109

コンテスト前のレート：1698
レート通りのパフォーマンスが得られる順位：667位（1200点、55分48秒）

A - Hands

問題
深く考えずにダイクストラをしたが、通った瞬間に、で解けたのではと思った。
ダイクストラの実装がいつも遅い。
最初に全部辺を張っておいた方が、ダイクストラ部分がコピペだけで済んで楽だった気がする。開き直った結果とはいえ、if文や重複コードの多さがもう少しなんとかならなかったものか。

思考過程

1. A, Bの各階個を頂点としてダイクストラをすることを考える。
2. 辺（廊下や階段）は、次の頂点への遷移部分で場合分けして可能な移動を処理することにする。

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 a = Integer.parseInt(sa[0]) - 1;
        int b = Integer.parseInt(sa[1]) - 1;
        int x = Integer.parseInt(sa[2]);
        int y = Integer.parseInt(sa[3]);
        br.close();

        int n = 100;
        int[] d = new int[n * 2];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[a] = 0;
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        Node first = new Node(a, 0);
        que.add(first);

        while (!que.isEmpty()) {
            Node cur = que.poll();
            if (cur.d > d[cur.v]) {
                continue;
            }
            int cx = cur.v / n; // 0:A, 1:B
            int cy = cur.v % n; // 階-1
            // 1階下へ
            if (0 < cy) {
                int next = cx * n + (cy - 1);
                int alt = d[cur.v] + y;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
            }
            // 1階上へ
            if (cy < n - 1) {
                int next = cx * n + (cy + 1);
                int alt = d[cur.v] + y;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
            }
            // A→B
            if (cx == 0) {
                // Aのi階→Bのi階
                int next = n + cy;
                int alt = d[cur.v] + x;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
                // Aのi+1階→Bのi階
                if (0 < cy) {
                    next = n + (cy - 1);
                    alt = d[cur.v] + x;
                    if (alt < d[next]) {
                        d[next] = alt;
                        que.add(new Node(next, alt));
                    }
                }
            // B→A
            } else {
                // Bのi階→Aのi階
                int next = cy;
                int alt = d[cur.v] + x;
                if (alt < d[next]) {
                    d[next] = alt;
                    que.add(new Node(next, alt));
                }
                // Bのi階→Aのi+1階
                if (cy < n - 1) {
                    next = (cy + 1);
                    alt = d[cur.v] + x;
                    if (alt < d[next]) {
                        d[next] = alt;
                        que.add(new Node(next, alt));
                    }
                }
            }
        }
        System.out.println(d[n + b]);
    }

    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;
        int d;

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

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

ここまで11分31秒＋0ペナ。925位。

B - log

問題
とするべきところがになっているというしょうもない1ペナを喰らう。

思考過程

1. 長さの丸太を～に分割するのが最適。
2. を満たす最大のを求めれば、が答え。
3. として、適当にの付近を試す。　→12ケースWA
4. 上記の方法だと、かなりの広範囲を調べる必要がありそうな気がしたので、二分探索をする。
5. ngの初期値は、乗しては超えるがlongの範囲は超えない程度に設定。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        br.close();

        long n2 = (n + 1) * 2;
        long ok = 1;
        long ng = 2000000000;
        while (Math.abs(ok - ng) > 1) {
            long mid = (ok + ng) / 2;
            if (mid * (mid + 1) <= n2) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        System.out.println(n + 1 - ok);
    }
}

ここまで24分47秒＋2ペナ。699位。

C - Large RPS Tournament

問題

思考過程

1. 例２を書き出してみて考える。
2. が奇数の場合、最後の参加者は最初の参加者と対戦することになる。より後の結果は、最初の組の結果の繰り返しになる。
3. 回戦も、回戦の最初の組の結果をとして同様に処理できる。
4. 以降同様。回処理後の先頭の文字が答え。
5. じゃんけんの勝敗の判定は、一瞬通りの場合分けを書きかけたが、Setに入れることで、SとPの対戦（Rがない）の場合はSの勝利などとした。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

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

        List<List<Character>> list = new ArrayList<>();
        List<Character> f = new ArrayList<>();
        for (char c : s) {
            f.add(c);
        }
        list.add(f);

        for (int i = 0; i < k; i++) {
            List<Character> pre = list.get(i);
            if (pre.size() % 2 == 1) {
                Character[] arr = pre.toArray(new Character[0]);
                for (Character c : arr) {
                    pre.add(c);
                }
            }
            List<Character> wk = new ArrayList<>();
            for (int j = 0; j < pre.size(); j+=2) {
                char a = pre.get(j);
                char b = pre.get(j + 1);
                Set<Character> set = new HashSet<>();
                set.add(a);
                set.add(b);
                if (set.size() == 1) {
                    wk.add(a);
                } else {
                    if (!set.contains('R')) {
                        wk.add('S');
                    } else if (!set.contains('S')) {
                        wk.add('P');
                    } else {
                        wk.add('R');
                    }
                }
            }
            list.add(wk);
        }
        System.out.println(list.get(k).get(0));
    }
}

ここまで48分27秒＋2ペナ。571位。

D - く

問題
思考過程8～10辺りが詰まりきっていないまま何度もWAを重ねたが、直しても直しても一向にACが増えず、そもそもオーバーフローしていたのが根本的に駄目だった。
マルチケースだとわずかな間違いでもほぼ全てWAになると思うので、闇雲に提出しても原因特定が難しい。

思考過程

1. 書き出してみると、回の操作での遷移は通りほどあるようだが、制約が大きいのでそのままBFSなどはできない。
2. また、回の場合ですら、入力が初期位置と一致しているか調べるのは、単純な場合分けでは大変そう。
   　
3. 右上に最速で移動していく方法を考えてみると、基本的には手で同じ形のままつ右上（x座標、y座標共に）に動かせる。
4. x座標とy座標を独立させて見てみると、点の合計で、増分とが交互になる。
5. x座標について見たとき、がほぼ答え。y座標も同様に計算し、それらのを取ればよい。
6. 以降、目的地に向かってという移動ができないケースを潰していく。
   　
7. 目的地が正方向の場合、初手はになる。
8. x座標、y座標共に正方向に動かしたい場合、一方が、もう一方がのようになるため、動かしたい距離が小さい方を後者に割り当てる。手目に移動できない分、手プラスとする。
9. x座標、y座標共に負方向に動かしたい場合、一方が、もう一方がのようになるため、動かしたい距離が小さい方を後者に割り当てる。手目に移動できない分、手プラスとする。
10. 一方が負方向、もう一方が正方向の場合は、とで、上記7以外の制限はない。
11. をつ足すとintの範囲を超えるので、オーバーフロー対策する。

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 t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < t; i++) {
            String[] sa = br.readLine().split(" ");
            long ax = Integer.parseInt(sa[0]);
            long ay = Integer.parseInt(sa[1]);
            long bx = Integer.parseInt(sa[2]);
            long by = Integer.parseInt(sa[3]);
            long cx = Integer.parseInt(sa[4]);
            long cy = Integer.parseInt(sa[5]);

            long vx = calc(ax, bx, cx);
            long vy = calc(ay, by, cy);
            long max = Math.max(vx, vy); // 思考過程5
            long tx = ax + bx + cx - 1;
            long ty = ay + by + cy - 1;
            // 思考過程8
            if (tx > 0 && ty > 0) {
                // 2手以上かかる場合
                if (Math.max(tx, ty) > 1) {
                    long min = Math.min(vx, vy) + 1;
                    max = Math.max(max, min);
                }
            // 思考過程9
            } else if (tx < 0 && ty < 0) {
                long min = Math.min(vx, vy) + 1;
                max = Math.max(max, min);
            }
            pw.println(max);
        }
        br.close();
        pw.flush();
    }

    static long calc(long ax, long bx, long cx) {
        long sx = 1;
        long tx = ax + bx + cx;
        long dx = Math.abs(tx - sx);
        long vx = dx / 3 * 2;
        dx %= 3;
        // 思考過程7
        int fx = 1;
        if (tx < sx) {
            fx = 2;
        }
        if (dx > 0) {
            dx -= fx;
            vx++;
            if (dx > 0) {
                vx++;
            }
        }
        return vx;
    }
}

ここまで118分23秒＋6ペナ。211位。

最終結果：ABCDの4完、148分23秒、214位、パフォーマンス2244
レート変動：1698→1766（+68）

AやBに手間取っていてまた今日も駄目かと思ったが、Cが普通くらいの時間で通せてなんとか救われ（3完ならパフォ1660程度でレート減少はわずかだった）、Dもやり切ることができてよかった。
D問題のDifficultyは2394で、本番中ACの最高難易度を更新。これまでの本番中黄diffACが7問目。

黄diffがたまに通るのもいいことだが、今年はとにかく青diffの正解率が低い状態で、青diffの正解率を上げるための復習が必要かな・・・というところ。

競プロ歴が2年近くになり、これまでに勉強したことも色々忘れ始めてきているようなので、くじかつで思い出すようにして、既出の類題で落とすことがないようにしていきたい。

レートについては、一時期highest-178まで落ち込んでいたが、今回で-54まで回復。次回2220ほど出せれば完全回復というところまで戻ってきた。