AtCoder Beginner Contest 003 解説 from AtCoder Inc.

A - AtCoder社の給料

n = gets.to_i
puts (1..n).reduce(0) { |a, e| a + 10_000 * e * (1.0 / n) }

上記のようにイテレーションを使って律儀に計算するのではなく、解説にあるように期待値の和から求めれば計算量が少なくて済む。
具体的には、 $10000 \times (n + 1) \times \frac{1}{2}$ となるので、puts 5000 * (gets.to_i + 1)だけで片付いてしまう。

B - AtCoderトランプ

s = gets.chomp
t = gets.chomp
 
s.size.times do |i|
  unless s[i] == t[i]
    next if s[i] == '@' && t[i] =~ /[atcoder]/
    next if s[i] =~ /[atcoder]/ && t[i] == '@'
    puts 'You will lose'
    exit
  end
end
puts 'You can win'

スッキリ書けたかな。

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

n, k = gets.split.map(&:to_i)
ratings = gets.split.map(&:to_i)
 
puts ratings.sort[-k..-1].reduce(0) { |a, e| (a + e) / 2.0 }

最大レートを達成するためには、N個の動画をレーティング順にソートして、高レーティングなK個の動画をチョイスしなければならない。
加えて、高レーティングなK個の動画の中で、レーティングの低い順に見ていく必要がある（後から見た動画の方がレーティングに与える影響が大きいため）。

D - AtCoder社の冬

# n個からk個を選ぶ組み合わせの数を求める
def c(n, k)
  (1..n).reduce(1, :*) / ((1..n-k).reduce(1, :*) * (1..k).reduce(1, :*))
end

# x行y列の区画におけるデスクとラックの配置パターン数を求める
def alloc(x, y)
  return 0 if x < 0 || y < 0
  return 0 if x * y < ::D + ::L
  c(x * y, ::D) * c(x * y - ::D, ::L)
end

R, C = gets.split.map(&:to_i)
X, Y = gets.split.map(&:to_i)
D, L = gets.split.map(&:to_i)

# 壁で囲まれた区画の配置パターン数
walled_area = (R - X + 1) * (C - Y + 1)

# デスクとラックの配置パターン数
desk_rack_area = alloc(X, Y)
# 以下、包除原理を用いて最上[下左右]列が全て空きスペースのパターンを排除
desk_rack_area -= alloc(X - 1, Y) * 2 + alloc(X, Y - 1) * 2
desk_rack_area += alloc(X - 1, Y - 1) * 4 + alloc(X - 2, Y) + alloc(X, Y - 2) 
desk_rack_area -= alloc(X - 1, Y - 2) * 2 + alloc(X - 2, Y - 1) * 2 
desk_rack_area += alloc(X - 2, Y - 2)

puts walled_area * desk_rack_area % 1_000_000_007

とても苦労した。
一難去ってまた一難という感じで、完答できるまでだいぶ時間が掛かってしまった。

復習も兼ねて、手順を追って解答を見ていく。

まずは、R行C列の社員室において、X行Y列の壁で囲まれた領域を設けるパターン数を求める。
行について考えてみると、例えばR = 3のとき、X = 1ならば3パターン、X = 2ならば2パターン、X = 3ならば1パターンといった具合になる。
よって、行の設置パターン数はR - X + 1。同様に、列はC - Y + 1。
つまり、壁で囲まれた領域の設置パターン数は、
$(R - X + 1) \times (C - Y + 1) \cdots ①$
になる。

次に、X行Y列の領域において、D個のデスクとL個のサーバーラックを配置するパターン数を求める。
ここでは、デスクもラックもない空きスペースの存在も考慮しなければいけない。
すると、求めるパターン数は、 $_{X \times Y}C_{D+L} \ \times \ _{X \times Y-D}C_L$ になる。
この式は、この後も繰り返し使われるので、allocという名前でメソッド化しておく。
なお、allocメソッドに毎回、定数D, Lを渡すのは面倒なので、::を使ってトップレベル定数にアクセスすることにした。

さて、実際にデスクとラックの配置パターン数を求めるわけだが、X行Y列の区画はデスクとラックの位置に沿って決められている。
よって、X行Y列の領域の最上[下左右]列のいずれかにデスクかラックが置かれていなければならない。
つまり、「X行Y列の領域の最上[下左右]列が全て空きスペースのパターン」を取り除かないと、正しいパターン数を求めることができない。

「最上[下左右]列が全て空きスペースのパターン」は、上下が空きスペース列、左右下が空きスペース列など、空きスペース列が重複するパターンも含まれる。
ここで、最上列が空きスペース列のパターンを集合Tとして、同様に最下列をB、最左列をL、最右列をRとすると、取り除くべきパターン数は、
$T \vee B \vee L \vee R \cdots ②$
ということになる。

これを包除原理を利用して変形すると、
$T + B + L + R - (T \wedge B) - (T \wedge L) - (T \wedge R) - (B \wedge L) - (B \wedge R) \\ - (L \wedge R) + (T \wedge B \wedge L) + (T \wedge B \wedge R) + (B \wedge L \wedge R) - (T \wedge B \wedge L \wedge R)$
となる。
要するに、それぞれの集合を足して、2集合の積集合を引いて、3集合の積集合を足して、4集合の積集合を引く。
集合の数を増やす毎に、足して引いてを変えながら繰り返していく。

ここまで来れば、あとはallocメソッドを使ってこれを再現していけばいい。
TやBは上下の空きスペース列が増えるということだから、Xを減らしていけばいいし、LやRならYを減らしていけばいい。
注意しなければいけないのは、行や列を減らして考えて処理するので、XやYが負の値を取ったり、X × Y が D + Lより少なくなってしまうケースが発生してしまうことだ。
条件に合わないそのようなケースを無視するために、allocメソッドに条件式を書いて該当ケースを弾いている。

最後に、① × ②で全てのパターンを求めてから余りを出せば終わり。