Codeforces AIM Tech Round 3 (Div. 1) B. Recover the String

問題概要

ある文字列があり、その文字列の部分列（連続でなくてもよい）のうち 00, 01, 10, 11 となるものの個数がそれぞれ与えられる。このような文字列をどれでもいいので 1 つ出力せよ。存在しないなら Impossible を出力せよ。

解法

00, 01, 10, 11 の個数をそれぞれ $n_{00}$, $n_{01}$, $n_{10}$, $n_{11}$ とする。

$n_{00}$ の個数は 0 の個数にのみ依存し、01 の並びには依存しない。このことを使えば元の文字列の 0 の個数が分かる。元の文字列が持つ 0 の個数を $n_0$, 1 の個数を $n_1$ とすると以下の条件を満たす。

$$\frac{n_0(n_0-1)}{2}=n_{00}, \quad \frac{n_1(n_1-1)}{2}=n_{11}$$

このような $n_0$, $n_1$ が存在しない場合は Impossible である。

0,1 の個数が分かったので $\underbrace{0\ldots0}_{n_0}\underbrace{1\ldots1}_{n_1}$ という文字列を試しに作ってみる。このとき 01 の個数は $n_0n_1$ で、10 の個数は 0 である。0,1 の並びを変えても 01 の個数と 10 の個数の総和は変わらないため、$n_0n_1=n_{01}+n_{10}$ でない場合は Impossible である。

成り立つのであれば、1 を左にずらす操作を繰り返すことで目的の文字列が得られる。なぜなら、1 を左にずらすと 01 の個数が -1、10の個数が +1 するからである。

文字列の長さは $\sqrt{10^9}$ 程度あるので、愚直に 1 ずらすと $10^9$ 回程度のループが回ってしまう。と言っても対処するのは難しくなくて、1 を一気に左端に持っていけばいい。

注意するべきなのは、0 が一個しかない場合と、1 が一個しかない場合である。01111 とか 0010 とかがきちんと判定できるか確かめよう。

0 0 0 0 も見落としがちで 0 または 1 が答えになる。

コーナーケースばかり気にして、計算量のことをまったく気にしてなかったので TLE してしまった。計算量の見積もりミス、この手のものをやり始めてから初めてやったかもしれない。