\(16\) 通り全てを考えます。

\((B, C) = (1, 0)\) の場合

\(S\) を反転させ、\(B, C\) を入れ替えても答えが変わりません。よって、このようなケースを除く \(12\) 通りについて考えます。

\((0, 0, 0, 0)\)

文字列 1 のみが美しいです。

\((0, 0, 0, 1)\) (and)

文字列の全ての要素が 1 であるときに限り美しいです。

\((0, 0, 1, 0)\)

結論から言うと、先頭が 1 かつ、110* という形で表現されない文字列に限り美しいです。

まず、先頭が 0 のとき、何回操作しても先頭が 0 になるため、先頭が 1 であることが必要です。

10 で始まっているとき、後ろの文字を適当に処理した後、\(i = 2, 1\) と選べば良いです。

たとえば、111 で始まっているとき、\(i = 2\) を選べば、10 で始まるケースに帰着できます。そのようなケースに帰着できないものは 110* という形で表現されるものに限ります。

\((0, 0, 1, 1)\)

先頭の要素が常に変わらないので、先頭が 1 のものに限り美しいです。

\((0, 1, 1, 0)\) (XOR)

1 の数の偶奇が変わらないので、1 の出現回数が奇数回のものに限り美しいです。

\((0, 1, 1, 1)\) (OR)

文字列の任意の要素が 0 のときは美しくないです。逆にそれ以外の場合は美しいです。

\((1, 0, 0, 0)\) (NOR)

文字列の長さが \(4\) 以上のときは必ず美しいです。 これは、長さ \(4\) の文字列を全探索することでわかります。

文字列の長さが \(3\) 以下のときは全探索すれば良いです。

\((1, 0, 0, 1)\) (XNOR)

問題 D と同様で、0 の出現回数が偶数回のものに限り美しいです。

\((1, 0, 1, 0)\)

長さが \(3\) 以上のときは必ず美しいです。これは、末尾に対する操作回数と最初の末尾の数の和の偶奇で決まることからわかります。

長さが \(2\) 以下のときは全探索すれば良いです。

\((1, 0, 1, 1)\)

結論から言うと、01* という形で表現されない文字列に限り美しいです。

場合分けすればこれが導き出せます。

\((1, 1, 1, 0)\) (NAND)

文字列の長さが \(4\) 以上のときは必ず美しいです。 これは、長さ \(4\) の文字列を全探索することでわかります。

文字列の長さが \(3\) 以下のときは全探索すれば良いです。

\((1, 1, 1, 1)\)

文字列 0 のみが美しい文字列ではないです。

実装例

C++ 148ms