Hi all, Atcoder Beginner Contest 132 was today. Atcoder only publishes Japanese editorials for beginner contests, so I wrote an unofficial English editorial. Hope it helps!

A: Fifty-Fifty

After sorting the input, a "good" string will look like "AABB". Therefore, we simply sort and check for this format.

char[] s = in.next().toCharArray();
Arrays.sort(s);
out.println(s[0] == s[1] && s[2] == s[3] && s[1] != s[2] ? "Yes" : "No");

B: Ordinary Number

It suffices to simply check every range of 3 and see if its middle element should be counted. A simple way is to sort each range of 3 and check that the middle element remains in the middle.

Runtime: $$$\mathcal{O}(n)$$$.

int n = in.nextInt();
int[] p = new int[n];
for (int i = 0; i < n; i++)
    p[i] = in.nextInt();

int answer = 0;
for (int i = 1; i + 1 < n; i++) {
    int[] x = {p[i - 1], p[i], p[i + 1]};
    Arrays.sort(x);
    if (p[i] == x[1])
        answer++;
}
out.println(answer);

C: Divide the Problems

If we first sort the problems by difficulty, the necessary condition is equivalent to "the first half of the problems will be for ABCs, and the second half will be for ARCs". If we assign $$$B$$$ to the hardest ABC problem (problem $$$(N/2)$$$, after sorting) and $$$R$$$ to the easiest ARC problem (problem $$$(N/2+1)$$$, after sorting), we need to select $$$K$$$ such that $$$B < K \le R$$$.

Therefore, we have $$$R-B$$$ choices for K. (Note: if $$$R$$$ and $$$B$$$ are equal, there is no choice of $$$K$$$ that splits the problems in half.)

Runtime: $$$\mathcal{O}(N \log N)$$$.

int n = in.nextInt();
Integer[] d = new Integer[n];
for (int i = 0; i < n; i++)
    d[i] = in.nextInt();

Arrays.sort(d);
out.println(d[n / 2] - d[n / 2 - 1]);

D: Blue and Red Balls

In order for Takahashi to take exactly $$$i$$$ moves, we need $$$i$$$ separate "buckets" of blue balls. Let us say we have $$$R = N-K$$$ red balls and $$$B = K$$$ blue balls. Then, we may separately compute $$$X$$$ as the number of ways to order the $$$R$$$ red balls and the $$$i$$$ buckets of blue balls, and compute $$$Y$$$ as the number of ways to distribute the $$$B$$$ blue balls into the $$$i$$$ buckets. The output for $$$i$$$ moves is then $$$X \cdot Y$$$.

Let us compute $$$X$$$. If we imagine the $$$R$$$ red balls already in a row, there are $$$R+1$$$ spaces to put a bucket of blue balls (it can go left of all the balls, right of all the balls, or in the $$$R-1$$$ gaps between consecutive red balls). Therefore, $$$X = \binom{R+1}{i}$$$.

Let us now compute $$$Y$$$. To distribute $$$B$$$ blue balls into $$$i$$$ buckets, we can imagine all the blue balls in a row and insert $$$i-1$$$ dividers into the $$$B-1$$$ spaces between the balls to separate them into buckets. Therefore, $$$Y = \binom{B-1}{i-1}$$$.

Note: computing binomial coefficients can be done for this problem either by precomputing Pascal's Triangle in $$$O(N^2)$$$ time or by precomputing factorials and their inverses, since $$$N \le 2000$$$.

int n = in.nextInt(), k = in.nextInt();

int r = n - k, b = k;
Mod107 m = new Mod107();

for (int i = 1; i <= k; i++) {
   ModularNumber<Mod107> x = m.ncr(r + 1, i);
   ModularNumber<Mod107> y = m.ncr(b - 1, i - 1);
   out.println(x.mult(y));
}

E: Hopscotch Addict

Repeating ken-ken-pa $$$k$$$ times corresponds to following a path of length exactly $$$3k$$$ in the graph. Therefore, we need to find the shortest path from $$$S$$$ to $$$T$$$ whose length is a multiple of 3.

In order to solve this, we create a new graph $$$G'$$$ with $$$3N$$$ vertices and $$$3M$$$ edges. For each vertex $$$v_i$$$ in the original graph $$$G$$$, we create three vertices $$$v_0$$$, $$$v_1$$$, and $$$v_2$$$ in $$$G'$$$. For every edge $$$(u, v)$$$ in $$$G$$$, we create edges $$$(u_0, v_1)$$$, $$$(u_1, v_2)$$$, and $$$(u_2, v_0)$$$ in $$$G'$$$.

In this way, a path from $$$u_i$$$ to $$$v_j$$$ in $$$G'$$$ corresponds to a path in $$$G$$$ whose length is congruent to $$$j-i \text{ (mod 3)}$$$.

Therefore, we can run a BFS on $$$G'$$$ to find the shortest path from $$$S_0$$$ to $$$T_0$$$, which corresponds to the shortest path with length a multiple of 3 in $$$G$$$. If we find such a path, we simply divide its length by 3 to get the number of ken-ken-pa.

Runtime: $$$\mathcal{O}(N + M)$$$.

int n = in.nextInt();
int m = in.nextInt();

List<Integer>[] adj = new List[3 * n];
for (int i = 0; i < 3 * n; i++) {
    adj[i] = new ArrayList<>();
}

for (int i = 0; i < m; i++) {
    int u = in.nextInt() - 1;
    int v = in.nextInt() - 1;

    // Create G'
    adj[u].add(v + n);
    adj[u + n].add(v + 2 * n);
    adj[u + 2 * n].add(v);
}

// BFS from s to t
int s = in.nextInt() - 1, t = in.nextInt() - 1;
Queue<Integer> q = new ArrayDeque<>();
q.add(s);
BitSet visited = new BitSet();
visited.set(s);
int[] dist = new int[3 * n];
dist[s] = 0;
while (!q.isEmpty()) {
    int cur = q.poll();
    for (int next : adj[cur]) {
        if (visited.get(next))
            continue;

        visited.set(next);
        dist[next] = dist[cur] + 1;
        q.add(next);
    }
}

// Divide path length by 3 to get number of ken-ken-pa.
out.println(visited.get(t) ? dist[t] / 3 : -1);

F: Small Products

Let's divide the numbers from $$$1$$$ to $$$N$$$ into "small" and "big" numbers. We call "small" numbers those that are at most $$$\sqrt{N}$$$, and "big" numbers those that are greater than $$$\sqrt{N}$$$.

This means that any two small numbers can be adjacent, and no two big numbers can be adjacent. When putting a small number $$$s$$$ and a big number $$$b$$$ adjacent, we require $$$s \cdot b \le N$$$.

Thus, we can split the possible values of $$$b$$$ into $$$\sqrt{N}$$$ buckets $$$B_i$$$ based on the maximal small number they can be paired with (for example, if $$$N=10$$$, the big numbers $$$4$$$ and $$$5$$$ can be paired with the small number $$$2$$$, but not with $$$3$$$, so they would go in $$$B_2$$$).

When we have built a partial sequence, we only care about the last value in the sequence when deciding how to build the rest of the sequence. Moreover, we actually only care about the $$$2\sqrt{N}$$$ categories the last element can fall into (either a small number or a bucket of big numbers).

Let $$$s(i, j)$$$ be the number of sequences of length $$$i$$$ ending with a small number $$$j$$$. Let $$$b(i, j)$$$ be the number of sequences of length $$$i$$$ ending with a big number in $$$B_i$$$.

A small number $$$j$$$ can be placed after any other small number, or after a big number in $$$B_k$$$ where $$$k \ge i$$$.

$$$\displaystyle s(i,j) = \sum_{k=1}^{\sqrt{N}} s(i-1,k) + \sum_{k=j}^{\sqrt{N}} b(i-1,k)$$$

A big number $$$j$$$ can be placed after any small number $$$k \le j$$$. We have $$$|B_j| = \frac{N}{j} - \frac{N}{j+1}$$$ possibilities for this big number.

$$$\displaystyle b(i,j) = \left( \frac{N}{j} - \frac{N}{j+1} \right) \sum_{k=1}^{j} s(i-1,k)$$$

This directly leads to an $$$\mathcal{O}(k \sqrt{N}^2)$$$ dynamic programming solution, which can be sped up to $$$\mathcal{O}(k \sqrt{N})$$$ by precomputing $$$\sum_{k=1}^j s(i-1,j)$$$ and $$$\sum_{k=j}^{\sqrt{N}} b(i-1,k)$$$ for all j, after we compute everything for $$$i-1$$$ and before we compute everything for $$$i$$$.

Runtime: $$$\mathcal{O}(k \sqrt{N})$$$.

long n = in.nextLong();
int k = in.nextInt();

// sqrtN is the smallest number that when squared is greater than n
int sqrtN = (int) BinarySearch.binarySearchLong(i -> i * i > n);

// dpSmall[i][j] is the number of sequences of length i where the last number is j.
long[][] dpSmall = new long[k + 1][sqrtN];
// dpBig[i][j] is the number of sequences of length i where the last number is in bucket B_j.
long[][] dpBig = new long[k + 1][sqrtN];

// The first number can be anything, which we represent by having exactly 1 seq of length 0 that
// "ends" with 1.
dpSmall[0][1] = 1;

for (int i = 0; i < k; i++) {
    for (int j = 1; j < sqrtN; j++) {
        dpSmall[i][j] += dpSmall[i][j - 1];
        dpSmall[i][j] %= MOD;
    }
    for (int j = sqrtN - 2; j > 0; j--) {
        dpBig[i][j] += dpBig[i][j + 1];
        dpBig[i][j] %= MOD;
    }

    // now dpSmall[i][...] is replaced by partial sums
    // now dpBig[i][...] is replaced by partial sums

    for (int j = 1; j < sqrtN; j++) {
        // If the previous number is anything <= j, we have (n/j - n/(j+1)) choices for this number.
        dpBig[i + 1][j] = dpSmall[i][j] * (n / j - n / (j + 1));

        // We don't want to count a number in dpBig that could be paired with itself, because
        // it's already in dpSmall.
        if (j == n / j)
            dpBig[i + 1][j] = 0;

        dpBig[i + 1][j] %= MOD;
    }
    for (int j = 1; j < sqrtN; j++) {
        // If we are adding a small number, we can add it to any sequence ending with a sufficiently small
        // big number, or any sequence at all ending with a small number.
        dpSmall[i + 1][j] = dpBig[i][j] + dpSmall[i][sqrtN - 1];
        dpSmall[i + 1][j] %= MOD;
    }
}

long answer = 0;
for (long x : dpSmall[k]) {
    answer += x;
    answer %= MOD;
}
for (long x : dpBig[k]) {
    answer += x;
    answer %= MOD;
}

out.println(answer);

Thanks for reading! Let me know if you have any questions or feedback for me.