忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/05/25 02:45 |
POH Lite 20万人月プロジェクト
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://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回も失敗しているのですが。


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

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


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

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

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


2014/08/01 23:37 | Comments(0) | PHP

コメント

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<買ったものリスト 2014/08/03 | HOME | DateTime::getTimestamp()すると日付が変わる件>>
忍者ブログ[PR]