AtCoder Beginner Contest 167

ABC


先に結果などを書いてしまうと、
全完124分26秒で、パフォーマンス2011、レート1738→1769(+31)。
ABC161から4連続マイナスの後、166、167は2連続全完で一気に2ヶ月ぶりのhighestまで戻りました。

緊急事態宣言以降は自宅待機が増え、精進量も増やしていたつもりがなかなか結果は出ず、辛くなり始めていたところでした。自分の経験では、精進の成果は1ヶ月くらい経ってから出てくることが多いような気がします。


A - Registration

問題
とりあえず最初に思いついた方法を全速力で実装する。

問題概要

2つの文字列S, Tが与えられる。Tが、Sに任意の1文字を追加した文字列である場合"Yes"、そうでなければ"No"を出力せよ。

  • S, Tは英小文字列
  • 1 \le |S| \le 10
  • |T|=|S|+1
思考過程
  1. Tから最後1文字を除いた文字列がSと一致するかを判定することにする。
import java.util.Scanner;

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

        if (t.substring(0, t.length() - 1).equals(s)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分24秒＋0ペナ。
終わった後のTwitterを見ていて、「t.startsWith(s)」で良かったことに気付いた。


B - Easy Linear Programming

問題
これもとりあえず最初に思いついた方法を全速力で実装する方針。

問題概要

1が書かれたカードがA枚、0が書かれたカードがB枚、-1が書かれたカードがC枚ある。
これらのカードから、ちょうどK枚を選んで取るとき、取ったカードに書かれた数の和として、ありえる値の最大値を求めよ。

  • 入力は全て整数
  • 0 \le A, B, C
  • 1 \le K \le A+B+C \le 2 \times 10^9
思考過程
  1. 1のカードから貪欲にK枚取る。
  2. 制約が大きいので計算で求める。
  3. オーバーフローは大丈夫そうだが、余計なペナルティを増やしたくないので念のため変数をlong型にしておく。
  4. まず+Aして、Bは無視するのでKからAとBを引く。引いた後がまだ0以上であればその分マイナス。　→WA。余計なペナ増やしたくないとは一体・・・。
  5. K \lt Aの場合の考慮が漏れていたことに、2分ほど悩んでやっと気付く。
import java.util.Scanner;

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

        long ans = Math.min(a, k);
        k -= a;
        k -= b;
        if (k > 0) {
            ans -= k;
        }
        System.out.println(ans);
    }
}

ここまで7分07秒＋1ペナ。およそ8分のロス。


C - Skill Up

問題
最近話題の全探索系。

問題概要

学びたいアルゴリズムがM個あり、最初各アルゴリズムの理解度は0。
N冊の参考書があり、i番目の参考書はC_i円で、購入するとj番目のアルゴリズムの理解度がA_{ij}上がる。
M個全ての理解度をX以上にすることが可能な場合は最小の費用を、不可能な場合は-1を出力せよ。

  • 入力は全て整数
  • 1 \le N, M \le 12
  • 1 \le X, C_i \le 10^5
  • 0 \le A_{ij} \le 10^5
思考過程
  1. N冊を買うか買わないかの組み合わせは2^N通り。
  2. 制約が小さくてこれで間に合うので全探索する。
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 m = sc.nextInt();
        int x = sc.nextInt();
        int[] c = new int[n];
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt();
            for (int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();

        int ans = Integer.MAX_VALUE;
        int end = 1 << n;
        for (int i = 0; i < end; i++) {
            int[] r = new int[m];
            int sum = 0;
            for (int j = 0; j < n; j++) {
                // 購入する場合
                if ((i >> j & 1) == 1) {
                    // 理解度加算
                    for (int j2 = 0; j2 < m; j2++) {
                        r[j2] += a[j][j2];
                    }
                    // 費用加算
                    sum += c[j];
                }
            }
            // 理解度足りないものがないか判定
            boolean ok = true;
            for (int j2 = 0; j2 < m; j2++) {
                if (r[j2] < x) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans = Math.min(ans, sum);
            }
        }
        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}

一応以下の2^N全探索部分はテンプレ。今ではもう迷わず書けるけど。

        int end = 1 << n;
        for (int i = 0; i < end; i++) {
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                }
            }
        }

ここまで12分00秒＋1ペナ。


D - Teleporter

問題
昔似たような問題に苦戦した気がするので、問題見てちょっと嫌な気持ちになる。
PASTのE（順列）が変に頭に残ってた影響で、例２を試すまで必ず町1に戻ってくると勘違いしていた。

問題概要

1～Nの番号が振られたN個の町がある。
1回の移動で、町i→町A_iに移動する。
町1から出発してちょうどK回移動するとどの町に到着するか。

  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i \le N
  • 1 \le K \le 10^{18}
思考過程
  1. Kが大きいのでシミュレーションは無理。
  2. 最悪でもN回移動すれば町1に戻ってくるので、それまでをシミュレーションし、周期を求めたくなる。　→町1ではなく、これまでに訪れたどれかの町だった。つまり、例１のように最初から周期に入っているとは限らず、例２のように途中から周期に入る場合があることがわかる。
  3. シミュレーションの記録として、「B_i：i回目の移動で訪れた町」を残しておこうとしていたが（B_Kがそのまま答えなので）、どの町を再訪するかわからず、再訪した時に周期L（現在の移動回数-前回訪れたときの移動回数）が知りたいので、「C_i：町iを訪れたときの移動回数」を残すように方針を変える。
  4. 上記のBを、「B_{i\%L}：i回目の移動で訪れた町」に置き換えることを考えると、周期に入った後も十分に（周期に入る前の長さ分）シミュレーションを進めると、Bが更新されない状態になる。
  5. 周期に入った後であればB_{K\%L}が答えになるが、周期前とかの場合分けがまだ必要。
  6. 周期前については、周期を見つけるまでのシミュレーションの時点でK回に達したらその時点で終了することにする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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]);
        long k = Long.parseLong(sa[1]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        int[] c = new int[n];
        Arrays.fill(c, -1);
        int now = 0; // ≒考察中のB_i
        c[now] = 0;
        int loop = 0; // 周期
        int in = 0; // 周期に入り始める町
        for (int i = 1; i <= n; i++) {
            now = a[now];
            // シミュレーション中にK回に達した場合
            if (i == k) {
                System.out.println(now + 1);
                return;
            }
            // 町を再訪したとき
            if (c[now] != -1) {
                in = now;
                loop = i - c[now];
                break;
            }
            c[now] = i;
        }

        int m = (int) (k % loop);
        boolean flg = false;
        now = 0;
        for (int i = 1; i <= k; i++) {
            now = a[now];
            if (now == in) {
                flg = true;
            }
            // 周期に入った後 かつ 移動回数%周期＝K%周期
            if (flg && i % loop == m) {
                System.out.println(now + 1);
                return;
            }
        }
    }
}

ちょうどPASTのO問題を受けてダブリングを使ったLCAをやりかけていたところでもあったので、ダブリング解も思いつきたかった。
ここまで30分26秒＋1ペナ。
この時点でのパフォ見込みが1200～1300くらい。


E - Colorful Blocks

問題
20～30分迷走した末、順位表見たら既にE問題は500人くらいは解いていてだいぶ出遅れており、F問題は100人程度で最終的には数百人解きそう（全く歯が立たない難しさではなさそう）だったので、中断してFを見てみることに。
Fに行く前のことはあまり覚えてないので、以下の思考過程はFを解いて戻った後の内容がメインになります。

問題概要

N個のブロックが横一列に並んでいる。
以下の条件を満たすブロック列の塗り方が何通りあるか。

  • 各ブロックを色1～Mのいずれかで塗る。
  • 同じ色で塗られている隣り合うブロックの組がK個以下。

998244353で割った余りを出力する。

  • 1 \le N, M \le 2 \times 10^5
  • 0 \le K \le N-1
思考過程
  1. 条件2つ目を無視した色の塗り方は全部でM^N通り。K個より多い場合を求めて全体から引くことも一応頭の片隅に。
  2. 例えば同じ色を3組作る場合でも、連続すれば4ブロックだし離せば6ブロックだしでどうすれば？
  3. 前から順に色を決めていくとすると、組のところの左側は何色でもよくて、右側が1色に限定されると思えば、連続しているか離れているかは関係ない。
  4. 前と同じ色にする箇所を決めて数えてみる？
  5. 例えばN=4くらいで作る組数ごとに数えてみると、先頭は何色でもよいのでM通り、前と同じ色にするところは1通り、異なる色にするところはM-1通りとなり、以下の表で横に掛け算したものの総和を求めればよいことがわかる。
  6. 組数iごとに、前と同じ色（1通り）となる箇所の取り方が_{N-1}C_i通りとなるため、答えは\sum_{i=0}^K _{N-1}C_i M(M-1)^{N - 1 - i}となる。

組数＼index 1 2 3 4
0 M M-1 M-1 M-1
1 M 1 M-1 M-1
M M-1 1 M-1
M M-1 M-1 1
2 M 1 1 M-1
M 1 M-1 1
M M-1 1 1
3 M 1 1 1 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

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]);
        br.close();

        int mod = 998244353;
        NCR ncr = new NCR(n, mod);
        long ans = 0;
        for (int i = 0; i <= k; i++) {
            long v1 = ncr.calc(n - 1, i);
            long v2 = power(m - 1, n - 1 - i, mod);
            long val = v1 * m % mod * v2 % mod;
            ans += val;
            ans %= mod;
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }

    static class NCR {
        long[] p, pi;
        int m;

        public NCR(int n, int mod) {
            n++;
            m = mod;
            p = new long[n];
            pi = new long[n];
            p[0] = 1;
            pi[0] = 1;
            for (int i = 1; i < n; i++) {
                p[i] = p[i - 1] * i % m;
            }
            pi[n - 1] = BigInteger.valueOf(p[n - 1])
                    .modInverse(BigInteger.valueOf(m)).longValue();
            for (int i = n - 1; i > 1; i--) {
                pi[i - 1] = pi[i] * i % m;
            }
        }

        public long calc(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[r] % m * pi[n - r] % m;
        }
    }
}

終わってみれば、本質部分は10行程度しかなかった・・。
F問題から戻った後急に上記の表が書け、10分ほどでAC。


F - Bracket Sequencing

問題
似たような問題をやったことがあったので、初めからどう貪欲するかばかり考えていた。中途半端に記憶があって雑であったし、4完で残り時間が少なかった焦りもあり、最終的に通れば何でもいいやとペナルティを重ねた。
以下の思考過程もちゃんとした証明とは程遠いと思います。

問題概要

'('、 ')' からなる空でない文字列S_iがN個与えられる。
S_i全てを好きな順序で連結するとき、括弧の対応が取れた文字列を構成できる場合は"Yes"、できない場合は"No"を出力せよ。

  • 1 \le N \le 10^6
  • S_iの文字列長の合計は10^6以下
思考過程
  1. '(' を+1、')' を-1とすると、総和が0かつ、途中で負にならない順序で並べられるかという問題になる。
  2. 最初に並べる1つについて考えると、その中で負になるともうアウト。各文字列について、初期値0としたときの最低到達点と最終到達点を知りたくなる。
  3. 初期値、最小値、最終値のみに注目すると、文字列を並べていくことは、二次元平面上でV字型のグラフを連結していくことと同様になり、N個全てについて最小値の部分が0以上である必要がある。
  4. 前半は最終値が正であるものを消化していきたいが、負になるとアウトという都合上、最終値が正の中でV字の凹みが小さいもの（つまり最小値の大きいもの）から消化するのが最適になりそう。
  5. とりあえず、最小値の降順→最終値の降順でソートし、前から順に最終値が0以上で最小値部分が負にならないものを消化していく。
  6. 後半は、順番を保ったまま、上記の処理で残ったものを順に見ていって負にならなければ"YES"？　→WA。
  7. よくわからないので、情報を得るため、例外を投げてみたりもする。
  8. 上記5.で残った最終値0以上を改めて消化し、負になるなら今度は"No"を出力。
  9. 後半は、V字の凹みが大きいものから消化していくべきな気がするので、残りを最小値の昇順にしてみる。　→AC数2ケースくらいしか増えず。
  10. 後半について前半の逆をちゃんと考えると、凹みの大きさは、初期値ではなく最終値から下がっている量なので、「最終値-最小値」の降順だった。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
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));
        int n = Integer.parseInt(br.readLine());
        char[][] s = new char[n][];
        for (int i = 0; i < n; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        Obj[] arr = new Obj[n];
        int total = 0;
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            int cnt = 0;
            for (int j = 0; j < s[i].length; j++) {
                if (s[i][j] == '(') {
                    cnt++;
                } else {
                    cnt--;
                    o.min = Math.min(o.min, cnt);
                }
            }
            o.cnt = cnt;
            arr[i] = o;
            total += cnt;
        }
        // 総和≠0の場合
        if (total != 0) {
            System.out.println("No");
            return;
        }

        // 最小値の降順→最終値の降順
        Arrays.sort(arr, (o1, o2) -> {
            if (o1.min != o2.min) {
                return o2.min - o1.min;
            }
            return o2.cnt - o1.cnt;
        });

        // とりあえず途中で負にならず、最終値が0以上のものを消化
        // ※本当はここの処理は不要で、次のブロックだけで足りている
        Queue<Obj> que = new ArrayDeque<>(); // 消化保留分を格納
        int now = 0;
        for (Obj o : arr) {
            if (now + o.min >= 0 && o.cnt >= 0) {
                now += o.cnt;
            } else {
                que.add(o);
            }
        }

        // 最終値が0以上のものを全て消化。今度は判定込み
        List<Obj> list = new ArrayList<>(); // 消化保留分を格納
        while (!que.isEmpty()) {
            Obj o = que.poll();
            if (now + o.min < 0) {
                System.out.println("No");
                return;
            }
            if (o.cnt >= 0) {
                now += o.cnt;
            } else {
                list.add(o);
            }
        }

        // 「最終値 - 最小値」の降順
        Collections.sort(list, (o1, o2) -> (o2.cnt - o2.min) - (o1.cnt - o1.min));
        for (Obj o : list) {
            if (now + o.min < 0) {
                System.out.println("No");
                return;
            }
            now += o.cnt;
        }
        System.out.println("Yes");
    }

    static class Obj {
        int min, cnt;
    }
}

E問題を飛ばしてここまで84分24秒＋6ペナ。
1500位くらいから一気に300位以内まで上がる。これで落ち着きを取り戻したからE問題も解けたのかも。