まずは \(S\) が固定されたときに目標が達成可能か判定してみます．

参加者 \(1\) に注目します．

参加者 \(1\) の帽子が赤い場合，青い帽子を被った参加者とペアにする必要があります． 試合の結果必ず参加者 \(1\) が勝ち残ることを考えると，青い帽子を被っている中で番号が最大の参加者を選んで損しません． よってこの場合ペアを確定できます．

参加者 \(1\) の帽子が青い場合は，試合相手の帽子の色に制限はありません．もし赤い帽子を被っている参加者が残っているなら，その中で番号最小の人と組ませることで損しません． 全員が青い帽子の場合は番号最大の参加者と組ませることで損しません． よってこの場合もペアが確定します．

以上より，参加者 \(1\) のペアが確定しました． このペアを取り除いたあとも，同じ議論で番号最小の参加者のペアが決定していきます． この操作を繰り返して最終的な組分けを決定し大会を進行すれば，最終的に目標が達成できるか否かがわかります．

こうして \(S\) が固定された場合の判定方法がわかりましたが，このままでは元の問題を解くことができないので，もう少し見通しをよくします．

直感的に考えると

• \(S\) 内に B が多いほど目標を達成しやすい
• \(S\) 内の B の位置が左に寄っているほど目標を達成しやすい

です． そこで，目標が達成可能な \(S\) であって，できるだけ少ない個数の B を含み，かつそれらができるだけ右に寄っているようなものを考えます． これを極小な \(S\) と呼ぶことにします． できるだけ右，の定義が曖昧ですが，どういう決め方をしても同じ結論になります． また極小な \(S\) が一意であることは自明ではありませんが，後述の議論より一意とわかります．

適当に手を動かすと，小さい \(N\) については以下の \(S\) が極小になります．

• \(N=1\): \(S=\)RB
• \(N=2\): \(S=\)RBRB
• \(N=3\): \(S=\)RBRRBRBB

最初に説明した貪欲法の”逆”を考えることで，より大きな \(N\) についても極小な \(S\) を求めることができます．

ある \(N\) に対する極小な \(S\) を \(T(N)\) で表すことにします． \(T(N)\) を使って，目標が達成可能な \(S\) を特徴づけます． するとこれは以下のような条件になります．

• \(S\) の R,B をそれぞれ \(-1\), \(+1\) に置き換えたあと累積和ととった数列を \(A\) とする．同様に \(T(N)\) の R,B をそれぞれ \(-1\), \(+1\) に置き換えたあと累積和ととった数列を \(B\) とする． すべての \(i\) について \(A_i \geq B_i\) ならば目標は達成可能で，そうでないなら目標は達成不可能である．

証明は帰納法でできます． ある \(i\) で \(A_i<B_i\) であったとします．まず，そのような \(i\) のうち最小をとります．そして，解説の最初で説明した貪欲な組分けを位置 \(i\) まで走らせたときの様子を観察してみます． すると，\(1\) 回戦が終わったあとの状態において，\(S\) は条件を満たさないことがわかります．

逆にすべての \(i\) で \(A_i \geq B_i\) のときには \(S\) は条件を満たします．これは簡単に確認できます．

ここまでくればあとは簡単です．結局問題は

• \(+1,-1\) 列が与えられる．隣接 swap を繰り返して累積和が特定の値以上になるようにせよ．

というものです．答えは累積和と目標の差を \(2\) で割った値になります．

上記の操作はすべて \(O(2^N)\) 時間で行えるため，元の問題も同じ計算量で解けます．

解答例