📖
AtCoder Beginner Contest 340 C - T-shirts 備忘録 PHP
PHPで解いています。
問題はこちら。
解のポイント
リセットまでの区間の最大値を求める
- 今回は予定がない日にすべてTシャツを洗濯する→Tシャツの在庫が元に戻る
つまりリセット日までの間にロゴTがどれだけ必要か?=ロゴTが必要な最大値を求めることがポイントである
ロゴTはなるべく買いたくない。つまり無地Tを先に使う
ロゴTの必要枚数が増えるごとに記録する
ロゴTの現在の枚数を配列に記録し、最後に最大値をmax関数で取得するのが効率的。
コード
復習のためメモ多めです。
16ms
<?php
list($N, $M) = explode(" ", trim(fgets(STDIN)));
$A = str_split(trim(fgets(STDIN)));
// 無地T初期値
$plane = $M;
// ロゴT初期値
$logo = 0;
// ロゴT必要枚数を配列で保持
$logo_arr = [];
// 日程数
$day = count($A);
for($i = 0; $i < $day; $i++) {
if($A[$i] == 0) {
// 予定がない:洗濯するのでリセット
$logo_arr[] = $logo;
$plane = $M;
$logo = 0;
} elseif($A[$i] == 1) {
if($plane > 0) {
$plane--;
} else {
$logo++;
}
$logo_arr[] = $logo;
} elseif($A[$i] == 2) {
$logo++;
$logo_arr[] = $logo;
}
}
echo max($logo_arr) . PHP_EOL;
Discussion