POH Lite 天才火消しエンジニア霧島 3.33秒

3.33秒 / 0.01秒

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

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);

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

https://twitter.com/rana_kualu/status/495214956573229056
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回も失敗しているのですが。

https://twitter.com/rana_kualu/status/494452573533773825
http://paiza.jp/poh/kirishima/result/4f809703f962fdb735dd00dd83943b22

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

https://twitter.com/rana_kualu/status/494821947201421312
http://paiza.jp/poh/kirishima/result/a5ec246afdb9c754e44f003bae62ab97

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

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