競技プログラミング

ABC305 A – Water Station

画像をクリックで問題に飛べます

イントロダクション

この問題では、全長100kmのマラソンコースに設置された給水所の位置を考えます。スタートから5kmごとに給水所が設置されており、スタート地点とゴール地点を合わせて21箇所の給水所があります。我々の目標は、マラソンコースの特定の位置(N km)にいる高橋くんに最も近い給水所がどこであるかを見つけることです。

問題の詳細説明

マラソンコースの全長は100kmで、スタートから5kmごとに給水所が設置されています。高橋くんはコースのNkm地点に位置しています。最も近い給水所の位置を求めてください。

高橋くんの位置(N)は0から100までの任意の整数です。そして、この問題の制約の下では、最も近い給水所は必ず1つに定まります。

問題の要素解説

この問題の中心的な要素は「距離」です。高橋くんの位置から最も近い給水所を見つけるためには、全ての給水所と高橋くんとの距離を計算し、最も小さい距離を見つける必要があります。

しかし、問題は給水所がスタートから5kmごとに配置されているという規則性を利用して簡略化することができます。つまり、高橋くんの位置Nを5で割った余りを計算し、その余りが2.5以下なら最も近い給水所はNを5で割った値(切り捨て)に5を掛けた位置に、余りが2.5より大きいならそれに5を掛けた位置にあると判断できます。

解答戦略

上述の問題の要素解説に基づいて、以下の解答戦略を採用します。

  1. 高橋くんの位置Nを5で割り、その余りを求めます。
  2. その余りが2.5以下なら、Nを5で割った値(切り捨て)に5を掛けた値が最も近い給水所の位置であると出力します。
  3. 余りが2.5より大きいなら、それに5を掛けた値を最も近い給水所の位置であると出力します。

コードの解説

Swiftでの実装は以下の通りです。

let N = Int(readLine()!)!
let div = N / 5
let mod = N % 5

if mod <= 2 {
print(div * 5)
} else {
print((div + 1) * 5)
}

ここでは、まず高橋くんの位置Nを入力として受け取ります。次に、Nを5で割った商と余りをそれぞれ計算します。その余りが2以下であれば、商に5を掛けた値(すなわち、Nを5で割った値を切り捨ててから5を掛け直した値)を出力します。それ以外の場合、つまり余りが2より大きい場合は、商に1を足してから5を掛けた値を出力します。これは、Nが次の給水所を通り越している場合に対応します。

コード全文

以下に、前述のコードを全文で示します。



let N = Int(readLine()!)!
let div = N / 5
let mod = N % 5

if mod <= 2 {
    print(div * 5)
} else {
    print((div + 1) * 5)
}

このコードは、Swiftの標準入力から高橋くんの位置Nを読み取り、その位置から最も近い給水所の位置を計算して出力します。

テストケースと実行結果

以下に、いくつかのテストケースとその実行結果を示します。

  1. 入力: 53 出力: 55
  2. 入力: 21 出力: 20
  3. 入力: 100 出力: 100

これらのテストケースでは、すべての出力が期待通りであり、高橋くんの位置から最も近い給水所の位置を正しく計算しています。

考察と最適化

この問題の解答戦略とコードは、既に最適化されています。給水所が均等に配置されているという規則性を利用して、すべての給水所との距離を計算する代わりに、高橋くんの位置を5で割ることで、直接最も近い給水所の位置を計算します。このアプローチにより、解答の計算時間はO(1)となり、高速で効率的です。

結論

この問題は、問題の特性と規則性を理解し、それを利用して効率的な解答戦略を開発することを示しています。我々の解答戦略とコードは、高橋くんの位置から最も近い給水所を効率的かつ正確に見つけることができます。

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

この記事が役立つと感じた方、または改善の提案や質問がある方は、ぜひコメントを残してください。皆さんからのフィードバックをお待ちしています。

COMMENT

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