結果

問題 No.31 悪のミックスジュース
ユーザー yuma25689yuma25689
提出日時 2015-11-17 15:13:50
言語 Perl
(5.38.2)
結果
AC  
実行時間 325 ms / 5,000 ms
コード長 4,010 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 5,156 KB
実行使用メモリ 53,340 KB
最終ジャッジ日時 2023-10-12 17:18:55
合計ジャッジ時間 3,273 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,724 KB
testcase_01 AC 150 ms
36,844 KB
testcase_02 AC 150 ms
37,860 KB
testcase_03 AC 224 ms
53,340 KB
testcase_04 AC 325 ms
53,096 KB
testcase_05 AC 323 ms
52,968 KB
testcase_06 AC 3 ms
4,620 KB
testcase_07 AC 276 ms
53,108 KB
testcase_08 AC 272 ms
53,108 KB
testcase_09 AC 219 ms
53,340 KB
testcase_10 AC 3 ms
4,712 KB
testcase_11 AC 6 ms
5,360 KB
testcase_12 AC 78 ms
21,520 KB
testcase_13 AC 2 ms
4,716 KB
testcase_14 AC 237 ms
48,784 KB
testcase_15 AC 4 ms
4,844 KB
testcase_16 AC 15 ms
6,528 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+1);
@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