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.

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, that's to say, find the maximum subarray XOR in a given array.