Pythonで不正投票（重複投票）を検出する方法

選挙システムなどでは、同じ有権者が複数回投票していないかをチェックする仕組みが重要になります。この記事では、Pythonを使って重複投票を効率的に検出するアルゴリズムを紹介します。

問題の定義

投票データを表すリストが与えられます。リストの各要素は2つの値を持っており、[c_id, v_id] の形式になっています。

• c_id：候補者ID
• v_id：投票者ID

この中に、2回以上投票している有権者が存在するかどうかを判定するのが目的です。

入力例

[[5, 1], [5, 0], [5, 4], [5, 3], [5, 0]]

この場合、[5, 0] が2回登場しているため、出力は True（不正あり）となります。

解決のアプローチ

最もシンプルかつ効率的な方法は、集合（set）を利用することです。手順は以下の通りです。

• 空の集合を作成する（例：all_votes）
• すべての投票データを順に処理し、各投票の投票者ID（vote[1]）を集合に追加していく
• 処理後、集合のサイズと投票リストの長さを比較する
  • サイズが異なれば、同じ投票者が複数回登録されている＝不正投票あり → True
  • サイズが同一なら、全員が1回ずつしか投票していない → False

集合には重複した要素が自動的に排除されるという特性があるため、この比較だけで重複の有無を簡単に判定できます。

実装例

class Solution:
    def solve(self, votes):
        seen = set()
        for vote in votes:
            seen.add(vote[1])
        return len(seen) != len(votes)

ob = Solution()
votes = [[5, 1], [5, 0], [5, 4], [5, 3], [5, 0]]
print(ob.solve(votes))

実行結果

入力

[[5, 1], [5, 0], [5, 4], [5, 3], [5, 0]]

出力

True

[5, 0] が重複しているため、正しく True が出力されました。

計算量について

このアルゴリズムの計算量は以下のようになります。

• 時間計算量： O(n) — 投票リストを一度だけ走査すればよいため
• 空間計算量： O(n) — 集合に最大 n 個の投票者IDを格納するため

ネストされたループで全ペアを比較する O(n²) の方法と比べて大幅に高速であり、大量の投票データでも実用的に動作します。