合計がsとなる配列の最大中央値を求めるC++プログラム

問題概要

2つの整数 n と s が与えられます。要素の合計がちょうど s と等しくなるような、n 個の非負の要素からなる配列を考えたとき、その中央値として実現可能な最大値を求めます。

例えば、入力が n = 3、s = 5 の場合、出力は 2 になります。これは、配列 [1, 2, 2] を考えると、合計が 5 で中央値が 2 となり、これより大きい中央値は実現できないからです。

解法のアプローチ

この問題は、次の手順で解くことができます。

• 配列を昇順に並べたとき、中央値より前に位置する下位 n / 2 個の要素は、すべて 0 にしても構いません。
• すると、残りの合計 s を中央値以降の (n / 2) + 1 個の要素で均等に分け合うのが最適な戦略になります。
• したがって、答えは s を m = (n / 2) + 1 で割った商(小数点以下切り捨て)となります。

m := (n / 2) の切り捨て + 1
return (s / m) の切り捨て

C++での実装例

以下の実装を見ると、理解がさらに深まるでしょう。

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

int solve(int n, int s) {
    int m = n / 2 + 1;
    return s / m;
}
int main() {
    int n = 3;
    int s = 5;
    cout << solve(n, s) << endl;
}

入力

3, 5

出力

2

まとめ

このアルゴリズムの計算量は O(1) と非常に効率的です。ポイントは、「中央値より小さい側の要素を極力小さくし、余った合計を中央値以上の要素に均等に振り分ける」という発想です。整数除算が自動的に切り捨てを行う性質を活かすことで、シンプルな割り算だけで最大の中央値を求められるのが魅力です。