blog.bouzuya.net

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 のときは Noc != 1 のときは c.checked_pow(b.min(60)) を使ってみて overflow すれば Yes でそうでなければ a < c^b してみて YesNo を返す。

提出: 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 の候補が出てくる。この m1 <= 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


今日のコミット。