2022/02/26 1633B Minority(少数)
問題本文
文字「0」と「1」のみで構成される文字列sが与えられます。
sの連続する部分文字列を選択し、その文字の厳密な少数派である文字のすべての出現箇所を部分文字列から削除する必要があります。
つまり、部分文字列内の「0」の量が「1」の量よりも厳密に小さい場合は、部分文字列から「0」の出現をすべて削除します。
「1」の量が「0」の量よりも厳密に小さい場合は、「1」の出現をすべて削除します。
数が同じ場合は、何もしないでください。
操作は1回だけ適用する必要があります。
削除できる文字の最大数はいくつですか？
入力
最初の行には、テストケースの数である単一の整数が含まれています。
各テストケースの唯一の行には、文字「0」と「1」のみで構成される空でない文字列sが含まれています。
sの長さはを超えません。
すべてのテストケースでの文字列の全長sは、を超えません。
出力テストケースごとに、1つの整数を出力します。
これは、操作を1回だけ適用した後に削除できる最大文字数です。
テストケースの説明
最初のテストケース「01」では、部分文字列「0」、「1」、または「01」を選択できます。
「0」「0」の量は1であり、「1」の量は0です。ここでは「1」は厳密な少数派であるため、出現するすべての部分文字列から削除されます。
ただし、0個あるので何も変わりません。
'1'についても同じです。
そして、「01」では、「0」と「1」のどちらも同じ 厳密な少数派ではありません。
したがって、何も変わりません。
したがって、文字を削除する方法はありません。
2番目のテストケース「1010101010111」では、部分文字列「10101010101」を選択できます。
5文字の「0」と6文字の「1」が含まれています。
「0」は厳密な少数派です。したがって、すべての「0」を削除できます。
同じ答えを生成する他の部分文字列が存在します。
3番目のテストケース「00110001000」では、部分文字列「011000100」を選択できます。
6文字の「0」と3文字の「1」が含まれています。
「1」は厳密な少数派です。したがって、すべての「1」を削除できます。
回答
https://codeforces.com/blog/entry/99539
可能な限り最大の答えを推定してみましょう。
最良の場合、文字列全体からすべて0またはすべて1を削除できます。
発生が最も少ない方が答えになります。
文字列内の0と1の量が異なる場合、この境界に到達するのは実際には簡単です。文字列全体である部分文字列を選択するだけです。
量が同じ場合、限界に達することは不可能です。
文字列全体を選択しても何も起こりません。
より小さな部分文字列を要求すると、答えが少なくなります。
答えを減らすことができる最小値は1です。
最後の文字を含まない文字列である部分文字列を選択すると、量の1つが1つ減ります。
これにより数が異なり、限界に達します。
全体的な複雑さ：テストケースごとに。
