ヒント

ヒント 1

条件を満たす長さ $2N$ の文字列は作れますか？

ヒント 1 の答え

$0$ を $2N$ 個並べたものがその例です。

ヒント 2

文字列が $2$ つだったら解けますか？

ヒント 3

なぜこの問題では文字列が $2$ つでなく $3$ つあるのでしょうか？

ヒント 4

$N$ 個の $0$ と $N$ 個の $1$ を含むいかなる長さ $2N$ の文字列 $S$ に対しても $S + S$ の部分列であるような、長さ $2N + 1$ の文字列が存在します。それはどのようなものでしょうか。

ヒント 5

$0\cdot N + 1\cdot N + 0$ が解の一つです。なぜでしょうか。

解法

$N$ 個の $0$ と $N$ 個の $1$ からなるいかなる長さ $2N$ の文字列 $S$ に対しても、$S + S$ は部分列として $0\cdot N + 1\cdot N + 0$ を含みます。

証明

$S$ における $0$ の位置を $a_1, a_2, \dots, a_N$ とすると、$S+S$ における $0$ の位置は
$a_1, a_2, \dots, a_N, a_1, + 2N, a_2 + 2N, \dots, a_N + 2N$

です。よって、$N$ 個目の $0$ と $2N$ 個目の $0$ の距離はちょうど $2N$ であり、これはこの間にちょうど $N$ 個の $1$ があることを意味します。

合計計算量: $O(N)$

補足

これは唯一の解ではありません。上記と同様に、\(A+B = N+1\) であるようないかなる \(1\le A, B\le N\) に対しても、\(0\cdot A + 1\cdot N + 0\cdot B\)（と \(1\cdot A + 0\cdot N + 1\cdot B\)）は解です。 また、\(2N+1\) という制約は可能な上限です。実際、文字列 \(0 \cdot N + 1 \cdot N + 0 \cdot N + 1 \cdot N\) と \((01)\cdot (2N)\) は長さ \(2N+2\) の共通部分列を持たないことが示せます。