C++で第2党が選挙に勝利するための最小投票数kを求める方法

問題概要

n個の要素を持つ配列Aがあるとします。ある学校にはn人の生徒がおり、それぞれがちょうどk票を持っていて、すべての票を使い切らなければなりません。政党は2つあります。A[i]は、i番目の生徒が第1党にA[i]票を投じたことを表し、その結果、第2党には残りのk − A[i]票が入ります。第2党が選挙に勝てるようにkを設定したい場合、kとして取り得る最小値を求めるのがこの問題です。

例えば、入力が A = [2, 2, 3, 2, 2] の場合、出力は5になります。第1党は 2 + 2 + 3 + 2 + 2 = 11 票を獲得しますが、k = 5 と設定すれば第2党は 3 + 3 + 2 + 3 + 3 = 14 票を獲得でき、選挙に勝利できるからです。

解法のポイント

この問題を効率的に解くために、次の2つの条件に着目します。

• 下限条件： 各生徒は手持ちのk票の中からA[i]票を第1党に渡すため、kは必ず配列Aの最大値m以上でなければなりません。
• 勝利条件： 第1党の合計得票数をsとすると、全票数は n × k です。第2党が勝つには n × k − s > s、つまり k > 2s / n が成立する必要があります。

したがって、答えは「m」と「2 × s / n + 1（整数除算）」の大きい方となります。

アルゴリズムの手順

n := 配列Aのサイズ
k を 0 から n 未満まで 1 ずつ増やしながら繰り返す:
    x := A[k]
    m := m と x の最大値
    s := s + x
m と (2 * s / n + 1) の最大値を返す

C++による実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
   int n = A.size(), k = 0, s = 0, m = 0;
   for (int k = 0; k < n; k++){
      int x = A[k];
      m = max(m, x);
      s += x;
   }
   return max(m, 2 * s / n + 1);
}
int main(){
   vector<int> A = { 2, 2, 3, 2, 2 };
   cout << solve(A) << endl;
}

入力

{ 2, 2, 3, 2, 2 }

出力

5

まとめ

このアルゴリズムは配列を一度走査するだけで答えが求まるため、時間計算量はO(n)と非常に効率的です。最大値mと合計sという2つの値から最適なkを直接計算できる点が大きな特徴です。