AtCoder Beginner Contest 223(Rated範囲外)

ABC

コンテスト前のレート：2038
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：187位（2000点、75分28秒）

A - Exact Price

問題

思考過程
  1. Xが0以外かつ、100で割り切れるかを調べる。
import java.util.Scanner;

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

        if (x > 0 && x % 100 == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

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


B - String Shifting

問題

思考過程
  1. とりあえずSを2つ繋げておけば、長さNの部分文字列を取り出すことでシフトした文字列を作れる。
  2. 開始位置が0～(N-1)である長さNの部分文字列を全てTreeSetに突っ込み、先頭と最後を取り出す。
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);
        String s = sc.next();
        sc.close();

        int n = s.length();
        char[] ss = (s + s).toCharArray();
        TreeSet<String> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            String t = String.valueOf(ss, i, n);
            set.add(t);
        }
        System.out.println(set.first());
        System.out.println(set.last());
    }
}

ここまで3分52秒＋0ペナ。265位。


C - Doukasen

問題

思考過程
  1. 左側からのみ火を付けた場合、導火線iが燃えるのにかかる時間C_iは、\frac{A_i}{B_i}。
  2. 求める地点にたどり着くまでの時間は、C_iの総和\div 2。
  3. (左からC_{i-1}までの和) \lt (上記2.の値) \le (左からC_{i}までの和)とすると答えは、(左からA_{i-1}までの和)に、A_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[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        sc.close();

        double[] c = new double[n];
        double sum = 0;
        for (int i = 0; i < n; i++) {
            c[i] = (double) a[i] / b[i]; // 1
            sum += c[i];
        }
        sum /= 2; // 2

        double ans = 0;
        double val = 0;
        for (int i = 0; i < n; i++) {
            if (val + c[i] <= sum) {
                ans += a[i];
                val += c[i];
            } else {
                double d = sum - val;
                ans += a[i] * d / c[i];
                break;
            }
        }
        System.out.println(ans);
    }
}

ここまで8分41秒＋0ペナ。58位。


D - Restricted Permutation

問題

思考過程
  1. 初めにまず1から順に並べた数列を作ってしまって、条件1つごとに満たしていなかったらrotateしていけばと考えてみるが、正当性怪しいし計算量もO(NM)になってしまいそう。
  2. 他に、連結成分ごとになんやかんやできないかなどと考えたりするが、できる気がしない。
    　
  3. A_iからB_iに辺を張った有向グラフを作ることをちゃんと考えてみると、ほぼトポロジカルソートするだけに思えてくる。
  4. トポロジカルソートを貼って、辞書順最小にするためにPriorityQueueに変更して、あとトポロジカルソートができたかどうかの判定を加える。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        int[] inCnt = new int[n];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            list.get(a).add(b);
            inCnt[b]++;
        }
        br.close();

        List<Integer> res = new ArrayList<>(n);
        PriorityQueue<Integer> que = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (inCnt[i] == 0) {
                que.add(i);
            }
        }
        while (!que.isEmpty()) {
            int cur = que.poll();
            res.add(cur);
            for (int i : list.get(cur)) {
                inCnt[i]--;
                if (inCnt[i] == 0) {
                    que.add(i);
                }
            }
        }

        if (res.size() != n) {
            System.out.println(-1);
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i : res) {
                sb.append(i + 1).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}

ここまで17分02秒＋0ペナ。76位。


E - Placing Rectangles

問題

思考過程
  1. 横→縦に切る場合と、横→横に切る場合を考える。
  2. まず横に切る際は、Y方向について\lceil \frac{A}{X} \rceilだけ使用するのが最適。
  3. 残った(Y-\lceil \frac{A}{X} \rceil) \times Xの領域について、縦に切る場合も横に切る場合も、ぎりぎり面積B以上となるように切り出して、残った面積がC以上あれば"Yes"。
  4. あとは、X, Yの入れ替え（縦→横、縦→縦）と、A, B, Cの入れ替えを全部試す。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long y = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        sc.close();

        if (judge(x, y, a, b, c)) {
            System.out.println("Yes");
            return;
        }
        if (judge(y, x, a, b, c)) {
            System.out.println("Yes");
            return;
        }
        if (judge(x, y, b, c, a)) {
            System.out.println("Yes");
            return;
        }
        if (judge(y, x, b, c, a)) {
            System.out.println("Yes");
            return;
        }
        if (judge(x, y, c, a, b)) {
            System.out.println("Yes");
            return;
        }
        if (judge(y, x, c, a, b)) {
            System.out.println("Yes");
            return;
        }
        System.out.println("No");
    }

    static boolean judge(long x, long y, long a, long b, long c) {
        long a1 = (a + x - 1) / x;
        long y2 = y - a1;
        if (y2 > 0) {
            // 横→縦
            long b1 = (b + y2 - 1) / y2;
            long x2 = x - b1;
            if (x2 > 0) {
                if (x2 * y2 >= c) {
                    return true;
                }
            }
            // 横→横
            long b2 = (b + x - 1) / x;
            long y3 = y2 - b2;
            if (x * y3 >= c) {
                return true;
            }
        }
        return false;
    }
}

ここまで27分46秒＋0ペナ。45位。


F - Parenthesis Checking

問題
遅延セグ木を自力で使ったのが初めてなので時間かかった。
境界値のミスがあって1ペナ。

思考過程
  1. '('を+1、')'を-1に置き換えた数列Aで累積和を取ると、l～r文字目が正しい括弧列になるためには、A_{l-1} = A_rかつ、この範囲内のA_iの最小値が両端を下回らないことが必要。
  2. クエリ1でS_l \ne S_rの場合に、数列Aがどのように変わるかを観察すると、A_l～A_{r-1}が+2もしくは-2される。
  3. よって、遅延セグ木を使って、クエリ1で区間加算、クエリ2で区間最小値取得ができればよさそう。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.function.BiFunction;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

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 q = Integer.parseInt(sa[1]);
        char[] ss = br.readLine().toCharArray();
        int[] t = new int[q];
        int[] l = new int[q];
        int[] r = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            l[i] = Integer.parseInt(sa[1]);
            r[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        Integer[] arr = new Integer[n + 1];
        arr[0] = 0;
        for (int i = 0; i < n; i++) {
            arr[i + 1] = arr[i] + (ss[i] == '(' ? 1 : -1);
        }
        LazySegTree<Integer, Integer> st = new LazySegTree<>(
                arr,
                Integer.MAX_VALUE,
                (s1, s2) -> {
                    return Math.min(s1, s2);
                },
                (f, s) -> {
                    return f + s;
                },
                (f1, f2) -> {
                    return f1 + f2;
                },
                0);

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            int li = l[i];
            int ri = r[i];
            if (t[i] == 1) {
                if (ss[li - 1] == '(' && ss[ri - 1] == ')') {
                    st.apply(li, ri, -2);
                    ss[li - 1] = ')';
                    ss[ri - 1] = '(';
                } else if (ss[li - 1] == ')' && ss[ri - 1] == '(') {
                    st.apply(li, ri, 2);
                    ss[li - 1] = '(';
                    ss[ri - 1] = ')';
                }
            } else {
                int vl = st.get(li - 1);
                int vr = st.get(ri);
                int min = st.prod(li - 1, ri);
                if (vl == vr && min == vl) {
                    pw.println("Yes");
                } else {
                    pw.println("No");
                }
            }
        }
        pw.flush();
    }
}

// 以下ACLを移植したLazySegTree

提出
ここまで87分13秒＋1ペナ。240位。



Gは、木の最大マッチングは葉から貪欲をすればよいらしいことだけ調べて、葉から2番目は絶対消せないのではなどと考えながら適当なDPをしたりするが、サンプルも合わず。



最終結果：ABCDEFの6完2000点、92分13秒、255位、パフォーマンス1921相当
レート変動：2038（Unrated）


今回は遅延セグ木を使えたのが良かった。
セグ木と同様の部分はもうあまり迷うことはないが、mapping、composition、idはどうすればいいのかあまり理解しておらず、区間加算だけなら非常に単純だったのでなんとかなった。