ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 195 F - Coprime Present

AtCoder プログラミング 競技プログラミング

お題箱より。

F - Coprime Present

解法

互いに素であるという条件を扱うときには、素因数だけに注目することで考慮すべき対象の個数を減らせる場合があります。2つの正整数が互いに素であることと共通の素因数を持たないことは同値です。

集合 S = \lbrace A, A+1, ..., B-1, B\rbrace とします。求めるべき答えは、 S の部分集合のうち、どの相異なる2つの要素も共通の素因数を持たないものの個数です。そのため考えるべき素因数は、 S の要素のうち2つ以上のものが持っている素因数だけで十分です。

S の要素が連続する整数であり、その最大値と最小値の差が 72 以下と小さいことに注目します。 73 以上の素数 d について、 S に d の倍数が2つ以上含まれることはありません。相異なる d の倍数を2つ取ったとき、その差の絶対値は d 以上であるからです。

つまり考えるべき素因数は 72 以下の素数だけで十分であり、これは実際に数えると 20 個です。ここまで個数を絞れれば解法の見通しが立ちます。

ここからの考察の進め方ですが、まず動的計画法を考えてみるのが堅実で見通しが立ちやすいでしょう。要素を1つずつ見ていって、部分集合に追加する・追加しないの遷移をするDPを考えます。

要素を部分集合に追加して良いかを判定するために、追加前の部分集合の情報として何を覚えておけば良いかを考えます。これは「 72 以下の素因数のうち、集合内の要素が既に持っているのはどれか」だけで十分なので、次のように状態を定義します。

  • dp\lbrack i\rbrack\lbrack p\rbrack = 集合 S の前から i 個の要素のうち 0 個以上のものを含む部分集合であって、次の条件を満たすものの個数。
    • どの相異なる2要素も共通の素因数を持たない。
    • 含んでいる要素が持っている 72 以下の素因数からなる集合が p である。

これは p を 2^{20} 未満の非負整数として表現するビットDPとして実装できます。 dp\lbrack i\rbrack\lbrack p\rbrack からの遷移は次の2通りになります。

  • 次の要素を部分集合に追加しない：そのまま dp\lbrack i+1\rbrack\lbrack p\rbrack に遷移する。
  • 次の要素を部分集合に追加する：次の要素は A+i であり、これが持っている 72 以下の素因数からなる集合を p_{i} と表記する。 p と p_{i} が共通要素を持っていればこの遷移を無視し、持っていなければ dp\lbrack i+1\rbrack\lbrack p\cup p_{i}\rbrack に遷移する。

ACコード

Submission #20980982 - Panasonic Programming Contest (AtCoder Beginner Contest 195)

考察の進め方について

この記事では考慮すべき素因数が少ないという点から考察を進めていきました。考慮すべき素因数が 20 個しかないと分かると、指数時間かかるアルゴリズムも視野に入るので考察の幅が広がります。

先にDPを考えるアプローチもできます。条件を満たす部分集合の個数を求める方法として、要素を1つずつ見ていって部分集合に追加する・追加しないの遷移をするDPは代表的でまず考えるべきものです。このDPで必要な情報を考えると、既に持っている素因数の集合が必要になり、その種類数を見積もろうという考察に進むことができます。

※「ビットDP」はDPで必要な情報を考えた結果出てくるものなので、最初からビットDPを思いつく必要はありません。考察のスタートはあくまで「要素を1つずつ見ていくDP」です

記事リクエストでもコンテスト後のTwitterでも、包除を考えて上手く行かなかったという声がありました。確かに、連続した整数・互いに素・数え上げという問題の断片的な特徴からは、通称「約数系包除」と呼ばれるアプローチを連想します。しかし実際に公式を適用してみると必要な値が求められずに行き詰まります。この問題のように部分集合の個数を数える問題では、約数系包除が上手くいきづらい印象です。