Pythonで最大人口となる年を求めるプログラムの書き方

問題の概要

ここでは、birth(出生年)と death(死亡年)の2列を持つ表を考えます。各行は i 番目の人物の出生年と死亡年を表しています。ある年 y の「人口」とは、その年に生存している人数のことです。i 番目の人物は、y が閉区間 [birth_i, death_i − 1] に含まれる場合に、年 y の人口としてカウントされます(死亡した当年は数えません)。この条件のもとで、人口が最大となる年のうち、最も早い年を求めるのが目的です。

入力例

この場合、出力は 1960 になります。1960年には2人(1960年生まれ〜2020年没の人と、1940年生まれ〜1970年没の人)が生存しており、これが最大人口だからです。1970年にも2人が生存しますが、より早い年である1960年が答えとなります。

解き方のアプローチ

この問題を解くためには、以下の手順に従います。

• d := キーが存在しない場合に 0 を返すマップ(defaultdict)を用意する

• res := 初期値として [2051, 0] を持つリストを用意する(2051年より後は対象外と仮定)

• matrix 内の各 (YOB: 出生年, YOD: 死亡年) のペアについて処理を行う

  • range(YOB, YOD) の各年 year に対して次を実行する

    • d[year] := d[year] + 1(その年の人口を1増やす)

    • d[year] >= res[1](現在の最大人口以上)である場合

      • d[year] > res[1](最大人口を更新する)ならば

        • res := [year, d[year]] を設定する

      • そうでなければ(同じ人口だが別の年の場合)

        • res := [min(year, res[0]), res[1]](より早い年を採用する)

• 最後に res[0](最大人口の最も早い年)を返す

それでは、理解を深めるために実際の実装を見てみましょう。

実装例(Python)

from collections import defaultdict
def solve(matrix):
    d = defaultdict(int)
    res = [2051, 0]
    for YOB, YOD in matrix:
        for year in range(YOB, YOD):
            d[year] += 1
            if d[year] >= res[1]:
                if d[year] > res[1]:
                    res = [year, d[year]]
                else:
                    res = [min(year, res[0]), res[1]]
    return res[0]
matrix = [[1970,2010],[1960,2020],[1940,1970]]
print(solve(matrix))

入力

[[1970,2010],[1960,2020],[1940,1970]]

出力

1960

コードのポイント

この実装では、collections.defaultdict(int) を使うことで、まだキーが存在しない年に対しても自動的に初期値 0 が設定され、シンプルに人口カウントを加算できます。また、死亡年そのものは範囲に含めないよう range(YOB, YOD) としている点が重要です。計算量は人物数を n、寿命の長さを L とすると O(n × L) となり、差分配法(imos法)を使えば O(n + 年幅) まで高速化することも可能です。