hogecoder

tsutaj 競技プログラミングの記録

2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) B: Coprime Integers

この辺の (海外の ICPC 問題の) 記事書く人いなさそうなので書きます

問題概要

原文 (PDF): https://codeforces.com/gym/101982/attachments/download/7897/20182019-acmicpc-pacific-northwest-regional-contest-div-1-en.pdf

整数  A, B, C, D が与えられる。 A \leq x \leq B, C \leq y \leq D を満たす整数の組  (x, y) であって  x, y が互いに素であるものの個数を求めよ。

  •  1 \leq A \leq B \leq 10^{7}
  •  1 \leq C \leq D \leq 10^{7}
  • TL 1 sec

解法

※ 計算量を書くために、 N = \max(B, D) としています。

お察しの通り  O(N \log N) を書いても落ちると思います。それよりも時間計算量が良いものを書く必要があります。

 f(p, q) を、「 1 \leq x \leq p, 1 \leq y \leq q を満たす組  (x, y) であって  x, y が互いに素であるものの個数」とします。元の問題で要求されていることとは微妙に異なりますが、この関数を組み合わせることで元の問題を表現することができます。具体的には  f(B, D) - f(A-1, D) - f(B, C-1) + f(A-1, C-1) を考えれば良いです (二次元累積和を実装したことがあるならば、それがイメージの助けになるかと思います)

では、この関数  f はどのようにすれば高速に計算できるでしょうか?整数の組  (x, y) 1 以外で最小の公約数が  d であるとして、包除原理のように考えると以下のようになります。

  •  d に含まれる素数が奇数個ならば、引かなければならないので引く
  •  d に含まれる素数が偶数個ならば、引きすぎたぶんを足す
  • ただし、 d が平方数で割り切れる (つまりある素数  p があって  d p^{2} で割り切れる) 場合は他の結果に包含されるので考慮しない

ここで「引く」「足す」「考慮しない」など、それぞれの場合の数に対して  -1, +1, 0 といった係数がかかることになりますが、この係数はまさにメビウス関数 (Mobius function) そのものです。この関数について詳しく知りたい方は メビウスの反転公式の証明と応用 | 高校数学の美しい物語 を見てください。メビウス関数はエラトステネスのふるいを動かす際に一緒に計算できるので、元の問題は  O(N \log \log N) で解けます。

ソースコード

const int MAXN = 10000010;
int mu[MAXN + 5];
bool is_prime[MAXN + 5];

int main() {
    fill(is_prime + 2, is_prime + MAXN + 1, true);
    fill(mu, mu + MAXN + 1, 1);
    for(int i=2; i<=MAXN; i++) {
        if(!is_prime[i]) continue;
        mu[i] = -1;
        for(int k=i<<1; k<=MAXN; k+=i) {
            is_prime[k] = false;
            if((k/i) % i == 0) mu[k] = 0;
            else mu[k] = -mu[k/i];
        }
    }

    int A, B, C, D; scanf("%d%d%d%d", &A, &B, &C, &D);

    auto calc = [&](int x, int y) {
        ll res = 0;
        for(int i=1; i<=min(x, y); i++) {
            res += 1LL * (x/i) * (y/i) * mu[i];
        }
        return res;
    };

    ll ans = calc(B, D) - calc(A-1, D) - calc(B, C-1) + calc(A-1, C-1);
    printf("%lld\n", ans);
    return 0;
}

第三回アルゴリズム実技検定 O 問題: 輪投げ

問題概要

原文はこちら

atcoder.jp

棒が  N 本ある。これらのうち異なる  M 本に輪を投げ入れることを  3 回行う。投げ入れ方によって以下のように得点が定められる。

  •  i 回目に  j 番目の棒に輪を投げ入れたとき、 A_{j} \left( B_j \right)^{i} \bmod R_{i} 点を得る。これらの合計を  X とする。
  •  j 番目の棒について、全 3 回のうち  i 回その棒に輪を投げ入れたとき、 A_{j} \left( B_j \right)^{i} 点を失う。これらの合計を  Y とする。
  • 総得点は  X - Y 点である。

得られる得点を最大化せよ。最大化した得点が負になることもある。

制約

  •  1 \leq M \leq N \leq 500
  •  2 \leq A_{i}, B_{i} \leq 1000
  •  2 \leq R_{i} \leq 10^{5}

解説

おそらくどう考えても動的計画法のアプローチでは無理だと思います。他のアプローチを考えましょう。満たすべき制約がそれなりに多いので、フローを考えてみることにします。必要そうな頂点や辺を順に考えていきます。

  1. それぞれの回において、ある  M 本を選んでそこに投げなければならないので、流量  M だけ通過できるような頂点が  3 つ欲しい
  2. ある棒に関しては一度に複数回投げられないので、1. で用意した各頂点から流量  1 ずつ、棒を表す全頂点に張りたい
  3. 失点を表現できるように頂点を作りたい (後述)

符号を反転させて最小化問題として捉え、最小費用流で考えてみると、途中までは以下のようにグラフを作ると良くなります。辺に書いてある  (a, b) とは、流量が  a でコストが  b であることを表します。

※図における  A_i はすべて  A_j に置き換えて読んでください

f:id:tsutaj:20200606180236j:plain

さて、実際には失点を表現できるようにグラフを作らなければならないですが、後半のグラフはどう作ればよいでしょうか?ここで超重要なのが、 B_{i} \geq 2 であるので 失点は指数的に増える ということです。より具体的に言うと、 x \lt y ならば  \left( B^{x} - B^{x-1} \right) \lt \left( B^{y} - B^{y-1} \right) であることが重要です。

 B の差分がどんどん広がっていくわけですので、以下のように辺を張ると、上の頂点から貪欲にいくつか使用したもののみが最小費用流の解となりえることがわかるので、このように張ると良いです。

f:id:tsutaj:20200606180249j:plain

ソースコード

// フロー 略

int main() {
    int N, M; cin >> N >> M;
    vector<ll> A(N), B(N);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<N; i++) cin >> B[i];
    vector<ll> R(3);
    for(int i=0; i<3; i++) cin >> R[i];

    Flow<ll, ll> fl(2 + 3 + N + 3*N, LONGINF, LONGINF, LONGINF);
    int source = 3 + N + 3*N, sink = source + 1;
    for(int i=0; i<3; i++) {
        fl.add_edge(source, i, M, 0);
    }
    for(int r=0; r<3; r++) {
        for(int i=0; i<N; i++) {
            ll val = A[i];
            for(int j=0; j<=r; j++) (val *= B[i]) %= R[r];
            fl.add_edge(r, 3+i, 1, -val);
        }
    }
    for(int i=0; i<N; i++) {
        ll acc = 0;
        for(int r=0; r<3; r++) {
            ll val = A[i];
            for(int j=0; j<=r; j++) (val *= B[i]);
            fl.add_edge(3+i, 3+N+(3*i+r), 1, val - acc);
            acc += val - acc;
        }
    }
    for(int i=0; i<N; i++) {
        for(int r=0; r<3; r++) {
            fl.add_edge(3+N+(3*i+r), sink, 1, 0);
        }
    }

    ll ans = fl.mincost_flow(source, sink, 3*M);
    assert(ans != LONGINF);
    printf("%lld\n", -ans);
    return 0;
}

検定の問題としては要求知識がコアだな・・・と少し思いましたが、過去問の傾向見るとこんなもんかなという気もしますね。

第三回アルゴリズム実技検定 N 問題: 入れ替えと並び替え

問題概要

原文はこちら

atcoder.jp

長さ  N の数列  A = \left( a_{i} \right) があり、 A ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計  Q 回行った後、最終的にできた数列を出力せよ。

  • 整数  1 \leq x \lt N が与えられるので、 a_{x} a_{x+1} を交換する。
  • 整数  1 \leq l \leq r \leq N が与えられるので、 a_{l}, a_{l+1}, \ldots, a_{r} を昇順にソートする。

制約

  •  1 \leq N \leq 2 \times 10^{5}
  •  1 \leq Q \leq 2 \times 10^{5}

解説

愚直にやると間に合いそうにないので、何か発想の転換が必要です。まずはどうやったら時間内に処理できそうかを考えてみましょう。

1 番目のクエリは隣り合っている要素を swap するだけなので簡単に  O(1) で実現可能です。以降、2 番目のクエリをどうするかを考えます。まず、準備のため 転倒数 という概念を次のように定めます。

  • 数列  A = \left( a_i \right) のうち、 1 \leq l \lt r \leq N かつ  a_{l} \gt a_{r} を満たす相異なるインデックス  (l, r) の総数を 転倒数 とよぶ。

例えば  A = \left[ 3, 4, 1, 5, 2 \right] という数列に関して転倒数を考えると、インデックスのペア  (1, 3), (1, 5), (2, 3), (2, 5), (4, 5) について上記の条件を満たすので、転倒数は  5 となります。

さて、はじめに与えられる  A は昇順にソートされていることから、転倒数は  0 であることがわかります。また、 1 番目のクエリにおいて、swap される前の要素に関して  a_{x} \lt a_{x+1} ならば転倒数は  1 増え、 a_{x} \gt a_{x+1} ならば転倒数は  1 減ることがわかります。これらのことから、次のようなことが言えます。

  • ある 2 番目のクエリについて、それ以前に発生した 1 番目のクエリの回数を  q とするとき、2 番目のクエリの対象となる数列の転倒数は 高々  q である。

つまり転倒数が  O(Q) であることが言えるというわけです。ある範囲をソートするという操作は、言い換えるとその範囲内の転倒数が  0 となるようにすることですので、転倒数  q に対して  O(f(q)) (ここで  f(q) は計算量に関する関数) で対処できるようなソートアルゴリズムがあるならば、慣らし計算量  O(f(Q)) で元の問題を解くことができます。

さて、ここで問題となるのはどのようなソートアルゴリズムを持ってくるかですが、自分は本番で  f(q) = q \log qアルゴリズムを作って解きました。次でその概要を簡単に説明します。

ソートアルゴリズム

 a_{k} \gt a_{k+1} を満たす  k の集合を管理することを考えます。初期状態ではこのような要素は存在しないため空集合です。

1 番目のクエリで  a_{x}, a_{x+1} について swap の操作が行われるとき、 (a_{x-1}, a_{x}), (a_{x}, a_{x+1}), (a_{x+1}, a_{x+2}) の高々 3 つのペアについて大小関係が入れ替わる可能性があります。これらを更新することで、次の状態に対応する集合が得られます。この操作は、例えば C++ の場合ですと std::set で  O(\log q) で実現できます。

2 番目のクエリでは  l \leq x \lt r を満たす全ての  x について (これは swap をした結果新たに生まれる  x も含む) swap をすればソートができますが、先程の議論からこのような要素の数は高々  q なので、集合を更新しながら転倒数を減らすのは全体で  O(q \log q) で処理できます。

ソースコード

上の解説とちょっと違います ( a_{k} \gt a_{k+1} を満たす  k+1 の集合を管理してます)

int main() {
    int N, Q; cin >> N >> Q;
    set<int> ind;    
    vector<int> A(N);
    iota(A.begin(), A.end(), 1);
    while(Q--) {
        int t, x, y; cin >> t >> x >> y;
        if(t == 1) {
            x--;            
            for(int k=-1; k<=1; k++) {
                // x+k と x+k+1 との比較 -> x+k+1 のほうを削除
                if(x+k < 0 or x+k+1 >= N) continue;
                if(A[x+k] > A[x+k+1]) ind.erase(x+k+1);
            }
            swap(A[x], A[x+1]);
            for(int k=-1; k<=1; k++) {
                if(x+k < 0 or x+k+1 >= N) continue;
                if(A[x+k] > A[x+k+1]) ind.emplace(x+k+1);
            }
        }
        if(t == 2) {
            x--;            
            while(true) {
                auto ptr = ind.upper_bound(x);
                if(ptr == ind.end() or *ptr >= y) break;

                int u = *ptr - 1;
                for(int k=-1; k<=1; k++) {
                    // u+k と u+k+1 との比較 -> u+k+1 のほうを削除
                    if(u+k < 0 or u+k+1 >= N) continue;
                    if(A[u+k] > A[u+k+1]) ind.erase(u+k+1);
                }

                swap(A[u], A[u+1]);

                for(int k=-1; k<=1; k++) {
                    if(u+k < 0 or u+k+1 >= N) continue;
                    if(A[u+k] > A[u+k+1]) ind.emplace(u+k+1);
                }
            }
        }
    }
    for(int i=0; i<N; i++) printf("%d%c", A[i], " \n"[i + 1 == N]);
    return 0;
}

結構面白い問題だなと思いました。慣らし計算量に関する良い題材ですね。