Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

ABC191 - F - GCD or MIN

https://atcoder.jp/contests/abc191/tasks/abc191_f

概要

黒板にN個の数字${A[i]}$が書かれている。以下の操作をN-1回行って、最後に残った数は何通りあるでしょう?

  • 2つの数字$a, b$を選び、それらを黒板から消す。代わりに、$\min(a, b)$もしくは、$\gcd(a, b)$のいずれか一方を黒板に書き込む。

制約:$1 \leq N \leq 2000, 1 \leq A[i] \leq 109$

考え方

  1. 少し考えると、残る数字は$\min({A[i]})$より小さくないといけない。(そうでなければ絶対に最後まで残せない)
  2. また、残る数字は明らかに$A[i]$の要素のうちのいくつかの$\gcd$である。(gcdかminなので)
  3. よって、$\gcd(A[i], A[j], \cdots) \leq \min(A[i])$となる$\gcd$をすべて列挙したい。
  4. 2つペアでgcd取ればすべて行けるんじゃない?->嘘です。
  5. $dp[i] := iが作れるか?$のDPをするのは時間計算量が足りない。
  6. 発想の転換をし、$x$の倍数となるもののgcdはいくつか?(これが$x$と等しければ$x$をgcdとして残せるので)を数えると、これは時間内に数えられそう->AC。

考察

まず、$\min(A[i])$より大きい値を残すのは不可能である。なぜならば、常にmin方向(gcdも数字としては小さくなる)に数が選ばれるからである。そして、操作は

  1. いくつかの要素を選んでそのgcdを取る。この時、その値たちのgcdは$\min(A[i])$以下である。
  2. 残ったすべての操作についてminを取る。

の操作で言い換えられるとわかる(残る数字ならば必ずこの手順で黒板に残せる)。

では問題は、$A[i]$からいくつかの値を選んで、作れるgcdを列挙する方法である。

試し方1(間違い)

$dp[x] := xがgcdとなれるか?$のbool値DPを行う。遷移式は、(dp[x]がtrueなら)

$$ dp[\gcd(x, A[i])] = true $$

この愚直な遷移式では、すべての$A[i]$の約数の種類を$X$として、$O(NX \log X)$ほどの計算量で押さえられる。

しかし、ここで$X$はとても大きくなりうるのだ。とても雑な$A[i]$の構成法でこれが大きくなると示せる。

A[0] = 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12
A[1] = 13 * 14 * 15 * 16 * 17 * 18
A[2] = 19 * 20 * 21 * 22 * 23 * 24
...

このように構成すると、$N$個目の要素$4197$まで掛けることとなり、これらの間でも更にかけていくことができるので $X$は明らかに膨大になり、時間内には間に合わないとわかるだろう。

試し方2(間違い)

先ほどはすべてを試そうとしたがゆえに、時間計算量が間に合わなくなった。では、すべてのありうる答えの候補は、2つペアのgcdから求められる、と考えて$O(N2)$で試せばいいのではないか?

しかしこれはgcd系の問題でよく出る間違った命題である。 反例として、以下のようなケースがある。

$$ a = 2 \times 3 = 6, b = 3 \times 5 = 15, c = 5 \times 2 = 10 \ \gcd(a, b) = 3, \gcd(b, c) = 5, \gcd(c, a) = 2, \gcd(a, b, c) = 1 $$

このような反例で、2つペアのgcdがすべてのgcdをカバーできるわけではないとわかる。 集合内の部分集合の要素によるgcdの列挙は、○○個のペアだけで~とはならないのだ。

正しいアプローチ

試し方1では、すべての約数の候補を持っていて、かつ毎回の更新でそれらをすべて見ることから計算量が爆発した。 ここで、DPの対象の入れ替え?みたいなことをしてみる。

$ dp[x] := xを約数に持つAの要素すべての\gcd $

このようにすることで、$dp[x]$の計算に関わる$A[i]$の数を大きく減らすことができる。 もともとのDP遷移の場合、共通因数をそもそも持たない多くの遷移先はgcd == 1となっていた。この無駄を省くために、$x$を因数に持つ$A[i]$のみが$dp[x]$の遷移に関わるというアルゴリズム設計をするとうまくいく。

このアプローチの計算量はどうなるのだろうか。$109$以下の1つの数で最も約数の個数が多いのは$1344=d$個であるとわかっているので、$N$個の要素についてそれぞれ約数を全部見ても、たかだか$O(Nd)$で押さえられる。そして、mapを使用することによって、最終的に$O(Nd \log \max(A[i]))$と最悪計算量を抑えられる。(約数列挙部分は$o(N \sqrt{\max(A[i])})$)

$d$の具体的な値は知らずとも、約数であるので大体$O(\sqrt{N})$だなあと見当をつけることができれば、これが間に合うとわかる。

ACソースコード

C++

最後に

40分かけたのに解けなかったのは本当に反省。GCDは2つペアで見ちゃいけない(警告)