AtCoder Beginner Contest 141 has just finished, and this is an unofficial editorial.

You can check my solutions, but I used lots of defines in my codes, and they're hard to read.

C — Attack Survival

Let $$$cnt[i]$$$ be the number of times the player $$$i$$$ correctly answered a question. The player $$$i$$$ survived if and only if $$$q-cnt[i]<k$$$.

D — Powerful Discount Tickets

First, you have to know $$$\left\lfloor\frac{x}{2^k}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac x 2\right\rfloor}{2^{k-1}}\right\rfloor$$$(when both $$$x$$$ and $$$k$$$ are positive integers and $$$k\ge 1$$$).

In fact, it is true that $$$\left\lfloor\frac{\left\lfloor\frac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\frac{x}{yz}\right\rfloor$$$ (when $$$x$$$, $$$y$$$, $$$z$$$ are all positive integers).

Because of this, we can use a single ticket $$$k$$$ times instead of use $$$k$$$ tickets at one time.

Then, we can use a heap (or priority_queue) to maintain all the prices, each time choose the most expensive item, and use a ticket for it.

E — Who Says a Pun?

If we enumberate the split point, it will become a Longest Common Substring Problem.

For example, if we split the string into $$$[1,mid)$$$ and $$$[mid,n]$$$, we need to calculate the LCS of them, and the answer is the maximum LCS among all possible splits.

I used suffix automaton to solve it.

You can also use DP to solve it:

Let $$$f_{i, j}$$$ be the longest length if the first substring starts from $$$i$$$ and the second one starts from $$$j$$$.

$$$f_{i,j}=\begin{cases}0&s[i]\ne s[j]\\min(j-i,f_{i+1,j+1})&s[i]=s[j]\end{cases}$$$

The answer is the maximum value of all $$$f_{i,j}$$$.

F — Xor Sum 3

Consider each bit separately. Let $$$cnt[i]$$$ be the number of "1"s in the $$$i$$$-th bit (the bit of $$$2^i$$$), if $$$cnt[i]$$$ is odd, the sum of this bit is definitely $$$1$$$.

So, we only have to consider the bits with even number of "1"s. If the XOR of the red integers of a bit is $$$1$$$, then the blue one is also $$$1$$$; otherwise they are both $$$0$$$.

So, we have to maximize the XOR of either the red integers or the blue integers (only consider the bits with even number of "1"s), that's to say, find the maximum subset XOR of a given set.