結果

問題 No.31 悪のミックスジュース
ユーザー yuma25689yuma25689
提出日時 2015-11-17 14:59:56
言語 Perl
(5.38.2)
結果
WA  
実行時間 -
コード長 4,006 bytes
コンパイル時間 109 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 53,624 KB
最終ジャッジ日時 2024-09-13 16:50:24
合計ジャッジ時間 2,698 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,816 KB
testcase_01 AC 134 ms
37,144 KB
testcase_02 AC 140 ms
38,388 KB
testcase_03 AC 210 ms
53,624 KB
testcase_04 AC 200 ms
53,212 KB
testcase_05 AC 197 ms
53,336 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 256 ms
53,368 KB
testcase_08 AC 256 ms
53,416 KB
testcase_09 AC 200 ms
53,536 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 7 ms
6,944 KB
testcase_12 AC 72 ms
21,884 KB
testcase_13 WA -
testcase_14 AC 219 ms
49,128 KB
testcase_15 AC 5 ms
6,944 KB
testcase_16 AC 14 ms
7,296 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Scalar value @input[0] better written as $input[0] at Main.pl line 12.
Scalar value @input[1] better written as $input[1] at Main.pl line 13.
Scalar value @fruit_costs[0] better written as $fruit_costs[0] at Main.pl line 41.
Main.pl syntax OK

ソースコード

diff # 

# ほぼ他の方のサンプルを見て理解しようとしながら写しただけみたいな・・・

# use List::Util 'min';

# N V
# C1 .. Cn
$INF = 10e16;

$input=<STDIN>;
chomp($input);
@input=split(/ /, $input);
$fruits_type_count=@input[0];
$goal_liter=@input[1];
$input=<STDIN>;
chomp($input);
@fruit_costs=split(/ /, $input);
$cost_summary = 0;
for($i=0;$i<@fruit_costs;$i++)
{
	$cost_summary += $fruit_costs[$i];
}

if( $goal_liter <= $fruits_type_count )
{
	# 目標値がフルーツの種類の数以下ならば
	# すべてのフルーツを１リットル買って終了
	print "$cost_summary\n";
	exit(0);
}

# 果物のコストを、下記のように集計する
# sum[k] = cost[0] + cost[1] + ... + cost[k]
# その意味は、
# kを１個買うとき、それより小さいindexの果物もすべて最低で1つは買わなければならない
# (indexが小さいものほど、量が多いというルールだから)
# そのため、kを1個買うということは、それ以下indexのすべてのジュースを１個ずつ買うということになり、
# この集計結果は、それを考慮した(k以下のすべてのジュースも１個ずつ買った金額の集計になった)金額になっているということ？
# それを使えば、kのジュースを買う場合の最小の額でルールが満たされる事にもなる

# 集計の配列
@sum_fruit_costs=(@fruit_costs[0]);
for($i=1;$i < @fruit_costs; $i++)
{
	push( @sum_fruit_costs, $sum_fruit_costs[$i-1] + $fruit_costs[$i] );
}

# とりあえずまあ、全部一個ずつ買った状態にする
# それも最低条件の１つ
# print(acc_fruit_costs[fruits_type_count-1])
$alreadyCaluculatedCost = $cost_summary;
$goal_liter-=$fruits_type_count*1;

# さらに、目標値が大きい場合、通常のdpでは時間がかかりすぎるので、目標値を削る
# 基本的に、同じリットルを買った際に一番コストの小さいフルーツをできるだけたくさん買う。
# リットル単価の安い物？
# 全部のフルーツを舐められるギリギリくらいまでリットルを残せばその方法で減らせるはず？
$minCostIndex=0;
for($i=0; $i < @sum_fruit_costs;$i++)
{
	if( $sum_fruit_costs[$i] * ($minCostIndex+1) < $sum_fruit_costs[$minCostIndex] * ($i+1) )
	{
		$minCostIndex = $i;
	}
}

# print( $minCostIndex."\n");


# 上記で、最もコストが小さいものを求めた
# ラスト100個(フルーツ数個)のフルーツを選べれば良いレベルまで減らして良い？
# 多分、ラスト100個はフルーツのリットル単価のみでは計算できない
# つまり、すべてのフルーツ(100個)を舐められるだけのリットル(フルーツ数2乗+フルーツ数くらいあれば良い？)を残してそのフルーツを買う
# 多分・・・多分・・・
$literCalcByDp = $fruits_type_count**2 + $fruits_type_count;
$minCostFruitBoughtCount = 0;
if( 0 < $goal_liter - $literCalcByDp )
{
	# ある程度($literCalcByDp)よりも目標リットルが大きい
	# 上記方法でそこまで削減する
	$minCostFruitBoughtCount = int(($goal_liter - $literCalcByDp) / ($minCostIndex+1));
}

$goal_liter -= $minCostFruitBoughtCount * ($minCostIndex+1);
$alreadyCaluculatedCost += $minCostFruitBoughtCount * $sum_fruit_costs[$minCostIndex];

# print( "\n".$goal_liter."\n");
# print( $alreadyCaluculatedCost."\n");
# print($minCostFruitBoughtCount*($minCostIndex+1)."\n");

# dp用配列定義
$arr_count = $goal_liter * $fruits_type_count;
@dp = ($INF)x$arr_count;

$dp[0]=0;
# dp
for( $i=0; $i<$goal_liter; $i++ )
{
	# iリットル時の最小コスト
	for( $j=0; $j<$fruits_type_count; $j++ )
	{
		# 全種類のフルーツをループ
		# フルーツ(index=$j)を加えた時の最小コスト
		if( $dp[$i] + $sum_fruit_costs[$j] < $dp[$i+$j+1])
		{
			$dp[$i+($j+1)] = $dp[$i] + $sum_fruit_costs[$j];
		}
	}
}

print $alreadyCaluculatedCost + $dp[$goal_liter]."\n";
0