AtCoder Regular Contest 150

コンテスト前のレート：
レート通りのパフォーマンスが得られる順位：439位（1300点、102分21秒）

A - Continuous 1

問題
連続部分以外に'1'があってもいいと勘違いするしミスもするしひどかった。
下記7.のようなcontinueミスをするくらいならやっぱり1ケース分でメソッド化くらいするべきかな・・・。

思考過程

1. '0'以外の文字が連続かつ前後が'1'でない箇所が箇所だけなら"Yes"？　→12/26ケースWA
2. その箇所について、該当の箇所以外に'1'がないことも見ないと駄目だった。　→変わらず
3. これだとそもそも範囲内に全ての'1'を含まない箇所も候補数に数えてしまっていて駄目。
   　
4. 最初の'1'から最後の'1'までの区間を必ず含める区間とし、前後に続く'?'も含めてちょうどになればよい。また、前か後一方しか'?'が続かない場合は以上続いてもよい。
5. '1'が個もない場合は"No"にしておく。　→16/26ケースWA
6. '?'が個連続でもOKなのでそんなわけない。そのようなケースも"Yes"にする。　→8/26ケースWA
   　
7. 色々試すとケース数よりも多く答えが出力されている。for文の途中で"No"を出力してcontinueしていたら、次のケースへのスキップになっていなかったので直す。

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);
        label:
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            int n = Integer.parseInt(sa[0]);
            int k = Integer.parseInt(sa[1]);
            char[] s = br.readLine().toCharArray();

            int l = n;
            int r = -1;
            for (int i = 0; i < n; i++) {
                if (s[i] == '1') {
                    l = Math.min(l, i);
                    r = Math.max(r, i);
                }
            }
            // 6. '1'が1個もない場合
            if (l > r) {
                int cnt = 0;
                int one = 0;
                for (int i = 0; i < n; i++) {
                    if (s[i] == '?') {
                        one++;
                        if (one >= k) {
                            cnt++;
                        }
                    } else {
                        one = 0;
                    }
                }
                if (cnt == 1) {
                    pw.println("Yes");
                } else {
                    pw.println("No");
                }
                continue;
            }
            // 最初と最後の'1'の間に'0'がないか
            for (int i = l; i <= r; i++) {
                if (s[i] == '0') {
                    pw.println("No");
                    continue label; // 7. labelが付いていなかった
                }
            }
            // '1'の区間がちょうど長さK
            if (r - l + 1 == k) {
                pw.println("Yes");
                continue;
            }
            // '1'の区間がKより長い
            if (r - l + 1 > k) {
                pw.println("No");
                continue;
            }

            // '1'の区間の前に続く'?'
            int cnt1 = 0;
            for (int i = l - 1; i >= 0; i--) {
                if (s[i] == '?') {
                    cnt1++;
                } else {
                    break;
                }
            }
            // '1'の区間の後に続く'?'
            int cnt2 = 0;
            for (int i = r + 1; i < n; i++) {
                if (s[i] == '?') {
                    cnt2++;
                } else {
                    break;
                }
            }
            // 4. '1'と前後の'?'を合わせた長さを元に判定
            int total = r - l + 1 + cnt1 + cnt2;
            if (total < k) {
                pw.println("No");
            } else if (total == k) {
                pw.println("Yes");
            } else {
                if (cnt1 == 0 || cnt2 == 0) {
                    pw.println("Yes");
                } else {
                    pw.println("No");
                }
            }
        }
        pw.flush();
        br.close();
    }
}

ここまで40分14秒＋4ペナ。1085位。

B - Make Divisible

問題

思考過程

1. 最初から条件を満たす場合は。
2. を増やさない場合と、を最低限だけ増やす（として、これがで済むようになるまでを増やす）場合だけ考えればよい？
3. サンプルケース目がとなり、除算が発生。の場合は明らかにをになるまで増やすのが最適なので条件分け。
4. また、サンプルケース目が合わないのでやっぱり全探索的なことをする必要はありそう。制約的にはとかくらい。
   　
5. を全探索することを考えると、調べる必要があるのは上記2.のの種類数。
6. の間は普通に全探索し、の間はを全探索すればよいことになる。

※下記コード内のx, yは問題文中のとは異なる。

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));
        int t = Integer.parseInt(br.readLine());
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]);
            int b = Integer.parseInt(sa[1]);

            // 3
            if (a > b) {
                System.out.println(a - b);
                continue;
            }

            // 1
            int x = b % a;
            if (x == 0) {
                System.out.println(0);
                continue;
            }
            long ans = a - x;

            // 6
            for (int i = a; i * i <= b; i++) {
                long y = b % i;
                if (y == 0) {
                    ans = Math.min(ans, i - a);
                } else {
                    ans = Math.min(ans, i - a + i - y);
                }
            }
            for (int m = 1; m * m <= b; m++) {
                long i = (b + m - 1) / m;
                if (i < a) {
                    break;
                }
                long y = b % i;
                if (y == 0) {
                    ans = Math.min(ans, i - a);
                } else {
                    ans = Math.min(ans, i - a + i - y);
                }
            }
            System.out.println(ans);
        }
        br.close();
    }
}

ここまで61分21秒＋4ペナ。542位。

C - Path and Subsequence

問題
最近やったABC271-Eにちょっと似ているような気がした。

思考過程

1. 「各頂点にたどり着いた時、最も悪くての何番目までを部分列として持った状態になっているか」を始点から各頂点までの距離としてダイクストラ法をする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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 n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        int k = Integer.parseInt(sa[2]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int u = Integer.parseInt(sa[0]) - 1;
            int v = Integer.parseInt(sa[1]) - 1;
            list.get(u).add(v);
            list.get(v).add(u);
        }
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[k + 1]; // 配列外参照しそうなので+1
        for (int i = 0; i < k; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int inf = 1000000000;
        int[] d = new int[n];
        Arrays.fill(d, inf);
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        que.add(new Node(0, -1));
        d[0] = -1; // 頂点0に付いた時点で、頂点0分を除きb[-1]まで満たしているとする
        boolean[] fix = new boolean[n];
        while (!que.isEmpty()) {
            Node cur = que.poll();
            int cv = cur.v;
            if (fix[cv]) {
                continue;
            }
            fix[cv] = true;
            if (b[d[cv] + 1] == a[cv]) {
                d[cv]++;
            }
            for (int next : list.get(cv)) {
                if (!fix[next]) {
                    if (d[cv] < d[next]) {
                        que.add(new Node(next, d[cv]));
                        d[next] = d[cv];
                    }
                }
            }
        }
        if (d[n - 1] == k - 1) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    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;
        }
    }
}

ここまで78分09秒＋4ペナ。350位。

残り時間は一応全ての問題を読んでからDを解こうとするも何もわからず。
とりあえずパスグラフで考えてもでもうわからなかった。
こういう確率とか期待値とかのやつ苦手。

最終結果：ABCの3完1300点、98分09秒、415位、パフォーマンス1991
レート変動：1962→1965（+3）

そうか青パフォでもプラスなのか・・・という感じ。

前回のARCと同じくA問題で大苦戦したが今回はなんとか通せた。
Aでペナ込み1時間もかかっており、これが10分20分で解けていれば2200台ほどのパフォが出ていたのでもったいない。

まず問題をまともに読解できていないのをなんとかしなければ。