C - 花壇の植え付け / Planting the Flower Bed Editorial
by 
MMNMM
\(N=1\) のとき、隣り合うポイントが存在しないので、どのポイントを選んでも条件を満たします。 最も左にあるポイントと最も右にあるポイントが一致するので、これらの距離は常に \(0\) になります。 よって、\(N=1\) なら答えは \(0\) です。
以下では、\(N\ge2\) のときについて考えます。
条件を満たす選び方が存在するなら、その選び方で最も左にあるポイントをポイント \(1\) に、最も右にあるポイントをポイント \(M\) に置き換えた選び方も条件を満たします。 よって、答えは条件を満たす選び方が存在しなければ \(-1\) 、存在すれば \(D _ 1+D _ 2+\cdots+D _ {M-1}\) となります。
条件を満たす選び方が存在するかは、貪欲法を使って判定することができます。 具体的には、ポイントを先頭から確認し、直前に選んだポイントとの距離が \(K\) 以上（もしくはまだポイントをひとつも選んでいない）ならそのポイントを選ぶことを繰り返して \(N\) 個以上のポイントを選べるかどうか判定すればよいです。
証明
\(X _ i\) を、ポイント \(1\) とポイント \(i\) との距離として定めます（つまり、\(X _ i=D _ 1+D _ 2+\cdots+D _ {i-1}\) です）。 ポイントは左から順に番号付けられているので、\(X _ i\lt X _ {i+1}\) です。
貪欲法で \(L\) 個のポイントが選べたとし、選んだポイントをポイント \(I _ 1,I _ 2,\ldots,I _ L\) とします。 \(L\ge N\) なら、先頭の \(N\) 個を選べば条件を満たすように \(N\) 個のポイントを選ぶことができます。 逆に、条件を満たす \(N\) 個のポイントがあれば、\(L\ge N\) となることを示します。
条件を満たす \(N\) 個のポイントの選び方をひとつとり、ポイント \(J _ 1,J _ 2,\ldots,J _ N\) とします。 ポイントの満たす条件から、\(X _ {J _ {i+1}}-X _ {J _ i}\ge K\) が成り立ちます。 貪欲法の選び方から、\(X _ {I _ {i+1}-1}-X _ {I _ i}\lt K\le X _ {I _ {i+1}}-X _ {I _ i}\) が成り立ちます。
すべての \(1\le i\le\min\lbrace L,N\rbrace\) に対して、\(I _ i\le J _ i\) が成り立つことを示します。 \(1=I _ 1\le J _ 1\) は明らかです。 ある \(1\le i\lt\min\lbrace L,N\rbrace\) をとり、\(I _ i\le J _ i\) が成り立つとします。 すると、\(X _ {I _ {i+1}-1}-X _ {J _ i}\le X _ {I _ {i+1}-1}-X _ {I _ i}\lt K\le X _ {J _ {i+1}}-X _ {J _ i}\) なので \(X _ {I _ {i+1}-1}\lt X _ {J _ {i+1}}\) となり、\(I _ {i+1}-1\lt J _ {i+1}\) が成り立ちます。 これらから、すべての \(1\le i\le\min\lbrace L,N\rbrace\) に対して、\(I _ i\le J _ i\) が成り立つことが示せました。
このことから、貪欲法においてこれまでに選んだポイントが \(N\) 個未満なら、\(J _ N\) までに距離が \(K\) 以上のポイントがあることがわかります。 よって、貪欲法は \(N\) 個以上のポイントを選び、\(L\ge N\) が示されました。
あとは、この貪欲法に従って判定を行えばよいです。 時間計算量は \(O(N)\) になります。
実装例は以下のようになります。
#include <iostream>
using namespace std;
int main() {
int N, M;
long K;
cin >> N >> M >> K;
// N = 1 なら、答えは 0
if (N == 1) {
cout << 0 << endl;
return 0;
}
// 左端から右端までの距離
long sum_D = 0;
// 最後に選んだポイントからの距離
long last_distance = 0;
// 選んだポイントの個数
int chosen = 1;
for (int i = 0; i < M - 1; ++i) {
int D;
cin >> D;
sum_D += D;
last_distance += D;
// 最後に選んだポイントから K 以上離れたら
if (last_distance >= K) {
++chosen; // そのポイントを選ぶ
last_distance = 0;
}
}
// N 個以上ポイントを選ぶことができたかで場合分け
if (chosen >= N) {
cout << sum_D << endl;
} else {
cout << -1 << endl;
}
return 0;
}
N, M, K = map(int, input().split())
if N == 1:
print(0)
exit()
# 左端から右端までの距離
sum_D = 0
# 最後に選んだポイントからの距離
last_distance = 0
# 選んだポイントの個数
chosen = 1
for D in map(int, input().split()):
sum_D += D
last_distance += D
# 最後に選んだポイントから K 以上離れたら
if last_distance >= K:
chosen += 1 # そのポイントを選ぶ
last_distance = 0
# N 個以上ポイントを選ぶことができたかで場合分け
if chosen >= N:
print(sum_D)
else:
print(-1)
posted:
last update: