AtCoder ABC 282 E - Choose Two and Eat One (青色, 500 点)

これをグラフの問題だと思えるかどうか！

• 問題へのリンク

問題概要

箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は ​ である。

箱の中に 2 個以上のボールが残っている限り、下記の行動を繰り返す。

• 箱の中から 2 つのボールを選んで取り出す
• 取り出した 2 つのボールに書かれた整数をそれぞれ としたとき、 を得点として獲得する
• その後、取り出した 2 つのボールのうち、片方を削除して、もう片方を箱に戻す

合計得点としてあり得る最大値を求めよ。

制約

• 
• 
• 

考えたこと

まず最初に考えたことは「 などという設定」はほとんど意味がないであろうということだった。本当は の行列を与えて、ボール に対して操作する得点は であるというようにしてもいいくらいの感じだろうと思った。それだと入力が多くなるので、乱数っぽいものを用意したのだろうと。

というわけで、サンプル 1 について、 の表にしてみる。

	ボール 1	ボール 2	ボール 3	ボール 4
ボール 1	x	2	5	2
ボール 2	2	x	7	8
ボール 3	5	7	x	7
ボール 4	2	8	7	x

元の問題は、この表から 個の整数を選んだ総和が最大にするということになる。ただし、本当に大きい順に 3 つ選ぶことはできない。

この表の場合の最適解は (1, 3)、(2, 4)、(3, 4) である (ボール を選ぶことを と表記している)。

たとえば、(2, 3)、(2, 4)、(3, 4) とすれば、7 + 8 + 7 = 22 と大きくなるのに、それができないのはなぜだろうか？？　まず気づくのはボール 1 が登場していないこと。そして、下図のように、ボール 2, 3, 4 がループしてしまっていることだ。

ループしているとダメみたい。たとえば、ボール 2, 3 を選んでボール 3 を消したとする。次にボール 2, 4 を選んでボール 3 を消したとする。そしたら、ボール 4 だけが残るので、最後にボール 3, 4 を選ぶことはできない。

ボールを選ぶ順序や、消すボールをどっちにするかを、どのように選んでもダメだ。

グラフで考える

ここから先はグラフでちゃんと考えることにする。頂点数 の完全グラフだ。このグラフから 本の辺を選ぶ問題と言える (選んだ辺は「操作のために選ぶ 2 つのボールの組」に相当する)。

先ほどの観察から「選ぶ辺の集合によってループが形成されてはいけない」ということが言えそうだ。

実際これは容易に証明できる。もし 辺からなるループができたとする。このとき、どの順序で辺を選んだとしても、 回目の作業を終えた時点で、 個あったボールは残り 1 個になってしまう。最後の 回目の作業ができないのだ。

以上から、選ぶ辺集合がループを形成しないことが必要条件だと言えた。つまり、全域木になることが必要だということだ。

全域木ならすべて作れる

逆に、任意の全域木は、上手に「2 つのボールを選ぶ順序」と「どちらのボールを消すか」を設定することで実現できる。

具体的には、以下のことを繰り返せば良い。このように「葉から順に処理していく」という考え方はよく見かける。

---

• まだ残っているボール (に対応する頂点) のうち、葉を 1 つ選ぶ
• その葉に接続している辺の両端に対応する 2 つのボールを取り出す
• 葉に対応する側のボールを食べる

---

これを繰り返すことで、「取り出した 2 つのボールに対応する辺の集合」が所望の全域木になるようにすることができる。

最大全域木問題

以上より、この問題は「最大全域木問題」に帰着された。最小全域木問題は有名。それと同じ方法で最大全域木問題も解ける。つまり、Kruskal 法を辺が重い順に適用していけばよい。

Kruskal 法はたとえばけんちょん本では 15 章に書いた。

計算量は となる。なお余談だが、Prim 法を priority_queue を用いずに書く方法で にすることもできる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

// a^n mod m
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// Union-Find
struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

using pint = pair<int,int>;  // 頂点対
using Edge = pair<long long, pint>;  // 重み付き辺

int main() {
    // 入力
    long long N, M;
    cin >> N >> M;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // すべての辺を求めて、重い順にソート
    vector<Edge> edges;
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            long long cost = (modpow(A[i], A[j], M) + modpow(A[j], A[i], M)) % M;
            edges.push_back(Edge(cost, pint(i, j)));
        }
    }
    sort(edges.begin(), edges.end(), greater<Edge>());

    // Kruskal 法の適用
    long long res = 0;
    UnionFind uf(N);
    for (auto e : edges) {
        long long add = e.first;
        int u = e.second.first, v = e.second.second;
        if (uf.issame(u, v)) continue;
        res += add;
        uf.merge(u, v);
    }
    cout << res << endl;
}

AtCoder ARC 111 A - Simple Math 2 (緑色, 300 点)

上手に整理すれば、とてもシンプルな問題！

• 問題へのリンク

問題概要

正の整数 が与えられる。

を で割った商 を で割ったあまりを求めよ。

制約

• 
• 

考えたこと

で割るような操作を 2 回しているので、 を で割った余りを考えるとよいのだろうなというあたりをつける。

を で割ったときの商を 、あまりを として、

とおく。さらに、 を で割ったときの商を 、あまりを とすると

と表せることになる。さて、このとき、 と表せることから、次のことが読み取れる。

---

• を で割ったときの商は に一致する
• さらに、 を で割ったあまりは に一致する
• したがって、求める値は である

---

よって、この問題は「 を で割ったあまりを で割った商」を求めることで解ける。

計算量は となる。

コード

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

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    long long N, M;
    cin >> N >> M;
    cout << modpow(10LL, N, M * M) / M << endl;
}

yukicoder No.2066 Simple Math !

floor sum のいい感じの練習問題！

• 問題へのリンク

問題概要

正整数 が与えられる。

非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。

( 個の入力ケースが与えられる)

制約

• 
• 

考えたこと

いかにも二分探索という問題。次の判定問題を考える。

---

以上 以下の整数のうち、 という形で表せる整数の個数を求めよ

(この値が 個以上である最小の が答え)

---

「 という形で表せる正\整数」をまともに数えるのは大変なので、できれば の組を数える方に帰着させたい。

そこで、 を最大公約数 で割っておくことにする。その状態で答えを求めて、最終的に答えに をかければよい。よって、 は互いに素であると仮定してよい。

を一意にするために

が互いに素であるならば、次のことが言える。

---

とするとき、整数 に対して、

を満たす整数 の値の組はただ つに定まる

---

よって、 の範囲で を動かしていき、 となるような の個数を足していけばよい。

と変形できる。 のとき、 個であるとわかる。これを合算していく。floor sum が使える。

このままだと の係数が負になっているので、次のように設定する。

• 
• 
• 
• 

こうして、floor sum を適用すればよい。計算量は対数の 2 乗オーダーとなる。

コード

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

// sum_{i=0}^{n-1} floor((a * i + b) / m)
// O(log(n + m + a + b))
// __int128 can be used for T
template<class T> T floor_sum(T n, T a, T b, T m) {
    if (n == 0) return 0;
    T res = 0;
    if (a >= m) {
        res += n * (n - 1) * (a / m) / 2;
        a %= m;
    }
    if (b >= m) {
        res += n * (b / m);
        b %= m;
    }
    if (a == 0) return res;
    T ymax = (a * n + b) / m, xmax = ymax * m - b;
    if (ymax == 0) return res;
    res += (n - (xmax + a - 1) / a) * ymax;
    res += floor_sum(ymax, m, (a - xmax % a) % a, a);
    return res;
}

// calc #n that can be expressed n =  Px + Qy (P, Q is coprime)
// 0 <= n <= M
long long calc_num(__int128 P, __int128 Q, __int128 M) {
    __int128 mp = M / P;
    __int128 N = min(mp + 1, Q);
    __int128 a = P, b = M + Q - a * (N - 1);
    return floor_sum(N, a, b, Q) - 1;
}

int main() {
    int CASE;
    cin >> CASE;
    while (CASE--) {
        long long P, Q, K;
        cin >> P >> Q >> K;

        long long G = gcd(P, Q);
        P /= G, Q /= G;

        long long low = -1, high = 1LL<<50;
        while (high - low > 1) {
            long long M = (low + high) / 2;
            if (calc_num(P, Q, M) >= K) high = M;
            else low = M;
        }
        cout << high * G << endl;
    }
}

yukicoder No.2032 Let's Write Multiples!!

floor sum の練習！

• 問題へのリンク

問題概要

以上 以下の の倍数をすべて十進表記で 1 回ずつ書き出した時、数字 が書かれる回数を求めよ。

(テストケースが 個与えられる)

制約

• 
• 
• 
• 

考えたこと

各桁ごとに考える。整数 の右から 桁めが である条件は

を で割ったあまりが 以上 未満である

と言い換えられる。さらに、次のように言い換えられる。

• の 桁めが であるとき、
• そうでないとき

よって、 以上 以下の の倍数の各桁について、 の値の総和を求めればよい。

計算量は となる。

コード

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

// sum_{i=0}^{n-1} floor((a * i + b) / m)
// O(log(n + m + a + b))
long long floor_sum(long long n, long long a, long long b, long long m) {
    if (n == 0) return 0;
    long long res = 0;
    if (a >= m) {
        res += n * (n - 1) * (a / m) / 2;
        a %= m;
    }
    if (b >= m) {
        res += n * (b / m);
        b %= m;
    }
    if (a == 0) return res;
    long long ymax = (a * n + b) / m, xmax = ymax * m - b;
    if (ymax == 0) return res;
    res += (n - (xmax + a - 1) / a) * ymax;
    res += floor_sum(ymax, m, (a - xmax % a) % a, a);
    return res;
}

int main() {
    int CASE;
    cin >> CASE;
    while (CASE--) {
        long long L, R, K, C;
        cin >> L >> R >> K >> C;

        // 0 以上 N 以下の整数についての答えを求める
        auto solve = [&](long long N) -> long long {
            long long res = 0;
            long long beki = 1;
            for (int k = 0; k <= 10; ++k) {
                long long upper = floor_sum(N/K+1, K, beki*(10-C), beki*10);
                long long lower = floor_sum(N/K+1, K, beki*(9-C), beki*10);
                res += upper - lower;
                beki *= 10;
            }
            return res;
        };
        cout << solve(R) - solve(L-1) << endl;
    }
}

AtCoder ABC 283 Ex - Popcount Sum (橙色, 600 点)

floor sum と聞いて！！

• 問題へのリンク

問題概要

以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。

( ケース与えられる)

制約

• 
• 
• 

考えたこと

TL を見て、floor sum と知った上での考察。

「popcount の総和を求めよ」という設定自体から、とりあえず各桁ごとに求めればよさそうという推測は立つ。

桁目の値が になるものの個数を求めるために、その条件を言い換えていくことにする。まずよくあるのは、

の 桁目が である
を で割ったあまりが 以上 未満である

という言い換え。この言い換えは、たとえば次の問題で本質的に活躍する。この言い換えは苦手で、少し前に頑張って意識したので、今回はスムーズに出た。

drken1215.hatenablog.com

これは、次のように言い換えられる。

つまり、元の問題は次のように言い換えられる。

---

以上 以下の で割って あまる整数 について、

の総和を求めよ。

---

さらに

とおくと、 の条件は

となる。最終的な答えは、 とおいて、

と表せる。この値は floor sum で求められる。計算量は となる。

コード

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

// sum_{i=0}^{n-1} floor((a * i + b) / m)
// O(log(n + m + a + b))
long long floor_sum(long long n, long long a, long long b, long long m) {
    if (n == 0) return 0;
    long long res = 0;
    if (a >= m) {
        res += n * (n - 1) * (a / m) / 2;
        a %= m;
    }
    if (b >= m) {
        res += n * (b / m);
        b %= m;
    }
    if (a == 0) return res;
    long long ymax = (a * n + b) / m, xmax = ymax * m - b;
    if (ymax == 0) return res;
    res += (n - (xmax + a - 1) / a) * ymax;
    res += floor_sum(ymax, m, (a - xmax % a) % a, a);
    return res;
}

int main() {
    int CASE;
    cin >> CASE;
    while (CASE--) {
        long long N, M, R;
        cin >> N >> M >> R;
        long long range = (N - R) / M + 1;

        long long res = 0;
        for (int k = 0; k <= 30; ++k) {
            long long upper = floor_sum(range, M, R + (1LL<<k), 1LL<<(k+1));
            long long lower = floor_sum(range, M, R, 1LL<<(k+1));
            res += upper - lower;
        }
        cout << res << endl;
    }
}