2022-03-16 アルゴリズムと数学 演習問題集 089, 090 を解いた
アルゴリズムと数学 演習問題集 089 - Log Inequality 2 を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_by
\log_2 a < b \log_2 c
\log_2 a < \log_2 c^b
a < c^b
c^b は overflow する可能性がある。制約から 1 <= a <= 10^18 なので MIN(c^b,10^18+1) で良い。これは c = 2 としても b <= 60 程度で十分に大きいと分かる (2^60 > 10^18) 。また c = 1 のときは b が大きいからといって c^b が大きいとは限らないので別で扱う。 c = 1 のときは制約から a >= 1 なので常に false になる。
まとめると c = 1 のときは No 。 c != 1 のときは c.checked_pow(b.min(60)) を使ってみて overflow すれば Yes でそうでなければ a < c^b してみて Yes か No を返す。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30157903
アルゴリズムと数学 演習問題集 090 - Digit Product Equation（★7） を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_y
競プロ典型 90 問の 025 - Digit Product Equation（★7） と同じ問題 (https://atcoder.jp/contests/typical90/tasks/typical90_y) 。自力では解けず解説を読む。
解説: https://twitter.com/e869120/status/1387175538544975872
N <= 10^11 なので m を全探索 O(N) すると間に合わない。
f(x) は各位の数字の積なので数字の順序は関係ない (後から気づいたことには 1 は個数が増えても関係ない) 。例えば f(234) = f(243) = f(324) = f(342) = 24 になる。 N のとり得る種類に比べて少ない。
そこで f(x) の x の各桁を昇順にしたもので考える。そうすると 10 種類の数字から重複を許して 11 個選ぶ「重複組合せ」なので _{10+11-1}C_{11} = 167960 。これなら列挙できる。
求めるものは m - f(m) = b の個数なので f(m) を列挙すると m = f(m) + b の形で m の候補が出てくる。この m が 1 <= m <= N であるかと m - f(m) = b を満たすかを検算して数えれば良い。
f(x) の列挙は解説にあるとおり DFS で良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30157903
ちなみに _20C_10 の DFS で思い出すのは ABC165 C - Many Requirements (https://atcoder.jp/contests/abc165/tasks/abc165_c) 。本番で解けなかった C 問題。 https://twitter.com/tanakh/status/1256584744101277707
今日のコミット。