このページについて
このページは、paiza ラーニング内に開設されているコンテンツ「レベルアップ問題集」で取り扱われているプログラミング課題について、独自の見解を述べたものです。
見解については、paizaラーニングの規約に基づき、許可されている範囲でのみ公開していますが、その内容については paiza とは一切関係なく、また paiza の立場を反映したものではありませんのでご注意ください。
挑戦する課題
レベルアップ問題集の日付セットから「連休を伸ばす1 (paizaランク B 相当)」を取り上げます。
以下は、問題公開 Web ページからの引用です。
問題
ある連続する
N日が休業日か営業日かのリストが与えられます。
L日までの有休を使って作ることができる最長の連休の日数を求めてください。
ただし、
- 連休とは連続する休業日の数です。
- 有休を1日使うとある営業日を休業日にすることができます。
入力される値
以下の形式で、整数 Nと Lが1行目で与えられ、2行目で N日の各日が休業日か営業日かのリストが与えらます。
|
1 2 |
N L B_1 B_2 B_3 ... B_N |
- 入力例
|
1 2 |
7 1 1 0 0 1 1 0 1 |
- 出力例
|
1 |
4 |
期待する出力
以下のような形式で、答えを出力してください。
|
1 |
A |
考え方
基本的な考え方は、与えられた有給休暇分、出勤日を休暇にし、その中から再長となる休暇数を調べることです。
効率的な方法は色々あるかと思いますが、ここでは力技で解いてゆくことにします。
たとえば、休暇日を 1 とし、出勤日を 0 、与えられる有給休暇数を 1としたとき、出勤予定表が次のようだったとします。
|
1 |
1 0 0 1 1 0 1 |
このとき、一番最初に現れる出勤日から順番に有給休暇を埋めていきます。
すると、パターンとしては
|
1 2 3 |
1) 1 1 0 1 1 0 1 2) 1 0 1 1 1 0 1 3) 1 0 0 1 1 1 1 |
の3つのパターンが考えられます。
今度はこの3つのパターンを連続した
1で構成される2次元配列に変形します。
つまり、
|
1 2 3 |
1) [[1 1], [1 1], [1]] 2) [[1], [1 1 1], [1]] 3) [[1], [1 1 1 1]] |
という感じに変形します。
その後、配列内の各配列に対し、含まれる 1の数を求め、その最大値を計算します。すると、
|
1 2 3 |
1) [[1 1], [1 1], [1]] -> 2 2) [[1], [1 1 1], [1]] -> 3 3) [[1], [1 1 1 1]] -> 4 |
という具合に求まり、最終的に連続して取得できる有給休暇数は「4日」という結果を得ることが可能となります。
ここで気をつけなければならないのは、入力パターンとして、「最初から全ての日付が休暇だった」というパターンもあり得るということです。
それを確認するため、
firstindex(of:) の戻り値をオプショナルバインディングで確認し、出勤日が見つからなかった場合には、入力された出勤簿の数をそのまま休暇数として求める作業をおこなっています。
つまり、
sa を出勤簿の配列とした場合、
|
1 2 3 4 5 6 |
if let i = sa.firstIndex(of: "0") { // 出勤日が見つかった場合 } else { // 全て休日だった場合（つまり、与えられた出勤表に 0 がなかった場合) max = sa.joined().count } |
という具合で処理をおこなっています。
解答例
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
// 連続数 N と有給数 L を取り込む let ia = readLine()!.split(separator: " ").map { Int($0)! } // 出勤表を取り込み、文字の配列にする let sa = readLine()!.split(separator: " ").map { String($0) } // 休暇の最大数 var max = 0 // 最初の営業日のインデックスを取得する if let i = sa.firstIndex(of: "0") { // スキャン開始のインデックスを、最初の営業日から最終営業日まで逐次変更する for j in i..<sa.count { // 有給休暇数をコピー var y = ia[1] // 出勤表をコピー var h = sa // 有給休暇数がなくなるまで、最初の営業日から最終営業日までスキャン for index in j..<sa.count where y > 0 { // 出勤日が見つかったら、休暇に変更し、有給数を減らす if h[index] == "0" { h[index] = "1" y -= 1 } } // 出勤表を連結し、有給で埋めきれなかった出勤日で区切った配列を作る。 // 次に、その中で最大長の要素数を得る。 let m = h.joined() .split(separator: "0") .max()! .count // 過去最大の長さであれば、max にその長さを代入する if m > max { max = m } } } else { // 全て休日だった場合（つまり、与えられた出勤表に 0 がなかった場合) max = sa.joined().count } // 結果出力 print(max) |
