数え上げ
問題 反省 解法は解説見ればわかるのでなんで反省点のみ. {a}, {b} をsortして右下から入れていこうとしていた -> 明らかに煩雑. 典型要素として perm を考えるときには挿入/数字が入る場所から決めていく -> 上の数字から入れていくのを a_i = b_j = x なる…
問題 解法 解説の1つの解釈として. 解説/解説放送と同じように, iをremoveした時に A_j が足されるかどうかを考える. ただし,確率ではなくそのような順列の場合の数を数え上げることにする. 事前準備として,n個の順列のうちで そのうちの要素 x,y (x!=y) に…
問題 解法 制約から半分全列挙をエスパーする 2Nとあるので半分と後半に分けてみる 前半の赤色がa文字とすると,前半の青色はN-a,後半の青色はaになる 前半の赤色=reverse(後半の青色) かつ 前半の青色=reverse(後半の赤色)である必要がある どちらも全列挙し…
問題 解法 良解説を聞くのが良い とりあえずsortして分布(c[x] := #( a_i=x なる i ) )をまとめておく 1人ずつグループに入れていこうとすると,分布(k人グループが何個できているか)を持たないといけないので状態が指数時間になって無理 視点を変えて,人数が…