ABC003 C - AtCoderプログラミング講座,D - AtCoder社の冬

今回もバチャコンで解いたC問題とD問題のメモです。

C - AtCoderプログラミング講座

提出コード
まずは動画のレートを降順でソートします。
そうしたら、大きい方から動画を見る個数だけ持ってきて、それを小さい順に見ます。
動画を見るたびに現在のレートを2で割るので、一番大きいレートの動画はできるだけ最後に見たいからです。あとはループで毎回の処理を行い、答えを出力すれば終わりです。

D - AtCoder社の冬

提出コード
まず前提としてmodに関するコンビネーションを使うので、けんちょんさんのブログを参考にしてください(いつもありがとうございます)。

qiita.com

最近学んだところだったのでいい機会だったかなと思います。
部分点解法については、割とすぐに求めることができました。
まず最初に最終的なのマスの位置を決めます。
これは通りあります。
次に、X×Yのマスの中の配置を決めます。

となります。はでも構いません。
あとはこれを計算して、のマスの決め方との積をとれば答えが求まります。 と、時間内に解けたのはここまででした。

満点解法については包除原理を用います。
具体的には、のマスの中の配置方法について、
の一番外側の縦と横の計4本のうち、
0、2、4本のマスをすべて未配置と仮定したときのラックと机の置き方の組み合わせを正
1、3本のマスをすべて未配置と仮定したときのラックと机の置き方の組み合わせを負
として、それらの総和をとります。このとき、のマスの中で未配置となるマスの数より、未配置と仮定したマスのほうが多かった場合はその組み合わせを0通りとします。
この総和が、最終的なのマスの配置の組み合わせになります。