読者です 読者をやめる 読者になる 読者になる

オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 003 D: AtCoder社の冬

問題文

abc003.contest.atcoder.jp

解法

いきなり X*Y の区画の上下左右すべてに、デスクまたはサーバーラックが接した配置の場合の数を数えるのは難しいので、とりあえず D 個のデスクと L 個のサーバーラックを自由に配置する場合の数を考える。これは X*Y から D 個選ぶ組み合わせの数と、X*Y-D から L 個選ぶ組み合わせの数の積に等しい。ここから、X*Y の区画の上下左右のいずれかまたは複数にデスクまたはサーバーラックが接していない配置の仕方の数を引いていく。

ちなみにこの式を包除原理という。この実装方法は蟻本にも載ってて、bit でエイってやるらしい。

あとは、この X*Y の区画を R*C のなかにずらして配置する分を掛け算で求めれば終わり。