No.1694 ZerOne

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 :

eSeF / テスター :

chineristAC 👑

ygussany

12 ProblemId : 5360 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-09-29 17:46:11

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

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

$S$

【制約】

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

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

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

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

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

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