Facebook Round 1A

仕切り直しでもう一回。SRMとかぶってたので適当にしかやってない。

Wine Tasting

1からNまでのPermutationのうち、i番目の値がiであるものが少なくともK個あるのは何通りか答えよ、という問題。

一致している個数をKからNまで全通り試す。一致している個数がL個のとき、一致していない個数は当然N-L個で、一致しているものはN個からL個選択する(パスカルの三角形で計算できる)のと、一致していないものは、(N-L)!から1個一致しているもの(N-L個から1個選択して、(N-L-1)個一致していないもの...というのをN-L個一致しているものを調べる。)を引いたもの...N-L個一致しているものを引いたもの、という感じになる。後は適当にメモなりなんなりするだけ。

Diversity Number

数列から、前半部が非下降列、後半部が非上昇列になるように部分数列を取り出す。このような部分数列は何通りあるか答えよ、という問題。

まずは一番大きい値をどれにするか決める。後は左側と右側に値を追加していく。ダブルカウントを避けるために、左側に追加する値は常に右側に追加する値よりも大きいようにすることと、値を追加するときに同じ値をスキップさせないようにすることに注意してDPするだけ。

Turn on the Lights

2次元平面にライトが並んでいる、あるライトを触ると、それと隣接するものが影響を受け、ついていたら消え、消えていたらつく。このとき全部のライトをつける最短手数を答えよ、という問題。

最初の一列を操作する方法を任意に試すと、次の列はその列を全部つけるような操作しかできない。最終的に最後の列が全部ついているようにできれば、その手数が最短のものを答えれば良い。