Maximin Game [Kyoto University Programming Contest 2019 D]

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d

前提知識

• カタラン数

解説

https://atcoder.jp/contests/kupc2019/submissions/7958349

順列を2グループに分けていく問題であるが、小さいほうから確定させていくことを考える。
01を作る場合は

千| 0  
月|   
  
千| 0  
月| 1  
  
千| 0  
月| 12  
  
千| 03  
月| 12  

となる。負ける方に先に割り当てていく。
010101の場合は操作は一意に定まるが、0011の場合は違う。

千| 0  
月|   
  
ここまではいいが、次が分岐する  
  
千| 01  
月| 2  
  
千| 02  
月| 1  
  
ここからは一本道。  
  
千| 01  
月| 234  
  
千| 02  
月| 134  
  
ここからもそれぞれ分岐（上でだけ分岐させてみる）。  
  
千| 0157  
月| 2346  
  
千| 0167  
月| 2345  

このように、連続している部分で分岐が起こり、境目で一旦戻ることになる。
よって連続している部分での組み合わせを掛け合わせていくと答えになる。

連続していくとどれだけの組み合わせがあるかであるが、実はカタラン数というのに帰着する。
例えば、千咲さんに配ることを(、月乃瀬さんに配ることを)として、4回勝負ですべて月乃瀬さん勝利とすると、
(が4つ、)が4つで正しいかっこ列を作ることと配り方が丁度対応する。
これは直感的でないかもしれないが、どんなターンでも千咲さんが必ず多いという制約があることから分かるだろう。
この正しいかっこ列の組み合わせはカタラン数と丁度一致する。
カタラン数は、二項係数を使った効率的な計算方法がよく知られている。
よって、それを使うと解ける。

Comb<mint, 201010> com;
int N;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    auto rl = runLengthEncoding(S);

    mint ans = 1;
    fore(p, rl) ans *= com.catalanNumber(p.second, p.second);
    cout << ans << endl;
}