キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)(Rated範囲外)

A - Discount
- 思考過程
B - Play Snuke
- 思考過程
C - Unexpressed
- 思考過程
D - Poker
- 思考過程
E - Oversleeping
- 思考過程
F - Zebraness
- 思考過程

コンテスト前のレート：2029
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：307位（1500点、82分33秒）

レートが2000以上になってUnratedになったので、適当にD問題くらいからやってみようとするが、すぐにわかりそうになかったので結局前から解くことに。
出遅れただけになったかも。

A - Discount

思考過程

値引き額は $A-B$ 。
これを定価 $A$ で割って $100$ を掛ける。（ $100.0$ とすることでdouble型に変換する）

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

        System.out.println(100.0 * (a - b) / a);
    }
}

ここまで2分43秒＋0ペナ。2894位。
開始3分でもう全参加者の内4割くらいの人が通してるのね・・・。

B - Play Snuke

問題

思考過程

境界が一瞬ではわかりにくいが、例１により、 $A_i \lt X_i$ であれば買えることがわかる。
条件を満たす中で $P_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[] p = new int[n];
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            p[i] = sc.nextInt();
            x[i] = sc.nextInt();
        }
        sc.close();

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (a[i] < x[i]) {
                ans = Math.min(ans, p[i]);
            }
        }
        if (ans == Integer.MAX_VALUE) {
            ans = -1;
        }
        System.out.println(ans);
    }
}

ここまで5分18秒＋0ペナ。966位。

C - Unexpressed

問題

思考過程

全ての $N$ について調べるには制約が大きいので無理。
作れる値だけ全探索しようとすると、 $a$ は $\sqrt{N}$ まで調べればよく、 $b$ は $a=2$ の場合でも $30$ そこそこくらいにしかならない。
全探索すると作れる値に重複が出るので、Setに格納して重複排除する。答えは $N-$ Setのサイズ。
$a^b$ の計算は、power関数を貼ってもよかったが、 $a$ を掛けてはSetに入れるのを繰り返すのが無駄がない。
ループの始め方や抜け方などを間違えて、 $0$ 乗や $1$ 乗を追加したり、 $N$ より大きい値を追加したりしないように注意する。

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);
        long n = sc.nextLong();
        sc.close();

        Set<Long> set = new HashSet<>();
        for (long a = 2; a * a <= n; a++) {
            long v = a;
            while (true) {
                v *= a;
                if (v <= n) {
                    set.add(v);
                } else {
                    break;
                }
            }
        }
        System.out.println(n - set.size());
    }
}

ここまで10分05秒＋0ペナ。462位。

D - Poker

問題

思考過程

高橋くんと青木くんそれぞれについて、 $1$ ～ $9$ を引いた時の＜点数、その点数になる確率＞のマップを前計算しておき、高橋くん側の各点数について、青木くん側でより小さいキーを持つエントリの値の合計を求めるような感じ？と思ったりもしたが、残り $1$ 枚しかない値を $2$ 人とも取ってしまう場合も発生しそうで意味不明になる。
　
$9 \times 9$ 通り全部調べ、点数の条件を満たす場合に、発生確率を答えに足していくことにする。
まず、点数計算する部分を関数化して見通しを良くする。
　
発生確率は、便宜上先に高橋くんがカードを引くとすると、「数値 $i$ の残り枚数（以下 $ra$ ）／全体の残り枚数（以下 $ta$ ）」となり、 $ra$ は $4$ 枚目までをカウントして求めることができ、 $ta$ は $9K-8$ 。
後に引く青木くんの方は、数値 $j$ の残り枚数には $i$ も考慮し、全体の残り枚数は $ta-1$ 。
高橋くんが $i$ かつ青木くんが $j$ の発生確率は、上記4.と5.の掛け算。

import java.util.Scanner;

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

        int ta = k * 9 - 8; // 高橋くんが引くときの全体の残り枚数
        int tb = ta - 1;    // 青木くんが引くときの全体の残り枚数
        int[] a = new int[10]; // 高橋くんの手札
        int[] b = new int[10]; // 青木くんの手札
        for (int i = 0; i < 4; i++) {
            a[s[i] - '0']++;
            b[t[i] - '0']++;
        }

        double ans = 0;
        for (int i = 1; i <= 9; i++) {
            int ra = k - a[i] - b[i]; // 数値iの残り枚数
            if (ra == 0) {
                continue;
            }
            a[i]++;
            int va = calc(a); // 高橋くんの点数
            double pa = (double) ra / ta; // 高橋くんがiの確率
            for (int j = 1; j <= 9; j++) {
                int rb = k - a[j] - b[j]; // 数値jの残り枚数
                if (rb == 0) {
                    continue;
                }
                b[j]++;
                int vb = calc(b); // 青木くんの点数
                double pb = (double) rb / (tb); // 青木くんがjの確率
                b[j]--;
                if (va > vb) {
                    ans += pa * pb;
                }
            }
            a[i]--;
        }
        System.out.println(ans);
    }

    static int calc(int[] a) {
        int ret = 0;
        for (int j = 1; j <= 9; j++) {
            int v = j;
            for (int j2 = 0; j2 < a[j]; j2++) {
                v *= 10;
            }
            ret += v;
        }
        return ret;
    }
}

ここまで29分38秒＋0ペナ。364位。

E - Oversleeping

問題
Dを解いた後は、EとFを行ったり来たり。
どちらかと言えばF重視でやっていたが、完全に行き詰ったのでEに集中することにした。

思考過程

街 $B$ にいるという条件を満たす $t$ は、 $X \leq t \lt X+Y$ $(mod (2X+2Y))$ 。
起きているという条件を満たす $t$ は、 $P \leq t \lt P+Q$ $(mod (P+Q))$ 。
なんとなく中国剰余定理（CRT）のような雰囲気を感じる。
範囲を指定することはできないので、 $Y \times Q$ 通り全通り試してみる。サンプルが通ったので提出。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();

            int a = x * 2 + y * 2;
            int b = p + q;
            long ans = Long.MAX_VALUE;
            for (int j = 0; j < y; j++) {
                for (int j2 = 0; j2 < q; j2++) {
                    long[] res = crt(new long[] { x + j, p + j2 }, new long[] { a, b });
                    if (res[1] != 0) {
                        ans = Math.min(ans, res[0]);
                    }
                }
            }
            if (ans == Long.MAX_VALUE) {
                System.out.println("infinity");
            } else {
                System.out.println(ans);
            }
        }
        sc.close();
    }

    // 以下ライブラリ（ACLのcrt）

    static long[] crt(long[] r, long[] m) {
        assert r.length == m.length : "|r|=" + r.length + ", |m|=" + m.length;

        int n = r.length;
        long r0 = 0, m0 = 1;
        for (int i = 0; i < n; i++) {
            assert 1 <= m[i] : "m[" + i + "]=" + m;

            long r1 = r[i] % m[i];
            if (r1 < 0) {
                r1 += m[i];
            }
            long m1 = m[i];
            if (m0 < m1) {
                long tmp = r0;
                r0 = r1;
                r1 = tmp;
                tmp = m0;
                m0 = m1;
                m1 = tmp;
            }
            if (m0 % m1 == 0) {
                if (r0 % m1 != r1) {
                    return new long[] { 0, 0 };
                }
                continue;
            }

            long[] ig = invGcd(m0, m1);
            long g = ig[0], im = ig[1];
            long u1 = m1 / g;
            if ((r1 - r0) % g != 0) {
                return new long[] { 0, 0 };
            }

            long x = (r1 - r0) / g % u1 * im % u1;
            r0 += x * m0;
            m0 *= u1;
            if (r0 < 0) {
                r0 += m0;
            }
        }
        return new long[] { r0, m0 };
    }

    private static long[] invGcd(long a, long b) {
        a = a % b;
        if (a < 0) {
            a += b;
        }
        if (a == 0) {
            return new long[] { b, 0 };
        }

        long s = b, t = a;
        long m0 = 0, m1 = 1;
        while (t > 0) {
            long u = s / t;
            s -= t * u;
            m0 -= m1 * u;
            long tmp = s;
            s = t;
            t = tmp;
            tmp = m0;
            m0 = m1;
            m1 = tmp;
        }
        if (m0 < 0) {
            m0 += b / s;
        }
        return new long[] { s, m0 };
    }
}

ここまで62分27秒＋0ペナ。191位。

F - Zebraness

問題
解けず。
辺の張り方どころか、フローだと全く気付かなかった。

思考過程

DPをしようとしたら、例３が駄目。1つ左と上のマスを見るだけでは正しいDPができない。正しくやろうとすれば、多分2行分くらいの $O(2^N)$ とかのデータを持つ必要はありそうなので無理。
実はほぼ貪欲だったりするか？と思い、とりあえず?を全部Bで埋めた後、周囲の数がB $\gt$ WだったらWに変え、連鎖的に変えるべきマスが発生しないかBFSで調べる。といったことをした結果、サンプルは通ったが半分ほどのケースでWA。

最終結果：ABCDEの5完、62分27秒、214位、パフォーマンス2197相当
レート変動：2029（Unrated）

Unratedだしと思って4完で諦めかけていたが、何気に初めてCRTを使って本番中ACができたのは良かった。
F問題で全く見当違いのことをしている辺り、まだまだACLは使いこなせていないものが多い。
PASTにも出ることがあるようだし、フロー系のものは早めに使えるようになりたいと思う。中身の理解は諦めているけど。

今回も青diffを落とさず、2021/1/2のABC187を最後に青diff以下を1問も落とさないのを継続中。
色落ちしないためには、やはり1色下の問題を落とさないことが重要なのだと思う。