結果

問題 No.31 悪のミックスジュース
ユーザー yuma25689yuma25689
提出日時 2015-11-17 15:13:50
言語 Perl
(5.38.2)
結果
AC  
実行時間 321 ms / 5,000 ms
コード長 4,010 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 6,816 KB
実行使用メモリ 54,016 KB
最終ジャッジ日時 2024-09-14 15:52:36
合計ジャッジ時間 3,278 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
testcase_01 AC 136 ms
37,248 KB
testcase_02 AC 141 ms
38,544 KB
testcase_03 AC 211 ms
53,888 KB
testcase_04 AC 321 ms
53,632 KB
testcase_05 AC 321 ms
53,624 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 269 ms
53,632 KB
testcase_08 AC 255 ms
53,632 KB
testcase_09 AC 203 ms
54,016 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 8 ms
6,016 KB
testcase_12 AC 74 ms
22,016 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 220 ms
49,408 KB
testcase_15 AC 5 ms
5,376 KB
testcase_16 AC 14 ms
7,168 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