高速ゼータ変換を思いつくのに時間かかった

問題概要

あなたは $N$ 人の従業員を持つ店の店長です。 $i$ 番目の従業員は今日から「 $A_{i}$ 日連続で働いた後 $A_{i}$ 日連続で休む」ことを繰り返します。

あなたは今日から毎日出勤し、その日に出勤している従業員の中から 1 人選び、メダルを 1 枚配ります。（その日に出勤している従業員が 1 人もいなければ何もしません）

全ての従業員に $K$ 枚以上のメダルを配るためには、最短で何日かかるでしょうか。

制約

$1 \le N \le 18$
$1 \le K, A_{i} \le 10^{5}$

考えたこと

最初に、「実は全員が × な日を除けば毎日埋められるんじゃないか」と想像してみた。しかしこれはすぐに反例が見つかった。

$A = (1, 1, 1, 1, 1, 6)$
$K = 1$

のとき、上記の仮説が正しければ 6 日間で実現できることになる。しかし実際は $(1, 1, 1, 1, 1)$ のところで、2 日置きに揃って x になる壁が分厚くて、10 日間を要する。

上記のことから、ボトルネックとなるような「従業員の部分集合」を特定できれば、その従業員全員に行き渡らせるのに必要な人数が答えになるのではないかと考えた！！具体的には、 $D$ 日以内に終えられるかどうかは、次のように判定できそうに思えた。

従業員の部分集合 $S$ に対して、 $D$ 日間のうち「全員が ×」という日が $d(S)$ 日分であったとする。

このとき、任意の $S$ に対して $D - d(S) \ge K|S|$ であるならば、可能である。

そしてこれが正しいことが Hall の定理から示せるのだ。Hall の定理とは、頂点集合 $U, V$ とに分割された二部グラフに対して、以下が同値だと主張している！

$U$ をすべてカバーするマッチングが存在する
(Hall の条件) $U$ の任意の部分集合 $A$ に対して、 $\Gamma(A) \ge |A|$ が成立する ( $\Gamma(A)$ は $A$ に含まれるいずれかの頂点に隣接している頂点の個数)

そして従業員の問題に戻り、左側を「従業員 × $K$ 日分」として、右側を「日程」とすると、上記の予想は Hall の条件に該当する。

よって結論として、下の条件を満たすような $D$ の最小値を求めればよい。二分探索がピッタリとなる。なお、 $D = 2NK$ とすると条件を満たすことに注意する。これを二分探索の上限に設定できる。

任意の $S$ に対して $D - d(S) \ge K|S|$ が成立する

判定パート

残りは、判定問題を解くこと。

$f(S)$ := $S$ に該当する従業員のみ x で、それ以外の従業員は o であるような日数

としたとき、

$d(S)$ := $\sum_{S \subset T} f(T)$

が成立することに注意しよう。よって、 $f(S)$ さえ求めておけば高速ゼータ変換によって $d(S)$ を求めることができる。 $f(S)$ は、あらかじめ $2NK$ 日分の「働く従業員の集合」を求めておけば、簡単に求められる。

以上をまとめると、 $O(N^{2}K + N2^{N}(\log N + \log K))$ で求められることがわかった。

コード

#include <bits/stdc++.h>
using namespace std;

const int MAX = 4000000;
int main() {
    int N, K; 
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<int> bits(MAX, (1<<N)-1);
    for (int t = 0; t < MAX; ++t) {
        for (int i = 0; i < N; ++i) {
            int r = t % (A[i] * 2);
            if (0 <= r && r < A[i]) bits[t] &= ~(1<<i);
        }
    }
  
    auto biok = [&](int x) {
        vector<int> d(1<<N, 0);
        for (int t = 0; t < x; ++t) d[bits[t]]++;
        for (int i = 0; i < N; ++i) {
            for (int bit = (1<<N)-1; bit >= 0; --bit) {
                if (bit & (1<<i)) continue;
                d[bit] += d[bit | (1<<i)];
            }
        }
        for (int bit = 0; bit < (1<<N); ++bit) {
            int con = 0;
            for (int i = 0; i < N; ++i) if (bit & (1<<i)) ++con;
            int lim = x - con * K;
            if (d[bit] > lim) return false;
        }
        return true;
    };

    int left = 0, right = MAX;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        if (biok(mid)) right = mid;
        else left = mid;
    }
    cout << right << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 106 E - Medals (赤色, 700 点)

問題概要

制約

考えたこと

判定パート

コード