yukicoder contest 349

　Cまで三完。

コンテストへのリンク

No.1989 Pairing Multiset

　解説AC。具体例・図もあり、解説が分かりやすかった。

　解説を箇条書きにすると、

・Sが定まっているとき、f(S)はソートして二つずつ組みを作っていけば求められる

・多重集合はソート済み配列と同一視できる。

・ソート済み配列は、グリッド上の経路に対応させられる。（ので、その個数は、経路数と対応する）

・グリッド上で、ある縦の線に対応する経路数の和として数えられる

・あとは計算量削減パート

　という感じか。

　

　四点目・五点目は簡単ではないけど、三点目までたどりつけばこういうことは考えそう。

　なので、二点目・三点目が思いつけるかどうか、という気がする。

　「多重集合やソート済みの配列はグリッド上の経路に対応させられる」は時々見かける内容だと思うので、押さえておきたい。