OUPC2022 A「Grouping」解説

はじめに

「Grouping」writer の Badlylucky です。

OUPC2022 にご参加いただき、ありがとうございました。OUPC2021 で A 問題枠を担当しましたが、OUPC2022 でも A 問題枠を担当しました。

問題

A「Grouping」

$A$ 以上 $B$ 以下の数を $N$ で割ったあまりでそれぞれ分類する問題です。

解法

解法1: 愚直に分類する

$A$ 以上 $B$ 以下の数の総数、$B-A+1$ はたかだか $2\times10^5 + 1$ であり、すべての数に対してどのグループに所属するかを愚直に計算しても十分間に合います¹。

必要になるグループは所属する数の個数が最大になるものと最小になるものだけですが、事前にどのグループが最大・最小になるか分からないため全グループについて集計します。

グループごとの集計は配列を使って実現します。

この解法の C++ での実装例を下に示します。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int A, B, N;
    cin >> A >> B >> N;
    vector<int> group(N, 0);
    for (int i = A; i <= B; i++) {
        int r = ((i % N) + N) % N;
        group[r]++;
    }
    int groupMax = -1;
    int groupMin = B - A + 2;
    for (int i = 0; i < N; i++) {
        groupMax = max(groupMax, group[i]);
        groupMin = min(groupMin, group[i]);
    }
    cout << groupMin << " " << groupMax << endl;
    return 0;
}

解法2: 数学的に計算する

丁寧に考察すると、実は所属する数の個数が最大になるものと最小になるもののグループに所属する数の個数の差は、$0$ か $1$ にしかならないことが分かります。

$A$ を $N$ で割ったあまりを $r_A$ 、$B$ を $N$ で割ったあまりを $r_B$ とします。簡単のため、以降の議論では $A, B \geq 0$ 、 $r_A = 0$ の場合について考えます。

このとき、適当な正の整数 $q_{A}, q_{B} (q_{A} \leq q_{B})$ を使って、$A = q_{A}N, B = q_{B}N + r_B$ と表せます。$A$ 以上 $B$ 以下の整数は漏れなく対象の数の中に入っていることを考慮すると、$A$ 以上 $B$ 以下の数の中には、あまりが $0$ 以上 $N-1$ 以下のグループの数が $q_B - q_A$ 個ずつと $0$ 以上 $r_B$ 以下のグループの数が $1$ 個ずつあることが分かります。

よって $r_B = N-1$ のときに限り所属する数が最大になるグループと最小になるグループの所属する数の個数は等しくなり、それ以外のケースでは所属する数が最大になるグループと最小になるグループの所属する数の個数の差はちょうど $1$ となります。

これは一般の $A, B$ についても成立します。$A$ 以上 $B$ 以下の数の集合を $k$ ずらして $A+k$ 以上 $B+k$ 以下の数の集合に置き換えることは、この問題においてはあまりのグループを $k$ ずらすのと同義であり、全体の個数に変化はありません。したがって、$A, B \geq 0$ について、$A' = A + k = 0$ となるように $A, B$ をずらすことで $r_A = 0$ の場合と同じケースにできます。

また、$A, B$ が負の場合でも、$-10^5 \leq A \leq B \leq 10^5$ の区間を $0 \leq A \leq B \leq 2\times10^5$ のようにずらすことで $A,B \geq 0$ 、$r_A = 0$ の場合と同じように計算することができます。

これらをまとめると $r_B - r_A = N-1 \pmod{N}$ のときに限り最大値と最小値はともに $\left\lfloor \dfrac{B - A + 1}{N} \right\rfloor$ となり、それ以外のときは最小値は $\left\lfloor \dfrac{B - A + 1}{N} \right\rfloor$ 、最大値は $\left\lfloor \dfrac{B - A + 1}{N} \right\rfloor + 1$ となります。

この解法の C++ での実装を下に示します。

#include <iostream>
using namespace std;
int main() {
    int A, B, N;
    cin>> A >> B >> N;
    int minGroup = (B - A + 1) / N;
    int maxGroup = minGroup;
    if ((B - A + 1) % N > 0) {
        maxGroup++;
    }
    cout<< minGroup << " " << maxGroup << endl;
    return 0;
}

1. この問題の元の案では、$-10^9 \leq A \leq B \leq 10^9$ でしたが、C++ の場合それでもコンパイル時の最適化が効いて間に合いました。 ↩