解法

最初の文字を固定したときの最適な文字列 \(x\) は、以下の条件を満たす限り、直前と同じ文字を使い続ける貪欲法で構築できます。

• \(x\) の \(i\) 文字目までの 0 の個数が、\(s\) の \(i\) 文字目までの 0 の個数と \(t\) の \(i\) 文字目までの 0 の個数の間にある

よって、最初の文字を 0 とした場合と 1 とした場合それぞれで貪欲に構築した文字列の美しさを求め、大きい方を出力すればよいです。

C++による実装例

証明

以下で貪欲の正当性を示します。

文字列を二次元グリッド上の経路と対応付ける

文字列 \(s\in S_{n,m}\) を次のように座標 \((0,0)\) から\((n,m)\) に \(n+m\) ステップで移動する経路と対応付けて説明します。

• \(i\) ステップ目に座標 \((x,y)\) にいるとき、\(s\) の \(i\) 文字目が 0 であれば \((x+1,y)\) に、1 であれば \((x,y+1)\) に移動する。

この経路において、文字列の隣り合った \(2\) 文字を入れ替える操作は、図のような、経路の曲がり角を「折り返す」ような操作に対応します。

よって、\(s,t\) に対応する経路を \(S,T\) とすると、\(s,t\) の間にある文字列に対応する経路は、\(S,T\) の間（\(S,T\)で囲われる領域内）にあることが分かります。 また、美しさを最大化するためには、曲がる回数を最小化すればよいです。

まっすぐ進んだら \(S\) と \(T\) の間の領域から出てしまう場合、方向転換する必要があります。 それ以外の場合にする方向転換を 悪い方向転換 と呼ぶことにします。 曲がる回数の最小を求める時に、悪い方向転換を考える必要が無いことを示せば十分です。

これは次のような方針で示すことができます。\((0,0)\) から \((n,m)\) への経路であって\(S\) と \(T\) の間にある \(P\) を任意にとり、\(P\) が悪い方向転換をするとします。 次のように \(P\) に手を加えることで、以下の条件を満たす経路 \(Q\) が構築できます。

• 方向転換の回数が \(P\) より多くない
• 最初の悪い方向転換のタイミング（何ステップ目か）が \(P\) より遅いか、悪い方向転換をしない

\(n+1\) 回のうち、最初に悪い方向転換をした地点を点 \(A\) とおきます。 点 \(A\) で曲がらず、\(S\) か \(T\) にぶつかってから曲がることにした経路を \(P'\) とします。 \(P\) と \(P'\) が点 \(A\) 以降初めて交わる（同じ点を共有する）点を \(B\) とします。 点 \(A\) から点 \(B\) まで（両端を含む）の間に \(P'\) が曲がる回数は常に \(1\) 回です。点 \(A\) から点 \(B\) までの間に \(P\) が曲がる回数は \(2\) 回以上です。 \(B=(n,m)\) である場合、\(P'\) は悪い方向転換をしていないため、この\(P'\) を \(Q\) とすればよいです。 そうでない場合、点 \(B\) までは \(P'\) の経路を、点 \(B\) から先は \(P\) の経路を取るようにした新たな経路 \(P''\) を考えます。 点 \(A\) から点 \(B\) まで（両端を含む）の間に \(P''\) が曲がる回数は常に \(2\) 回です。 また、\(P''\) の最初の悪い方向転換の場所は点 \(B\) です。 よって、この \(P''\) を \(Q\) とすればよいです。

\(P\) から \(Q\) を構築する操作を繰り返すと、いつかは悪い方向転換をしない経路が構築できます（悪い方向転換をする経路である限り、だんだん最初の方向転換のタイミングが遅くなっていくが、\((0,0)\) から \((n,m)\) への経路は \(n+m\) ステップと有限であるため）。よって、これで示せました。