弱小PHPerの憂鬱

https://paiza.jp/poh/kirishima

> ※ 実際のプロジェクトではこの様には行きませんので、人員を増やす場合は慎重に検討する事をお勧めいたします。

1万円の下請けってどんなところなんだろうか。
まあ典型的なナップザック問題なので、さっくり解いてしまいましょう。

<?php
	// 入力をパース
	$input = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
		// 1行目は必要人数
		$ninzuu = (int)$input[0];
		// 2行目は会社数 使わない
		// $kaishasuu = (int)$input[1];
		// 3行目以降は人数+価格 最大50社しかない
		unset($input[0]);unset($input[1]);
		$list = array_map(function($a){
			// 0=>人数,1=>価格
			$t=explode(' ', $a, 2);
			return [(int)$t[0],(int)$t[1]];
		}, $input);
	
	// 動的計画法
	$data = [0=>0];
	foreach($list as $key1=>$val1){
		// 1社で越えている場合は0にだけ足せばいい
		if($val1[0]>=$ninzuu){
			if(isset($data[$val1[0]])){
				$data[$val1[0]] = min($data[$val1[0]], $val1[1]);
			}else{
				$data[$val1[0]] = $val1[1];
			}
			continue;
		}
		
		foreach($data as $key2=>$val2){
			// 既に人数を越えている場合は計算不要
			if($key2 >= $ninzuu){ continue; }
			
			// 対象人数の金額を登録
			$num = $key2+$val1[0];
			if(isset($data[$num])){
				// 既に値がある場合は安い方
				$data[$num] = min($data[$num], $val2+$val1[1]);
			}else{
				$data[$num] = $val2+$val1[1];
			}
		}
	}
	
	// 最低人数越えのキーのうち、最低金額のものを選択
	$minTotal = 250000000;
	foreach($data as $key=>$val){
		if($key >= $ninzuu && $val < $minTotal ){
			$minTotal = $val;
		}
	}
	print($minTotal . PHP_EOL);

普通に動的計画法を適用しただけです。
実に簡単ですね。
人数をキーにしたせいで動的計画法というより総当たりになってしまった気もしますがまあいいや。
さっそく実行。

ようやく突破。ものすごくしょうもないところで詰まってた。 http://t.co/FEQmErTYki #paizahack_lite

— ラナ・クアール (@rana_kualu) 2014, 8月 1

http://paiza.jp/poh/kirishima/result/bebdc876df9e6cd24b4ee916a06eeea3

Test case 1	通過	実行時間： 0.01 秒
Test case 2	通過	実行時間： 0.01 秒
Test case 3	通過	実行時間： 0.01 秒
Test case 4	通過	実行時間： 0.01 秒
Test case 5	通過	実行時間： 0.01 秒
Test case 6	通過	実行時間： 0.27 秒
Test case 7	通過	実行時間： 3.33 秒

あっさり合格しました。
めでたし。

まあ、ここに辿り着くまでに実は2回も失敗しているのですが。

とりあえず作ってみたらテスト5でコケた。 やはりいきなり突破は無理か。 http://t.co/M9KLP5vFf8 #paizahack_lite

— ラナ・クアール (@rana_kualu) 2014, 7月 30

http://paiza.jp/poh/kirishima/result/4f809703f962fdb735dd00dd83943b22

最初、何も考えずに『単価の安い順に足していく』という頭の悪すぎる実装をやってしまいテスト5で失敗。
10人でいいプロジェクトに単価の安い100人を送り込まれてもねえ。

本気で実装してみたが何故かテスト7に失敗。 http://t.co/Q65KNKOsDE タイムアウトやメモリオーバーならともかく間違い？意味がわからんぞ？？？ #paizahack_lite

— ラナ・クアール (@rana_kualu) 2014, 7月 31

http://paiza.jp/poh/kirishima/result/a5ec246afdb9c754e44f003bae62ab97

まじめに考えてきちんと動的計画法を適用したのに何故かテスト7だけ失敗。
その日は何処にも間違う要素無いだろうがーなんでだーと延々悩んで結局答えが出なかったのですが、翌日見直してみたら
    $minTotal = 5000000;
とか書いてあって即死。
いやあこれは酷い。

さてこのアルゴリズム、テスト7では3秒以上かかっていますが、PHPで既に0.01秒というおかしな値が達成されています。
いったい果たしてどんな書き方がなされているのでしょうか。