paizaオンラインハッカソンVol.1に挑戦

ここ何回か PHP の最適化について書いていますが、実はこの企画にチャレンジしています。
新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.1

以下、提出したコードを掲載しています。自力でチャレンジしている方は御注意ください。

最初はごく普通に、データを読んで重複除去してソートして、というコードを書いていたのですが、手元でサンプルデータを作って計測してみたところ、どうやらそういった前処理にかかる時間が全体の大半を占めるようでした。

一方、リンク先の問題設定をみてもらうとわかるように、10 ～ 100 万の範囲で 20 万点サンプリングするということは、それが単純に一様分布から取られたサンプルであれば、大半のケースにおいては設定価格に極めて近いところで簡単に答えが見つかりそうです。

そこで、ある価格の商品が存在するかどうかを表す 1,000,001 要素のビット列を走査するという開き直ったコードを書いてみたところ、0.22/0.04/0.24 と高速に計算できました*1。
yさんの採点結果[100点 CTOに昇進しました！]｜paizaオンラインハッカソンVol.1

<?php

# 高速化のため標準入力を変数に代入する
$stdin = STDIN;

# 商品数とキャンペーン日数の読み込み
list ($num_products, $num_days) = fscanf($stdin, '%d %d');

# ある価格の商品が存在するかを示す配列
# $exists[$price >> 5] & (1 << ($price & 31)) が 0 でなければ $price の商品が存在する
$exists = array_fill(0, (1000001 + 31) >> 5, 0);

# ある価格の商品が二つ以上存在するかを示す配列
# 使い方は $exists と同様
$has_many = array_fill(0, (1000001 + 31) >> 5, 0);

# 商品価格を読み込み $exists と $has_many を初期化する
for ($i = $num_products; $i; --$i) {
    $price = (int) fgets($stdin);
    $index = $price >> 5;
    $mask = 1 << ($price & 31);
    if ($exists[$index] & $mask) {
        $has_many[$index] |= $mask;
    } else {
        $exists[$index] |= $mask;
    }
}

# キャンペーン設定価格の読み込み
$target_prices = array();
for ($i = $num_days; $i; --$i) {
    $target_prices[] = (int) fgets($stdin);
}

# 設定価格の高い順に並び替える
# これにより最悪計算量を O(D * P^2) から O(P^2) に改善できる
arsort($target_prices);

# 結果を格納する配列
$best_prices = array(0, $num_days, 0);

# 最良価格を初期化
# 初回の計算を必ず発生させるために最大価格 100 万円 + 1 を設定しておく
$best = 1000001;

foreach ($target_prices as $day => $target) {
    # 設定価格の高い順に調べているので
    # 前回の $best が今回の設定価格以下なら $best は今回の設定価格に対しても最良
    if ($target < $best) {
        # 設定価格から降順に調べていく
        # 商品の最低価格は 10 円なので 20 円未満になったところで打ち切る
        for ($best = $target; $best >= 20; --$best) {
            for ($i = 10, $j = $best - 10; $i < $j; ++$i, --$j) {
                # $i + $j = $best になるような価格 $i < $j の商品が共に存在すれば発見
                if ($exists[$i >> 5] & (1 << ($i & 31)) && $exists[$j >> 5] & (1 << ($j & 31))) {
                    break 2;
                }
            }
            # $i * 2 = $best になるような価格 $i の商品が複数存在すれば発見
            if ($i == $j && $has_many[$i >> 5] & (1 << ($i & 31))) {
                break;
            }
        }
        # $best_prices は 0 で初期化しているので、見つからなかった場合はそのまま終了
        if ($best < 20) {
            break;
        }
    }
    # 最良価格を設定
    $best_prices[$day] = $best;
}

# 結果を表示
for ($i = 0; $i < $num_days; ++$i) {
    echo $best_prices[$i] . "\n";
}

このコードは今回のテストデータに対しては高速に動いたのですが、最悪計算量はひどいもので、商品数を N, 価格範囲を P とすると O(N + P^2) になります。以下のデータを読ませた場合に、実際に最悪の場合が発生します。10 円の商品が二つだけ存在するところで、100 万円になる組み合わせはあるか、99 万 9999 円になる組み合わせはあるか、と、100 万行 100 万列の行列のほぼ全域を走査するので、都合 1 テラ回のループが発生する計算になります。

2 1
10
10
1000000

商品価格、キャンペーン設定価格がどちらも一様分布からサンプリングされるとして、商品数と処理時間の関係をグラフにしてみました。手元の環境での実験なので提出結果の処理時間と直接の比較はできませんが、商品数の少ないところで処理時間が爆発してしまう様子がわかります。商品数が多い方ではデータ読み込みのコストが支配的になります。比較として、商品価格でソートして走査する真っ当なプログラムも実装してみました*2。商品数 50,000 あたりで逆転しているようです。

*1:コード中、設定価格のソートや $best = 20 での打ち切りを行わない状態のものも提出したところ、0.23/0.04/0.23 でした。使われているテストデータに対しては、このあたりの高速化は特に効果がないようです。

*2:実際はもちろん、こちらを先に書いています。こちらのプログラムはテストケース 3 で 0.54 秒でした。