Last Person to Fit in the Bus

アルゴリズム概要

ステップバイステップ解説

Python / pandas 実装

import pandas as pd
import numpy as np

def last_passenger(queue: pd.DataFrame) -> pd.DataFrame:
    """
    turn(1〜N の連続整数)を 0-indexed の配列インデックスとして直接利用。
    ソートを O(N log N) argsort → O(N) 直接配置に置換し、
    線形探索を O(log N) searchsorted に置換する。

    Returns:
        pd.DataFrame: 列 ['person_name'] の 1 行
    """
    n = len(queue)

    # numpy 配列に一括変換（pandas オーバーヘッドを排除）
    turns   = queue['turn'].to_numpy() - 1    # 0-indexed に変換
    weights = queue['weight'].to_numpy()
    names   = queue['person_name'].to_numpy()

    # 🔑 turn を直接インデックスとして使い O(N) で配置（argsort 不要）
    weights_sorted = np.empty(n, dtype=np.int64)
    names_sorted   = np.empty(n, dtype=object)
    weights_sorted[turns] = weights
    names_sorted[turns]   = names

    # 累積和（単調増加が確定）
    cum_w = weights_sorted.cumsum()           # O(N)

    # 🔑 searchsorted: 単調増加列への二分探索 O(log N)
    # side='right': 1000 より大きくなる最初の位置 → -1 で最後の有効位置
    last_pos = np.searchsorted(cum_w, 1000, side='right') - 1

    if last_pos < 0:
        return pd.DataFrame({'person_name': []})

    return pd.DataFrame({'person_name': [names_sorted[last_pos]]})


# ─────────────────────────────────────────────
# 別解: 可読性重視（Beats ~83%）
# ─────────────────────────────────────────────
def last_passenger_readable(queue: pd.DataFrame) -> pd.DataFrame:
    return (
        queue
        .sort_values('turn')                        # 計算用ソート
        .assign(cum_w=lambda df: df['weight'].cumsum())
        .loc[lambda df: df['cum_w'].le(1000), ['person_name']]
        .tail(1)
        .reset_index(drop=True)
    )

WITH cum AS NOT MATERIALIZED (
  SELECT
    person_name,
    turn,
    SUM(weight) OVER (
      ORDER BY turn
      ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS cum_w
  FROM Queue
)
SELECT person_name
FROM cum
WHERE cum_w <= 1000
ORDER BY cum_w DESC   -- 単調増加のため turn DESC と等価、再ソートを省略
LIMIT 1;

処理フローチャート

フローの説明：
1. DataFrame を numpy 配列に変換し pandas オーバーヘッドを排除します。
2. turn が 1〜N の連続整数であることを利用し、直接インデックスとして配置（O(N)）することで argsort を不要にします。
3. cumsum() で単調増加な累積和を O(N) で生成します。
4. np.searchsorted(..., side='right') - 1 で二分探索 O(log N) により最後に乗れる位置を特定します。
5. 対応する人物名を返却します。

計算量分析