AtCoder ABC159 A 解法メモ n個のものからk個選ぶ組み合わせを計算したい（二項係数）

昔数学で習ったはずなんだけれども思い出せない＆実装にあたりちょっとハマったのでメモ。

解いていた問題

atcoder.jp

解法メモ

• 二項係数と呼ばれるもの(もの？)で導出可能

private fun readLn() = readLine()!!
private fun readStrings() = readLn().split(" ").toMutableList()
private fun readInt() = readLn().toInt()
private fun readInts() = readLn().split(" ").map { it.toInt() }.toMutableList()
private fun readLong() = readLn().toLong()
private fun readLongs() = readLn().split(" ").map { it.toLong() }.toMutableList()

fun main(args: Array<String>) {
    solveABC159A()
}

fun solveABC159A() {
    val (n, m) = readLongs()

    println(n * (n - 1) / 2 + m * (m - 1) / 2)
}

ハマったところ

• そもそもの問題（概要）
  • 偶数のボールn個、奇数のボールm個から、2つ取り出して和が偶数になる組み合わせの数(0≤n,m≤100)
    • つまり偶数・偶数 or 奇数・奇数の時の組み合わせを数えたい
• 二項係数（Wikipediaより）
  • n個のものからk個選ぶときは n! / ( k! * (n-k!) ) で求められる
    • ハマった点：これを愚直に実装してしまった
      • n,mともに制約が0以上100以下なので、100!（=9.332622e+157）とかいうめちゃくちゃでかい数字を計算してしまっていた
      • 階乗を展開すれば分母分子でk!分は約分できるので、今回の2つ選ぶ場合であれば n * (n - 1) / 2 で求められる
      • 偶数・偶数 or 奇数・奇数それぞれ同様なので n * (n - 1) / 2 + m * (m - 1) / 2 となる

最近はある程度計算量については意識はできるようになってきたと思っていたけれども、計算途中の値がどれくらいの大きさになるかまで考慮が及んでいなかったので、今後の課題だなと感じました。

提出した回答

• 誤（階乗版）：Submission #35590755 - AtCoder Beginner Contest 159
• 正：Submission #35590916 - AtCoder Beginner Contest 159

参考

• https://img.atcoder.jp/abc159/editorial.pdf
• 二項係数 - Wikipedia