競技プログラミング

競プロ典型 90 問 001 – Yokan Party(★4)

https://atcoder.jp/contests/typical90/tasks/typical90_a

イントロダクション

この記事では、Swiftを使った競技プログラミングについて取り組んだ問題を紹介します。対象とする問題は、特定の条件下で長さLのようかんを分割するというものです。

問題の詳細説明

我々の目の前には長さL[cm]のようかんがあり、N個の切れ目が付けられています。左からi番目の切れ目は左からA[i][cm]の位置にあります。あなたのタスクは、N個の切れ目のうちK個を選んでようかんをK+1個のピースに分割することです。ただし、最も短いピースの長さ(スコア)が最大となるように分割する必要があります。あなたの目標は、最大のスコアを出す分割方法を見つけることです。

問題の要素解説

この問題は主に2つの部分から構成されています。1つ目は、全てのピースの長さがx以上になるようにようかんを切断できるかどうかを確認する判定問題です。2つ目は、最大のスコア(最小のピースの長さの最大値)を見つけるための二分探索です。

解答戦略

我々の解答戦略は、判定関数を使用して全てのピースの長さが特定の値x以上になるように分割できるかを判定し、可能ならそのxをスコアとするというものです。これを行うために、xの値を二分探索で探します。

コードの解説

我々のコードはまず、ようかんの長さL、切れ目の数N、そして切れ目の位置Aを標準入力から読み込みます。次に、全てのピースの長さがx以上になるようにようかんを切断できるかどうかを判定する関数checkを定義します。この関数では、各切れ目の位置でxを超えたら切断するという操作を行います。最後に、二分探索を用いてスコアの最大値を求めます。

コード全文

import Foundation

// 入力
let inputs = readLine()!.split(separator: " ").map { Int($0)! }
let N = inputs[0]
let L = inputs[1]
let K = Int(readLine()!)!
let A = readLine()!.split(separator: " ").map { Int($0)! }

// 判定問題 (すべての長さを x 以上にすることは可能か?)
func check(_ x: Int) -> Bool {
    var num = 0  // 何個切れたか
    var pre = 0  // 前回の切れ目
    for i in 0..<N {
        // x を超えたら切断
        if A[i] - pre >= x {
            num += 1
            pre = A[i]
        }
    }
    
    // 最後のピースが x 以上なら加算
    if L - pre >= x {
        num += 1
    }
    
    return num >= K + 1
}

// 二分探索
var left = -1, right = L + 1
while right - left > 1 {
    let mid = (left + right) / 2
    if check(mid) {
        left = mid
    } else {
        right = mid
    }
}

print(left)

考察と最適化

今回の問題には、二分探索という強力な手法を使用して解決しました。これにより、効率的に最適解を見つけることが可能となりました。

結論

この記事では、Swiftを用いてある競技プログラミング問題に取り組み、問題解決のプロセスを詳しく解説しました。我々のアプローチとコードを通じて、二分探索や判定問題といった重要な概念について理解を深め、実際のプログラミングに役立てることができたでしょう。

コメントとフィードバックの募集

皆様からのフィードバックや質問を大歓迎します。コメント欄からお気軽にご意見や疑問点をお寄せください。我々と一緒に学び、成長していきましょう!

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です