hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

Educational Codeforces Round 8 F: Bear and Fair Set

問題概要

原文 → Problem - F - Codeforces

 5 の倍数  n と、整数  b, q が与えられるので、以下を全て満たす正の整数集合を構築できるかどうか判定せよ。

  • 素数 n で、値は全て  b 以下で相異なる
  •  \left\{ 0, 1, 2, 3, 4 \right\} の各元  r について、要素を  5 で割ったあまりが  r になるような、集合内の要素の数はちょうど  \frac{n}{5} 個である
  • 以下の  q 個の条件を全て満たす
    • 集合内の  1 から  \mathrm{upto}_i までの整数を全て数えた結果が  \mathrm{quantity}_i である

解説

まず、各条件を  \mathrm{upto}_i の値でソートします。すると、 \left[ 1, b \right] はいくつかの区間に分かれることになり、各区間内で数をいくつ選べば良いかもわかります。

以下のようにグラフを作り、最大フローが  n であるかどうかで判定可能です。

  • source に「余りが  r」を表す頂点をそれぞれつなげ、その頂点集合を  A とする。容量はすべて  \frac{n}{5}
  • sink に、各区間に対応するような頂点をつなげ、その頂点集合を  B とする。容量はその区間内で選ぶべき個数になる。
  •  A に属する頂点と  B に属する頂点との間は、対応する区間内にあまりが  r である要素がいくつあるかに応じて容量を設定してつなげる

f:id:tsutaj:20190126171705j:plain

また、Hall の結婚定理を使っても解くことができます。 A の頂点部分集合  A' 全てに対して、 A' B を結ぶ辺として使用される本数の最小値・最大値を求め、これをそれぞれ  E_{\min}, E_{\max} とします (下限が 0 でないことに注意)。条件を満たすような集合が存在する、つまり適切なマッチングが存在するための必要十分条件は、 E_{\min} \leq \frac{n}{5} \times |A'| \leq E_{max} になります (詳しくは Hall の結婚定理 を調べてください)。この方針でやると  O(2^{K} b) (この問題において  K = 5) で解けます。

ソースコード

以下の実装は普通にフローを流す方の解法です。

// フロー略
const int K = 5;
signed main() {
    int N, B, Q; scanf("%lld%lld%lld", &N, &B, &Q);

    vector< tuple<int, int> > queries;
    for(int i=0; i<Q; i++) {
        int upto, quan; scanf("%lld%lld", &upto, &quan);
        queries.emplace_back(upto, quan);
    }
    queries.emplace_back(B, N);
    sort(queries.begin(), queries.end());

    Flow<int> fl(K + queries.size() + 2);
    int source = K + queries.size(), sink = source + 1;

    // source <-> A
    for(int i=0; i<K; i++) {
        fl.add_edge(source, i, N / K);
    }

    bool ok = true;
    int pre_num = 0, pre_quan = 0;
    for(size_t x=0; x<queries.size(); x++) {
        auto q = queries[x];
        int upto, quan; tie(upto, quan) = q;
        if(pre_quan > quan) ok = false;
        int cap = quan - pre_quan;
        
        vector<int> cnt(K);
        for(int i=pre_num+1; i<=upto; i++) {
            int mod = i % K; cnt[mod]++;
        }

        // A <-> B
        for(int i=0; i<K; i++) {
            fl.add_edge(i, K + x, cnt[i]);
        }
        // B <-> sink
        fl.add_edge(K + x, sink, cap);

        pre_num = upto, pre_quan = quan;
    }

    int res = ok ? fl.max_flow(source, sink) : -1;
    printf("%s\n", res == N ? "fair" : "unfair");
    return 0;
}

Hall の結婚定理を用いた解法は公式の実装がわかりやすいです。