Educational Codeforces Round 80 A から E

A. Deadline

x と d/(x+1) が近いほど値が小さくなりそうなので d の正の平方根の前後を 100000 くらいを探したんだけど、これやるなら 1 から 1000000 を全探索で良かった。

B. Yet Another Meme Problem

b の桁数を L だと仮定する。そうすると与えられた条件は $ab + a + b = a \cdot 10^L + b$ と言い換えられる。式変形すると $a(b+1-10^L)=0$ となる。$a$ は零でないため $b+1-10^L=0$ である。つまり $b=10^L - 1$ である。$b=10^L - 1$ とすると確かに $L$ 桁になっているから、これは解である。$L$ としてありうるものは 1 から 10 しかないため、すべて探しても間に合う。なお各 $b$ に対して $a$ は任意であるから、$b$ としてありうる場合の数に A を掛けたものが答えになる。

C. Two Arrays

これは本番自分が思いついた方法とは異なる。b を反転して a の後ろにつければ、この問題は長さ 2m の数列を数え上げる問題に言い換えられる。これは C(2m+n-1,n-1) 通りある。

D. Minimax Problem

最大値を $x$ 以上にできるかを二分探索する。i 番目の数列に対して集合 $S_i$ を $A_{i,j}$ が $x$ 以上となる $j$ 全体とする。$S_i$ と $S_j$ の和集合が $\{1,2,\ldots,m\}$ となれば i と j は答えである。$S_i$ としてありうるものは 256 通りしかないため、$S_i$ を 256 通り確かめればよい。

E. Messenger Simulator

ある人に着目する。この人を赤い人と呼ぶ。また添字を身長に対応させる。履歴を古いものから新しいものの順で見ていき $n$ 回赤い人が現れたとする。最大値となる候補は履歴に現れる時点か終了時点しかないことに気をつける。1 回目では、履歴の先頭からいままでに赤い人よりも身長の高い人が現れた回数だけ後ろに下がっているはずである。k 回目では、k - 1 回目から k 回目までに現れた人の数だけ先頭から後ろに下がるはずである。

以上を踏まえると、数列のある区間の値の種類数がわかれば解けることがわかる。うまくやると点更新区間和だけで解ける。