結果

問題 No.31 悪のミックスジュース
コンテスト
ユーザー yuma25689
提出日時 2015-11-17 14:59:24
言語 Perl
(5.40.0)
結果
WA  
実行時間 -
コード長 4,003 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 7,072 KB
実行使用メモリ 53,892 KB
最終ジャッジ日時 2024-09-13 15:59:11
合計ジャッジ時間 3,093 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
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