A - 753
シグネチャを決める。
abc114a :: Int -- X
-> Bool -- 答え
abc114a x = elem x [7,5,3]
B - 754
シグネチャを決める。
abc114b :: String -- S
-> Int -- 答え
Data.List.Split.divvy の出番。
import Data.List.Split
abc114b s = minimum [abs $ 753 - read c | c <- divvy 3 1 s]
C - 755
シグネチャを決める。
abc114c :: Int -- N
-> Int -- 答え
直接解法
$N \leq 10^9$ なら、総当たり的な解法でも何とかなりそう。
整数値と、数字として3,5,7が一度でも使われたかのフラグ3つを組にして、3,5,7だけを使って作れる数を昇順に全列挙する。
$k-1$桁のそういう数の後ろに3,5,7を追加すると、$k$桁のそういう数が作れる。
$N$以下のそれらのうち、フラグが全て立っているものの個数を数える。
abc114c n = length $ filter (\(_,a,b,c) -> a && b && c) $ takeWhile (\(v,_,_,_) -> v <= n) s357
where
s357 = (0,False,False,False) : foldr f undefined s357
f (v,a,b,c) rest = (v*10+3,True,b,c):(v*10+5,a,True,c):(v*10+7,a,b,True):rest
D - 756
シグネチャを決める。
abc114d :: Int -- N
-> Int -- 答え
$N \leq 100$ と大したことないので、$N!$ の素因数分解を、個々の素因数分解の総合として求める。
素因数分解して $K = \prod p_i^{e_i}$ となる数は、約数を $\prod (e_i + 1)$ 個持つ。
$75 = 3 \times 5 \times 5$ なので、
七五数は素因数分解したとき、多重集合で表して $\{e_i\} = \{74\}, \{2,24\}, \{4,14\}, \{2,4,4\}$ のいずれかとなる。
なので、$N!$ の素因数分解から、こうなるように $p_i$ を選ぶやり方の場合の数を数えればよい。
結果
abc144d :: Int -> Int
abc144d n = c74 + pred c2 * c24 + pred c4 * c14 +(c2 - 2) * div (c4 * pred c4) 2
where
-- N!の素因数分解 prime factors of factorial of N
pffn = accumArray (+) 0 (2, n) [(p, 1) | k <- [2 .. n], p <- primeFactors k]
-- k個以上ある素因数の種類数を数える
count k = length $ filter (k <=) $ elems pffn
[c2,c4,c14,c24,c74] = map count [2,4,14,24,74]
ひっかかりポイントとして、「k個以上ある素因数の種類数」を数えたので、
例えば ${2,24}$ を数えるとき、24の方は c24 そのままでよいが、c2 の中には c24 で選んだものも入っているので1減らす必要がある。