AtCoder が提供しているABC（AtCoder Beginner Contest）361 C問題をC++とPythonで解いてみました。ABC361は、2024年7月6日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Make Them Narrow（Difficulty : 342）
問題の詳細は、リンク先をご覧ください。
ソートして、前からと後ろから要素を抜いて考えます。AtCoder Problems による Difficulty は 342 でした。
解答案
配列 A の要素をソートしても、その結果は変わりません。$K$ の要素を引いて、残りの最大値と最小値の差を求めます。つまり、残り $N-K$ の連続する数列の最大値と最小値の差の最小値を求めます。
C++ プログラム例（ABC361C）
ソートして、$n – k$ 個の要素の一番後ろの要素と一番前の要素の差の最小値を求めます（19行目）。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
int main()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
int result = INF;
int t = n - k - 1;
for (int i = 0; i + t < n; ++i) {
result = min(result, a[i + t] - a[i]);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC361C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 361 C"""
INF = 10**9 + 1
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
result = INF
t = n - k - 1
for i in range(n - t):
result = min(result, a[i + t] - a[i])
print(result)どちらも「AC」と判定されました。
最後に
今回は、C問題とD問題の難易度の差が大きかった気がします。
引き続き ABC の問題を紹介していきます。
