AtCoder Beginner Contest 190

ABC

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

A - Very Very Primitive Game

問題
if文1つにまとめて書くこともできそうだが、無難にやった。

思考過程
  1. C=0の場合、A=Bなら後手の青木くんの勝ち、A \lt Bでももちろん青木くんの勝ち。
  2. C=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();
        sc.close();

        if (c == 0) {
            if (a <= b) {
                System.out.println("Aoki");
            } else {
                System.out.println("Takahashi");
            }
        } else {
            if (b <= a) {
                System.out.println("Takahashi");
            } else {
                System.out.println("Aoki");
            }
        }
    }
}

ここまで1分29秒＋0ペナ。84位。


B - Magic 3

問題

思考過程
  1. 前から順に見ていき、条件を満たしているものがあったところでYesで終了。
  2. 条件は、「X_i \ge SまたはY_i \le D」が駄目なので、「X_i \lt SかつY_i \gt D」を満たす必要がある。
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 s = sc.nextInt();
        int d = 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();

        for (int i = 0; i < n; i++) {
            if (x[i] < s && y[i] > d) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}

ここまで3分35秒＋0ペナ。191位。


C - Bowls and Dishes

問題

思考過程
  1. Kが小さいので、各人がCを選んだかDを選んだか、2^K通り全探索することを考える。
  2. それぞれのパターンについて、O(M)で各条件が満たされるかどうかを調べて全体でO(2^KM)くらいでも間に合いそう。
  3. 判定は、選ばれた皿のSetを作ってcontainsで行うと簡単。
import java.util.HashSet;
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 m = sc.nextInt();
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        int[] c = new int[k];
        int[] d = new int[k];
        for (int i = 0; i < k; i++) {
            c[i] = sc.nextInt();
            d[i] = sc.nextInt();
        }
        sc.close();

        int ans = 0;
        int end = 1 << k;
        for (int i = 0; i < end; i++) {
            Set<Integer> set = new HashSet<>();
            for (int j = 0; j < k; j++) {
                if ((i >> j & 1) == 1) {
                    set.add(c[j]);
                } else {
                    set.add(d[j]);
                }
            }

            int cnt = 0;
            for (int j = 0; j < m; j++) {
                if (set.contains(a[j]) && set.contains(b[j])) {
                    cnt++;
                }
            }
            ans = Math.max(ans, cnt);
        }
        System.out.println(ans);
    }
}

ここまで7分38秒＋0ペナ。125位。


D - Staircase Sequences

問題
サンプルがかなり親切。
ちょっと自信なかったけど、コーナーのような例２と最大に近い例３が通ればまあ大丈夫だろうってなった。

思考過程
  1. 例１を見ながら条件を数式化していく。
  2. 数列の先頭をL、末尾をRとすると、台形の面積を求める要領（上底L、下底R、高さは要素数）で総和を求め、(L+R) \times (R-L+1) \div 2 = Nを満たす必要がある。
  3. これは、X \times Y = 2Nという形になるため、2Nの約数を全探索することを考える。
  4. 要素数をXとし、2N \div X = Yとすると、L+R=Y、R= L+X-1であるため、2L+X-1=Yを満たす必要がある。
  5. これを2L=Y-(X-1)とし、結局Y-(X-1)が偶数である場合をカウントしていけばよい。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

        int ans = 0;
        long n2 = n * 2;
        List<Long> list = divList(n2);
        for (long x : list) {
            long y = n2 / x;
            y -= x - 1;
            if (y % 2 == 0) {
                ans++;
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static List<Long> divList(long n) {
        List<Long> list = new ArrayList<>();
        long end = (long) Math.sqrt(n);
        for (int i = 1; i <= end; i++) {
            if (n % i == 0) {
                list.add((long) i);
            }
        }
        int i = end * end == n ? list.size() - 2 : list.size() - 1;
        for ( ; i >= 0; i--) {
            list.add(n / list.get(i));
        }
        return list;
    }
}

ここまで16分09秒＋0ペナ。155位。


E - Magical Ornament

問題
問題を読み終わってぱっと解けそうになく、順位表でもFの方が解かれていたので、先にFを解いた。
戻ってきた後、解法のイメージはすぐに出てきたが、実装が重めで時間がかかり、サンプルが一発では通らずデバッグに数分を要した。

思考過程
  1. 問題文を読み替えると、N, M, A, Bまでの入力は単に無向グラフを表していて、C_1～C_Kを1回以上通るルートの最短距離を求めよと言われている。
  2. これは、「DP[i][j]:=既に通った目的地の集合がiで、現在地（最後に通った頂点）がj」でできそうだが、O(2^KN)では駄目。
  3. あらかじめK個の頂点間の距離を求めておけば、O(2^KK)になる。
  4. 遷移は、集合iに含まれている頂点全てから、含まれていない頂点全てへの配る遷移を調べ、minを取っていく。
  5. 遷移がO(K^2)だと怪しい気もするが、定数倍を抑えるようにすれば大丈夫そう？
  6. 頂点間距離の前計算は、K回ダイクストラ・・・ではなくBFSをする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

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<>());
        }
        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);
            list.get(b).add(a);
        }
        int k = Integer.parseInt(br.readLine());
        sa = br.readLine().split(" ");
        int[] c = new int[k];
        for (int i = 0; i < k; i++) {
            c[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        // 頂点間の距離を前計算
        int[][] d = new int[k][n];
        for (int i = 0; i < k; i++) {
            d[i] = bfs(list, c[i]);
        }

        int end = 1 << k;
        int[][] dp = new int[end][k];
        for (int i = 0; i < end; i++) {
            Arrays.fill(dp[i], 100000000);
        }
        // 頂点を1つだけ訪問済の状態を初期状態とする
        for (int i = 0; i < end; i++) {
            if (Integer.bitCount(i) == 1) {
                for (int j = 0; j < k; j++) {
                    if ((i >> j & 1) == 1) {
                        dp[i][j] = 0;
                        break;
                    }
                }
            }
        }
        for (int i = 1; i < end; i++) {
            List<Integer> list1 = new ArrayList<>(); // 訪問済リスト
            List<Integer> list2 = new ArrayList<>(); // 未訪問リスト
            for (int j = 0; j < k; j++) {
                if ((i >> j & 1) == 1) {
                    list1.add(j);
                } else {
                    list2.add(j);
                }
            }
            // 訪問済→未訪問の全組合せ
            for (int j : list1) {
                for (int j2 : list2) {
                    int next = i | 1 << j2;
                    dp[next][j2] = Math.min(dp[next][j2], dp[i][j] + d[j][c[j2]]);
                }
            }
        }
        int ans = 100000000;
        for (int i = 0; i < k; i++) {
            ans = Math.min(ans, dp[end - 1][i]);
        }
        ans++;
        if (ans >= 100000000) {
            ans = -1;
        }
        System.out.println(ans);
    }

    static int[] bfs(List<List<Integer>> list, int s) {
        int[] d = new int[list.size()];
        Arrays.fill(d, 100000000);
        d[s] = 0;
        Queue<Integer> que = new ArrayDeque<>();
        que.add(s);

        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int next : list.get(cur)) {
                if (d[next] == 100000000) {
                    d[next] = d[cur] + 1;
                    que.add(next);
                }
            }
        }
        return d;
    }
}

ABCDFEと解いた時点で45分36秒＋0ペナ。132位。


F - Shift and Inversions

問題
要素が順列でなく、値の範囲が広かったり重複があったりしても、実装が面倒になるだけでそこまで難易度変わらないだろうか・・？
自分のライブラリだと、重複があるとおそらく駄目で、転倒数が貼るだけではなくなってしまうので助かったが。

思考過程
  1. とりあえず初期状態の転倒数を求める。
  2. 例１を見て、k=1の時は、k=0と比べて先頭要素を一番後ろに移動させている。
  3. そのように移動すると、先頭要素について、それより小さい値の数分転倒数が減り、それより大きい値の数分転倒数が増える。
  4. aが0, \ldots, N-1の並び替えであることから、a_iより小さい値の数も大きい値の数もO(1)で計算できる。
  5. この差分計算を繰り返していくだけに見えるが、本当にそれだけ？　→サンプルが合ったので提出してAC
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 n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long ans = tentousuu(a);
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(ans);
        for (int i = 0; i < n - 1; i++) {
            ans -= a[i];
            ans += n - 1 - a[i];
            pw.println(ans);
        }
        pw.flush();
    }

    // 以下ライブラリ

    static long tentousuu(int[] a) {
        int n = a.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(min, a[i]);
            max = Math.max(max, a[i]);
        }
        min--;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = a[i] - min;
        }

        BIT bit = new BIT(max - min);
        long ret = 0;
        for (int i = 0; i < n; i++) {
            ret += i - bit.sum(b[i]);
            bit.add(b[i], 1);
        }
        return ret;
    }

    static class BIT {
        int n;
        long[] arr;

        public BIT(int n) {
            this.n = n;
            arr = new long[n + 1];
        }

        void add(int idx, long val) {
            for (int i = idx; i <= n; i += i & -i) {
                arr[i] += val;
            }
        }

        long sum(int idx) {
            long sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += arr[i];
            }
            return sum;
        }
    }
}

ABCDFと解いた時点で24分27秒＋0ペナ。53位。
Fが5～6分程度で解けたの非常においしい。



最終結果：ABCDEFの全完、45分36秒、132位、パフォーマンス2400
レート変動：1872→1937（+65）


第3回ABCトーナメント（B1）の1回戦は6～7分ほどの差で勝利。

初の令和ABC上限パフォで、初のレート1900台。
次もパフォ2400だとレート1992くらいで、ぎりぎり一発黄色には届かないというところ。

まあそれ以前にまず間違いなく1900台維持もままならないと思うが・・・。
やっと1800台安定したか？と思え始めたばかりくらいなので。

それにしても、昨年11月半ば以降の成績が本当にだいぶ安定していて、変わったことと言えば、その頃からコンテスト以外の日はくじかつを毎日欠かさずやっているくらいで、新しい黄diff以上へのチャレンジはほぼ全くしていないので、地盤固めは本当に大事だったんだな・・・という感じ。

黄色目指すならさすがに黄diffも少しずつ地盤の中に入れていかないと駄目だと思うけど。