#59459 (Perl) No.31 悪のミックスジュース

• 問題: No.31 悪のミックスジュース
• ユーザー: yuma25689
• 提出日時: 2015-11-17 14:59:24
• 言語: Perl (5.38.2)
• 結果: WA
• 実行時間: -
• コード長: 4,003 bytes
• コンパイル時間: 256 ms
• コンパイル使用メモリ: 7,072 KB
• 実行使用メモリ: 53,892 KB
• 最終ジャッジ日時: 2024-09-13 15:59:11
• 合計ジャッジ時間: 3,093 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	4 ms; 6,940 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	4 ms; 6,944 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-

コンパイルメッセージ

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

ソースコード

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

# 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";