【Swift】（前編: K=1のケース）AtCoder競プロ典型 90 問「001 - Yokan Party (★4) 」

概要

• AtCoder:　001 - Yokan Party (★4) の部分的な解説
• スライディングウインドウ法を使って解いてみたかったので、記事を書いた。

• K=1のケースをスライディングウインドウ法で解答
• K>=2のケースは後日投稿予定

該当コード

import Foundation

var NL = readLine()!.components(separatedBy: " ").map{ Int($0)! }
var L = NL[1], N = NL[0]
var K = Int(readLine()!)!
var As = readLine()!.components(separatedBy: " ").map{ Int($0)! }
var maxLength = 0

if K == 1 {
    print(activate())
} 

func activate() -> Int {
    for right in 0 ..< As.count {
        let answer = min(L-As[right], As[right])
        maxLength = max(maxLength, answer)
    }
    return maxLength
}

解説

• K=1の場合は、forループとminとmaxを使った比較で行ける
• K=1すなわちピースは2つに分かれるのだから、このうち最小のスコアをmaxLengthに入れて更新していけばよい。
• ただし、この場合だとK>=2の場合に対応できないので、mid high rowを使った二分探索と貪欲法なる方法を使って検知していくらしい。
  • スライディングウインドウ法を覚えたので使ってみたかった。

テストケース

解答例１

3 34
1
8 13 26

// 出力：13　OK

解答例３

3 100
1
28 54 81

// 出力：46　OK

参考