n 個から r 個を選ぶ組み合わせは nCr = n! / (k! * (n-r)!) と書ける。ただ、mod p(pは素数) で計算するときは、分母にある「階乗の逆元」を求めるのがやや面倒である。 この逆元はフェルマーの小定理で求められる。説明を省略すると、a は p で割り切れな…

Easy(250): BearPair 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14130 解法 全探索。

問題 TopCoder Statistics - Problem Statement 2 つの音楽アルバム A, B について、曲の長さ(d1, d2)が与えられる(秒)。 曲の長さの合計が上限 minutes を超えないように各アルバムから曲を選ぶとき、選べる曲数の最大値を返す。 ただし、各アルバムからそ…

SRM は何回かやってたけど初めてコンテスト中に提出できました…(easy のみ)。 250: PalindromePrime 区間 [L, R] のうちで、素数かつ後ろから読んでも同じ(回分みたいになってる)整数をカウントする。 本番ではエラトステネスのふるいを書いたけど素数判定と…

Maximum Sum | Aizu Online Judge 累積和としゃくとり法を知らなかったのでメモ。計算量を考えずに全探索までしていたので書いておく。 最悪 O(n2) で最大 n = 100000 だから全探索はダメ(指数記号が出せない…)。

Sum of Integers | Aizu Online Judge 深さ優先探索の問題。C++ で書いたものを Python に翻訳して分かった気になるアレ。 #!/usr/bin/env python def dfs(pos, t, sum): global cnt if t == n: if sum == s: cnt += 1 return if pos > 9: return dfs(pos+1,…