問題一覧 > 通常問題

No.1694 ZerOne

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 : eSeFeSeF / テスター : chineristACchineristAC 👑 ygussanyygussany
11 ProblemId : 5360 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-29 17:46:11

問題文

01 からなる文字列 $S$ が与えられます。 以下の操作を $0$ 回以上繰り返して作ることのできる文字列としてありうるものの個数を求めてください。

  • 以下の条件 (1), (2), (3) を満たす $S$ の2つの空でない連続部分列 $t$、$u$ を選び、$S$ 中での位置を交換する。
    • (1): $t$ と $u$ は、重なりの無いように取り出す。 即ち、$t$ が $S$ の $L_t$〜$R_t$ 文字目であり、$u$ が $S$ の $L_u$〜$R_u$ 文字目であるとすると、 $L_t\le R_t < L_u\le R_u$ が成り立つようにする。
    • (2): $t$ に含まれる 0 の数は、$u$ に含まれる 0 の数に等しい。
    • (3): $t$ に含まれる 1 の数は、$u$ に含まれる 1 の数に等しい。

入力

$S$

【制約】

  • $S$ は 01 からなる長さ $1$ 以上 $60$ 以下の文字列

出力

操作を $0$ 回以上行ってできる可能性のある文字列の個数を 1 行に出力せよ。

サンプル

サンプル1
入力
001010
出力
2

例えば、$t=$ 001(1~3文字目)、$u=$ 010(4~6文字目)を選び、 それらの位置を入れ替えると文字列は 010001 になります。

実はこれと初期状態以外の文字列は生成できないので、答えは 2 です。

なお、$t=$ 010(2~4文字目)、$u=$ 010(4~6文字目)とすると、 01 の数は等しいですが $S$ の4文字目がどちらにも含まれているので、(1) を満たさず不適な操作です。

サンプル2
入力
10
出力
1

$t$ と $u$ として選べる文字列の組が存在しないので、操作を行うことができません。

サンプル3
入力
010101
出力
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。