問題
N個のショップがある。座標 X_i に位置し、商品価格 C_i。座標 0 から出発し座標 L に到達する。以下の条件で購入合計を最小化せよ。
- 各ショップは最大1回訪問可
- 訪問したショップでは必ず購入
- 訪問するショップの X 座標は昇順（後戻り禁止）
- 出発から最初のショップまで、最後のショップから L までの距離合計 ≤ K
入力形式
N L K
X_1 C_1
...
X_N C_N制約
$1 \le N \le 1000$
$1 \le L \le 10^9$
$0 \le K \le L$
$0 \le X_i \le L$
$1 \le C_i \le 10^9$
入出力例
入力例 1
4 10 3
2 100
5 200
7 150
9 50出力例 1
150{X=2, X=9} → C=100+50=150。距離=(2-0)+(10-9)=3 ≤ K=3。
ヒント (段階的開示)
ヒント1: 方向性
全探索で「最初のショップ i と最後のショップ j の組み合わせ」を試す。
ヒント2: アプローチ
途中のショップは買わなくてよい（コスト最小化）。C[i] + C[j] が最小の組を探す。
ヒント3: 誘導
for i in range(N):
if X[i] > K: continue
for j in range(i, N):
if X[j] < L - K: continue
ans = min(ans, C[i] + C[j])模範解答 (Python)
N, L, K = map(int, input().split())
shops = []
for _ in range(N):
x, c = map(int, input().split())
shops.append((x, c))
ans = float('inf')
for i in range(N):
xi, ci = shops[i]
if xi > K:
continue
for j in range(i, N):
xj, cj = shops[j]
if xj < L - K:
continue
ans = min(ans, ci + cj)
if ans == float('inf'):
print(-1)
else:
print(ans)Step-by-Step 解説
1制約の読み解き
最初のショップ条件
最初のショップ条件
X[i] ≤ K、最後のショップ条件 X[j] ≥ L - K。
2途中のショップは不要
i と j を決めたら、間のショップで買わないのが最適。
i と j を決めたら、間のショップで買わないのが最適。
3O(N²) 全探索
N=1000 で O(N²)=10^6 → 十分高速。
N=1000 で O(N²)=10^6 → 十分高速。
次のステップ
- 使ったアルゴリズム: 全探索 / 条件フィルタリング / 最小値更新
- 次回予告: DFS基礎（Phase 3 突入）