【日付セット】連休を伸ばす1 (paizaランク B 相当) 解答例 – PHP編【paiza】
【日付セット】 > 連休を伸ばす1 (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
個人的にかなり難しい問題でした。どうすれば結果を導けるのかと考え続けて数時間のたうち回ってた記憶がありますｗ；
こういう考え方ができればプログラムも楽しくなってくるんだろうなぁ。
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; $l = $input[1]; $array = explode(" ",trim(fgets(STDIN))); function holiday($i,$n,$l,$array){ $one = 0; $zero = 0; while(($i + $one + $zero) < $n){ if($array[$i + $one + $zero] == 1){ $one++; } else { if($zero == $l){ break; } $zero++; } } return $one + $zero; } $counter = 0; for($i = 0;$i < $n;$i++){ $tmp = holiday($i,$n,$l,$array); if($counter < $tmp){ $counter = $tmp; } } echo $counter; ?> |
解答方針
ポイントは「function holiday」の中です。このコード中が、「ある始点から何連休になるか」という検証プログラムになっています。この問題では連続するN日に対し、L日分の有休を使うことができるとあります。これはすなわち営業日を表す値「0」を休日を表す値「1」にすることができると考えることができます。「入力例2」を例として確認してみましょう
入力例2：7日の内、有休が1日分使用できる
・始点を一日目
一日目は休日である「1」が入ってるので「連休+1」となります。二日目は営業日である「0」ですが、有休を一回使うことができるので「1」として扱い、「連休+2」となります。三日目は有休ももう使えず、「0」なのでここで処理を中断させ、「連休は2日」となります。
・始点を二日目
2日目を始点と考えた場合、二日目は「0」ですが有休を使えるため「連休+1」となります。しかし三日目はもう有休を使えないため「連休+1」で処理は中断します。
このような処理をN回繰り返し、最も連休数が大きいものを更新していき答えを導いていきます。
各情報を取得する
|
1 2 3 4 |
$input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; //検証日数を取得 $l = $input[1]; //有給数を取得 $array = explode(" ",trim(fgets(STDIN))); //N日分のスケジュールを取得し配列に保存 |
連休を検証するプログラム部分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function holiday($i,$n,$l,$array){ //holiday関数を作成 $one = 0; //検査日が「1」だった回数 $zero = 0; //検査日が「0」だった回数 while(($i + $one + $zero) < $n){ //始点「i」日 + $one + $zero が「$n」より小さい場合、以降の処理を繰り返す if($array[$i + $one + $zero] == 1){ //検査日が「1」ならば $one++; //「1」を1増加させる } else { //「1」以外なら if($zero == $l){ //もし「$zero」が「$l」と一緒ならばループ処理を中断させる break; } $zero++; //「$zero」を1つ増やす } } return $one + $zero; } |
複雑に見えますが、検査日が「1」ならば「$one」が一つ増加し、「0」ならば「$zero」が一つ増加するシンプルなプログラムです。検査日「$i」日を始点として、有休が使えなくなった状態で「0」に当たるか、「$n」まで処理が終わったら終了するようになっています。そして処理終了後、「$one + $zero」が始点検査日からの連休となります。
N回、連休検査プログラムを動作させ、最大値を更新、出力する
|
1 2 3 4 5 6 7 8 |
$counter = 0; for($i = 0;$i < $n;$i++){ $tmp = holiday($i,$n,$l,$array); if($counter < $tmp){ $counter = $tmp; } } echo $counter; |
