AtCoder Beginner Contest 242(Rated範囲外)

A - T-shirt
- 思考過程
B - Minimize Ordering
- 思考過程
C - 1111gal password
- 思考過程
D - ABC Transform
- 思考過程
E - (∀x∀)
- 思考過程
F - Black and White Rooks
- 思考過程

コンテスト前のレート：2020
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：276位（2100点、94分24秒）

A - T-shirt

思考過程

$X \leq A$ の場合は $100\% (=1)$ 。
$A \lt X \leq B$ の場合は $\frac{C}{B-A}$ 。
$B \lt X$ の場合は $0$ 。

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();
        int x = sc.nextInt();
        sc.close();

        if (x <= a) {
            System.out.println(1);
        } else if (x <= b) {
            System.out.println((double) c / (b - a));
        } else {
            System.out.println(0);
        }
    }
}

ここまで1分42秒＋0ペナ。119位。

B - Minimize Ordering

問題

思考過程

$S$ をchar型配列にしてソートするだけ。

import java.util.Arrays;
import java.util.Scanner;

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

        Arrays.sort(s);
        System.out.println(s);
    }
}

ここまで2分35秒＋0ペナ。90位。

C - 1111gal password

問題
C問題のDPとしては難しいような気もしたけど、4000人以上解いてるしそうでもないのか・・・。

思考過程

「 $DP[i][j]:=i$ 桁目までで最後の桁が $j$ の場合の通り数」とすると、遷移は $j-1, j, j+1$ の和になる。
$j$ について配列の大きさを $0$ ～ $10$ まで取っておけば、余計なif文を減らせる。

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

        int mod = 998244353;
        long[][] dp = new long[n][11]; // 思考過程2
        // 1桁目だけの時点では1～9がそれぞれ1通り
        for (int i = 1; i <= 9; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= 9; j++) {
                // 思考過程1
                dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1];
                dp[i][j] %= mod;
            }
        }

        long ans = 0;
        for (int i = 1; i <= 9; i++) {
            ans += dp[n - 1][i];
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで5分56秒＋0ペナ。66位。

D - ABC Transform

問題
めちゃくちゃややこしい。飛ばしかけたけど、EやFも一見してすぐに解ける気がしなかったので順番通りやっていくことに。

思考過程

とりあえずを"A"文字として書き出してみると、文字列長はになり、文字列長が以上になった後番目の文字はA→B→C→A→のように繰り返していそう。
- A
- BC
- CAAB
- ABBCBCCA
  　
まずは各クエリの $k$ 文字目が $S^{(0)}$ の何文字目を操作していった部分に含まれるかを求める。（以降0-indexedとする）
これは $\frac{k}{2^t}$ 文字目となる。ただし、 $2^t$ がlong型の範囲を超える場合は $0$ 文字目となるように対処する。
$S^{(0)}$ の $a$ 文字目を操作していった部分の何文字目に当たるかは、 $k \% 2^t$ で求められる。
　
次に、 $S^{(0)}$ から毎回 $2$ 文字に置き換わっていく内の前と後どちらの文字をたどっていくと最終的に $b$ 文字目にたどり着けるかを求めたい。
これは $b$ を $2$ 進数にして上の桁から見ていき、 $0$ なら前、 $1$ なら後ろを選んでいけばよさそう。
例えば $b=4=100_{(2)}$ の場合、上記1.ではA→C(後)→A(前)→B(前)とたどれる。
ABCを $012$ に置き換えると、前への遷移は $+1$ 、後への遷移は $+2$ となる。（適宜modを取る）
　
あとは上記1.の通りの繰り返しを考慮するべく、ここまでの操作で $t$ 回に満たなかった分インクリメントする。
$t$ が大きい場合適当に $61$ とかに置き換えていたが、 $mod$ $3$ での値を変えてはいけなかった。

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

        long[] p = new long[63];
        p[0] = 1;
        for (int i = 1; i < p.length; i++) {
            p[i] = p[i - 1] * 2;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            long t2 = k[i];
            if (t[i] < 63) {
                t2 = p[(int) t[i]];
            }

            k[i]--;
            int a = (int) (k[i] / t2); // 3
            long b = k[i] % t2; // 4
            char[] c = Long.toBinaryString(b).toCharArray();
            int d = (int) Math.min(t[i], 60);
            // 10
            if (t[i] > 60) {
                d += t[i] % 3;
            }
            int x = s[a] - 'A';
            for (int j = 0; j < Math.min(c.length, d); j++) {
                // 6～8
                if (c[j] == '0') {
                    x++;
                } else {
                    x += 2;
                }
                x %= 3;
            }
            // 9
            for (int j = c.length; j < d; j++) {
                x++;
                x %= 3;
            }
            pw.println((char) ('A' + x));
        }
        pw.flush();
    }
}

ここまで44分44秒＋0ペナ。722位。

E - (∀x∀)

問題
文字列長の最大を $250000$ と勘違いして $2$ 回RE。
制約が $1 \leq N \leq 10^6$ って書かれていたら間違えなかった気がするけど、変に文章で書かれていたせいか $250000$ ばかり目に付いていた。

思考過程

例えば $S$ の $1$ 文字目が'E'だとすると、 $1$ 文字目が'A'～'D'の文字列は何でもOKとなり、それらは $4$ $\times 26^{\frac{N}{2}-1}$ 通り。（ $4$ は'A'～'D'の $4$ 通りから。 $N$ が奇数の場合は $\frac{N}{2}$ は切り上げ。）
中央の文字 $1$ つ手前までは同様の数え方を繰り返す。
$S$ の中央の文字が'E'だとすると、'A'～'D'については同様に $4 \times 26^0$ とできるが、'E'としたケースについては、実際に $S$ 以下となるかを確認し、OKなら $1$ 加算する。

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());

        int mod = 998244353;
        long[] p = new long[500005]; // 125000程度にしていて2回RE
        p[0] = 1;
        for (int i = 1; i < p.length; i++) {
            p[i] = p[i - 1] * 26 % mod;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            int n = Integer.parseInt(br.readLine());
            char[] s = br.readLine().toCharArray();

            int n2 = (n + 1) / 2;
            long ans = 0;
            // 1, 2
            for (int i = 0; i < n2; i++) {
                int c = s[i] - 'A';
                ans += p[n2 - i - 1] * c;
                ans %= mod;
            }
            // 3
            boolean ok = true;
            for (int i = n2 - 1; i >= 0; i--) {
                if (s[i] < s[n - 1 - i]) {
                    break;
                }
                if (s[i] > s[n - 1 - i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans++;
            }
            ans %= mod;
            pw.println(ans);
        }
        pw.flush();
        br.close();
    }
}

ここまで65分33秒＋2ペナ。557位。

F - Black and White Rooks

問題
解けず。以下途中まで。

思考過程

特定の行に黒と白が混在してはいけないということなので、 $N$ 行ある内の $i$ 行を黒に、 $i2$ 行を白に使うということにする。
すると、行の割り当て方が $_NC_i \times _{N-i}C_{i2}$ 通りとなる。ここまで列についても同様。
$x$ 行 $y$ 列の領域内に $c$ 個の駒を、どの行や列にも $1$ 個以上置くという制約込みで置く方法の通り数を $f(x, y, c)$ とすると、全体として $_NC_i \times _{N-i}C_{i2} \times _MC_j \times _{M-j}C_{j2} \times f(i, j, B) \times f(i2, j2, W)$ を求めればよいことになる。

この $f(x, y, c)$ が求められず。

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 b = Integer.parseInt(sa[2]);
        int w = Integer.parseInt(sa[3]);
        br.close();

        int mod = 998244353;
        Kaijou kai = new Kaijou(2500, mod);
        long ans = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                for (int i2 = 1; i2 <= n - i; i2++) {
                    for (int j2 = 1; j2 <= m - j; j2++) {
                        if (i * j >= b && i2 * j2 >= w) {
                            long v1 = kai.comb(n, i) * kai.comb(n - i, i2) % mod;
                            long v2 = kai.comb(m, j) * kai.comb(m - j, j2) % mod;
                            long v3 = calc(i, j, b, kai, mod);
                            long v4 = calc(i2, j2, w, kai, mod);
                            long val = v1 * v2 % mod * v3 % mod * v4 % mod;
                            ans += val;
                        }
                    }
                }
            }
        }
        ans %= mod;
        System.out.println(ans);
    }

    static long calc(int x, int y, int c, Kaijou kai, int mod) {
        // TODO
        return 0;
    }

    // 以下ライブラリ

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

        public Kaijou(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 comb(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[r] % m * pi[n - r] % m;
        }

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

Gは全然わからず。Exは見てもいない。

最終結果：ABCDEの5完1500点、75分33秒、738位、パフォーマンス1650相当
レート変動：2020（Unrated）

Eのペナがなくても1700台前半、Fまで解けても1900台前半といったところで、Gが解ける必要があるのはなかなか厳しかったと思う。
一応青diffまでは全埋め状態を保つつもりなので、これは必修か・・・。

最近知らなくてどうにもならない問題が青diffということがよくあって辛い。
今年に入ってから完全に灰diffでStreakつなぎしかしてないし、知識を増やすことをしないとやっぱり緩やかに落ちていくんだろうな。