COLOCON -Colopl programming contest 2018-：すぬけそだて――ごはん――

問題

https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c

[a, b] の数から 0 個以上の要素を選んで集合 S とする。集合 S に含まれる要素はそれぞれ互いに素である。このような集合 S は何通りあるか？

考え方

以下の 2 つ考えられる。

(i) [a, b] を全探索

最大 36 個の要素で全探索をすると 236 ≒ 7 * 1010 となる。ただし実は全探索する過程で、集合 S に含めることのできない要素については枝刈りされるので dfs で全探索することができる。

Submission #4144792 - COLOCON -Colopl programming contest 2018-

(ii) 素因数でビットDP

集合 S に [a, b] のある数 n を含めることができる場合は、n の素因数は集合 S の素因数には含まれない場合である。b - a <= 35 であるから、[a, b] は [1, 36] の中に含まれる素因数を取りうる。[1, 36] の中に含まれる素数は

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}

の 11 つである。よって、以下のような状態遷移を考えることができる。

dp[i][bit] := [a, b] の i 番目まで参照したときの素因数 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} の部分集合

とすると、

(A)bit に含まれる素因数と n に含まれる素因数に重なりがない場合
 dp[i][bit] -> dp[i+1][bit + state] (state は n に含まれる素因数の集合)

(B)bit に含まれる素因数と n に含まれる素因数が重なる場合
 dp[i][bit] -> dp[i+1][bit]

DP初期値は dp[0][0] = 1 として求めることができる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            long a = in.nextLong(), b = in.nextLong();

            long[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
            long[][] dp = new long[37][1 << 11];
            dp[0][0] = 1;

            int n = (int)(b - a + 1);
            for (int i = 0; i < n; i++) {

                int sum = 0;
                for (int j = 0; j < 11; j++) {
                    if ((i + a) % prime[j] == 0) sum += 1 << j;
                }

                for (int bit = 0; bit < 1 << 11; bit++) {
                    if ((bit & sum) == 0) {
                        dp[i+1][bit + sum] += dp[i][bit];
                    }
                    dp[i+1][bit] += dp[i][bit];
                }
            }

            long ans = 0;
            for (int bit = 0; bit < 1 << 11; bit++) {
                ans += dp[n][bit];
            }

            out.println(ans);

        }

どこに着目して考察するべきだったか

極端な制約 b - a \le 35 に着目する。また偶数と互いに素になる数は奇数であること、購入した数の集合が増えると、互いに素になれる数の候補が小さくなっていくことから枝刈り全探索が自然に出てくる

典型ポイント

  • 枝刈り全探索

類題

雑記

最初は 2 を素因数にもつ数の個数、3 を素因数にもつ数の個数、6 を素因数にもつ数の個数、その他の個数に分けて、うまいこと処理しようとしたが思ったより面倒で実装でもバグらせた。ちゃんと遷移を考えることが重要でした。