バイナリ文字列を並べ替えて、指定したインデックス範囲の値を最大化するには？（C/C++）

問題の概要

0と1のみで構成される文字列が与えられ、さらに互いに重ならないM個の区間 [A₁, B₁], [A₂, B₂], …, [A_M, B_M]（A ≤ B）が与えられます。どの2つの区間も交差しません。形式的には、任意の有効な i, j（i ≠ j）に対して、A_i < B_j または B_j < A_i が常に成り立ちます。

この課題では、次の2つの条件を同時に満たすような妥当な並べ替え（順列）を見つけることが求められます。

• M個の与えられた区間に含まれる数値（1）の合計が最大になること。
• 文字列全体が辞書順で最大になること。たとえば「1100」は「1001」よりも辞書順で大きな文字列です。

解き方のポイント

まず、文字列の各位置が何個の区間に覆われているか（被覆数）を調べます。被覆数の多い位置から優先的に「1」を割り当てることで、区間内の合計を最大化できます。その上で、余った「1」はできるだけ先頭に近い位置へ配置することで、文字列全体を辞書順で最大にできます。

入出力例

例1

入力:
11100
2
3 4
5 5

出力:
00111

まず区間 [3, 4] の位置に1を配置し、続いて [5, 5] の位置にも1を配置します。この時点でもう使用できる「1」が残っていないため、完成する文字列は「00111」となります。

例2

入力:
0000111
2
1 1
1 2

出力:
1110000

この例では、まず1番目と2番目の位置に1を置き、与えられた両方の区間の合計を最大化します。その後、「1」がまだ1つ残っているため、それを3番目の位置に配置することで文字列を辞書順で最大にし、並べ替えが完了します。

まとめ

この問題は貪欲法（グリーディ法）で効率よく解けます。各区間の被覆数に基づいて「1」を配置することで区間内の合計を最大化し、残りの「1」を前方の空き位置に詰めることで、条件を満たす辞書順最大の文字列を得ることができます。