POI 2011/2012 (~Platinum + eps) 풀이 및 후기

solved.ac 기준 플래티넘 아래쪽 문제들을 돌았다. Well 문제는 현재로서는 다이아지만 그냥 넣었다.

Letters

웰노운 유형이다. 만약 문자열의 모든 문자가 달랐다면 첫 번째 문자열의 문자들에 숫자를 1부터 순서대로 붙인 다음, 두 번째 문자열의 문자들을 \([1..n]\)로 이루어진 순열로 생각하고 inversion을 세면 된다. 문자열 중 같은 문자가 존재하면, 같은 문자끼리 swap을 하는 건 손해이므로 첫 번째와 두 번째 문자열에서 같은 문자끼리에도 순서를 부여할 수 있다. 즉 A라는 문자에 \(A_1, A_2, \ldots\)처럼 첨자를 붙여서 새로운 문자로 간주하고 앞서와 같은 과정을 반복하면 ok.

Distance

결국 두 수의 거리라는 것은 각각을 소인수분해했을 때 각 소인수의 지수의 차이의 합이다. 그러므로 \(l_1\) norm과 같으므로 문제에서 주어진 거리는 진짜 metric function이다. 따라서 문제를 \(D\)-dimensional space에 놓인 \(n\)개의 점 중 가장 가까운 점을 찾는 쿼리 문제로 다시 해석할 수 있다. 문제는 \(D=2\)만 해도 이 문제가 상당히 어렵다는 점에 있다. 정확히 생각은 안 해봤는데, 이런 문제가 나름 어렵기 때문에 \(10^6\) 이하의 모든 소수의 개수 \(10^5\)차원에서는 generalized problem을 해결하는 게 더 어렵다고 생각할 수 있다.

그러므로 이 문제에 한정한 특이점을 찾아야 하는데, 가장 먼저 떠올릴 수 있는 것은 관심 있는 공간의 크기가 딱 \(10^6\)개의 격자점을 포함하는 공간이라는 것이다. 왜냐하면 \(a\), \(b\)의 최단경로 상에 항상 \(gcd(a, b)\)가 놓이게 할 수 있는데, $$dist(a, b) = dist(a, gcd(a, b)) + dist(b, gcd(a, b)) = \left\lVert \frac{a}{gcd(a, b)} \right\rVert + \left\lVert \frac{b}{gcd(a, b)} \right\rVert$$가 성립하기 때문이다. 따라서 공간 내의 모든 점을 순회하는 무언가가 시간 안에 작동한다. 이 문제에서 \(gcd(a, b)\)라는 건 결국 일종의 트리에서의 LCA 역할과 비슷해진다는 점에 착안하여 다음과 같은 풀이를 만들 수 있다. \(gcd\)로 가능한 값 \(d\)를 전부 순회하면서 \(a_i\)들 중 \(d\)의 배수인 값들만 본다. 이 때 만약 어떤 \(a_k\)와 가장 가까운 점이 \(d\)를 최대공약수로 가진다고 하면, 그 점은 \(dist(x, d)\)가 최소인 점일 것이다. 만약 \(a_k\)가 \(dist(x, d)\)를 최소로 하는 값이라면 두 번째로 작은 값이 필요하다. 따라서 \(X\) 이하의 수들의 부분집합에서 약수를 전부 나열해도 \(XlogX\)개 이하이므로 (harmonic lemma) 이러한 풀이가 시간 내에 작동한다.

...를 떠올리고 적당한 문제라고 생각했는데, 정해는 이게 아니었고, 정해가 오히려 더 흥미로웠다. \(1, \ldots, 10^6\)을 각각 정점으로 가지고, \(\frac{j}{i} = p\) (\(p\)는 어떤 prime number)를 만족하면 \(i\)와 \(j\)를 간선으로 이은 그래프를 만들자. \(10^6\) 이하인 수가 가질 수 있는 서로 다른 소인수의 개수는 최대 7개이므로, 간선의 개수는 \(7\cdot10^6\)개를 넘지 않고 따라서 그래프를 explicit하게 구성할 수 있다. 이제 multisource bfs를 시행할 건데, source는 모든 \(a_i\) 값들이고, bfs를 돌면서 모든 정점에 '이 정점으로부터 가장 가까운 source와 그 거리'를 전부 계산할 수 있다. bfs가 끝난 이후에 모든 간선을 보면서, 간선 양 끝 점이 각각 \(a_i\)와 \(d_1\), \(a_j\)와 \(d_2\)만큼 떨어진 정점이었다고 하자. 이 때 \(a_i\), \(a_j\)에서 가장 가까운 점의 거리를 \(d_1+d_2+1\)로 update해준다 (더 작을 때 갱신). 모든 간선을 순회하면서 이 작업을 하면, 최종적으로 쓰인 거리가 답이 된다.

증명은 의외로 쉬운데, \(a_i\)와 가장 가까운 점이 \(a_j \neq a_i\)라고 해보자. \(a_i\)에서 \(a_j\)로 가는 경로 \(a_i = p_0, p_1, \cdots, p_n = a_j\)를 생각하자. 그러면 어떤 \(p_k\)와 \(p_{k+1}\)이 존재하여, bfs를 돌면서 계산된 가장 가까운 점이 \(p_k\)에서는 \(a_i\)이고 \(p_{k+1}\)에서는 \(a_j\)로 쓰여있다. 단순하게 생각하면 \(a_j\)에서 가장 가까운 점이 \(a_i\)라고 쓰여있지 않고 그 반대도 마찬가지이므로, 가까운 점에 대한 정보가 바뀌는 타이밍이 무조건 필요하다. 이걸 전부 확인해주면 된다는 논리이다. 따라서 시간복잡도는 \(O(V+E)\)이다.

Rendezvous

처음엔 왜 이 문제 제목만 영어가 아닌 걸까 싶었는데, 놀랍게도 이게 영단어였고, 뜻이 랑데부라는 걸 처음 알아서 매우 당황했다.

우리의 영원한 친구 functional graph에 관한 문제다. 그래프가 connected임을 가정하자. functional graph에는 사이클이 무조건 있고, 사이클을 제거하면 모든 간선이 루트로 향하는 트리들로 구성된 일종의 forest가 생긴다. 그럼 사실 해줄 수 있는 게 case work뿐이다. \(x\)랑 \(y\)가 만나는 위치가 사이클이면, 두 점이 사이클 위에서 모두 1칸 이상씩 움직이는 게 최적일 수는 없다. 따라서 \(x\)가 사이클에 도달했을 때 (혹은 출발지점일 때) 멈추는 정점인지, \(y\)가 멈춰있어야 되는지 두 경우를 전부 계산해보면 된다. \(x\)랑 \(y\)가 만나는 위치가 forest의 트리 중 하나이면, 그 트리에서 \(x\)와 \(y\)의 LCA 지점에서 만나는 게 최적이다. 필요한 정보들을 전부 전처리해주고 있으면 ok.

Well

가장 어려웠던 문제. \(z\)에 대한 이분탐색을 쓸 수 있다는 걸 생각하고 들어가자. 먼저 최소 한 위치가 \(0\)까지 파여야 한다는 조건이 없고 최소의 \(z\)만 구하는 게 목적이라면, '평탄화 작업'이라는 로직을 생각해볼 수 있다. 이 로직은 다음과 같이 생겼다.

for (int i=2; i<=n; ++i) x[i] = min(x[i], x[i-1] + z);
for (int i=n-1; i>=1; --i) x[i] = min(x[i], x[i+1] + z);

이 작업으로 인해서 \(\{ x_i \}\)가 \(\{ y_i \}\)로 변했다고 할 때, 이 수열은 적당히 삽을 파서 기울기가 \(z\) 이하가 되게 만든 임의의 가능한 땅의 상태 \(\{ z_i \}\)에 대해 \(z_i \leq y_i\)를 만족한다. 증명은 귀납법으로 가능하다. \(n=1\) 위치에서 첫 번째 루프를 실행하면 두 번째 칸이 \(\min(x[2], x[1]+z\) 높이를 가지는데, 이후 두 번째 루프의 마지막 시행 전까지의 과정은 길이 \(n-1\)인 수열에 대한 시행과 똑같으므로 귀납 가정을 사용할 수 있다. 마지막 시행을 합치면 잘 된다는 걸 확인할 수 있다.

그 다음에는 한 위치가 \(0\)이어야 한다는 걸 고려할 차례인데, 일단 단순하게 생각해보면 기울기가 \(\pm z\)인 역피라미드꼴 모양을 제거하는 시행 비스무리한 걸 하면 된다는 걸 알 수 있다. 그 때 제거되는 모래의 양이 얼마나 되는지 빠르게 판별할 수 있는지는 둘째치고, 우선 첫 번째 과정과 이를 어떻게 합칠지를 생각해보자. 그런데 직관적으로 생각해보면 \(0\) 깊이의 위치가 추가된다는 건 최종적인 수열을 \(\{ b_i \}\)라고 할 때, \(b_i \leq \lvert i-k \rvert z\)라는 조건을 하나만 추가하는 것이다. 그러므로 \(k\)를 중심으로 양쪽 어느 지점까지는 \(b_i \leq \lvert i-k \rvert z\) 조건이 높이를 결정하겠지만, 그 이후로는 원래의 수열 \(\{ x_i \}\)에 의해서 높이가 결정될 것이다. 따라서 일단 \(x_k = 0\)으로 바꾸고 평탄화 작업을 일일이 해보는 거나, 평탄화 작업을 먼저 하고 역피라미드를 없애는 거나 결과가 똑같으며, 결과가 똑같다면 후자도 최적해를 주는 로직임을 알 수 있다. 증명도 가능한데, 먼저 후자의 작업이 올바른 지형을 만든다는 증명을 먼저 하고, \(a_i \leq \lvert i-k \rvert z\) 조건이 추가된 임의의 수열 \(\{ a_i \}\)에 대해 \(a_i \leq b_i\)임을 보일 수 있다. 앞선 관찰로 인해서 \(a_i \leq y_i\)이고 \(b_i \leq y_i\)이기도 하다는 걸 이용하면 잘 된다.

그럼 역피라미드에 포함된 모래의 개수를 빠르게 세기만 하면 된다. 평탄화 작업을 끝낸 상태의 수열에서 생각하자. \(k\)의 깊이를 \(0\)으로 만들려고 할 때, 살아남는 왼쪽 지형에 포함되는 최대의 모래 양을 \(e[k]\)로 두자. \(e\) 배열을 다 채우는데 \(O(n)\)이 걸리게 하고 싶다. 어떤 위치 \(p\)에 대해서, \(p\) 위치에 구덩이가 파일 경우에는 모래가 남으면 안 되고, \(p+1\) 위치에 구덩이가 파일 경우에는 \(z\)개만큼의 모래는 남기게 할 수 있고, \(p+2\)에는 \(2z\)개만큼 남길 수 있다. 즉 살아남는 최대의 모래 양은 구덩이 위치에 대한 일차함수 꼴이다. 단 \(p + \lceil \frac{x_p}{z} \rceil\) 위치의 구덩이 이후로는 항상 \(x_p\)가 온전히 살아남기 때문에 이 때는 더 생각할 필요가 없다. 이 값을 배열에 일일이 쓰고 있으면 시간초과가 나겠지만, 계차를 미리 기록하고, 모든 모래 위치를 다 계산한 후 나중에 한꺼번에 등차 배열과 최종 값 배열을 계산한다고 생각하면 ok.

수식... 쓰기 좀 애매해서 말로 썼는데 굉장히 두서없어 보인다. 자세한 건 아래 코드 참조.

vector<int> lh(n+1, 0); // left hill
for (int i=1; i<=n; ++i) {
    if (i+1 <= n) lh[i+1] += z;
    if (i+1 + x[i]/z <= n) lh[i+1 + x[i]/z] -= z - x[i] % z;
    if (i+2 + x[i]/z <= n) lh[i+2 + x[i]/z] -= x[i] % z;
}

vector<ll> tot(n+1, 0);
ll d = 0, accum = 0;
for (int i=1; i<=n; ++i) {
    d += lh[i];
    accum += d;
    tot[i] += accum;
}

오른쪽도 똑같이 해주면 되고, \(z\)에 대해서 전체 과정을 이분탐색하면 끝나는데, 주의할 점이 두 가지 있다. 첫 번째는 \(z=0\)이면 위에서 한 논의들이 뭔가 굉장히 꼬이기 때문에 따로 예외처리를 해줘야 한다는 점이다. 두 번째는 BOJ에 스페셜 저지가 안 붙어있다는 점이다. 내가 파야 하는 spot의 최소 위치를 출력하면 맞는다. BOJ에서 POI 문제에 스페셜 저지가 안 붙어있다면, 보통 사전순 최소라는 조건을 달아서 답을 출력하면 맞는다. 반드시 BOJ를 써야 하는 이유가 없다면 그냥 폴란드 저지에서 채점을 하자.

Tour de Byteotia

정점이 \(n\)개인 undirected graph에서, 정점 번호가 \(1 \ldots k\)인 정점들 중 하나라도 사이클에 포함되지 않도록 그래프에서 간선을 최소 개수로 제거하라는 문제이다. 이 문제를 풀다 보면 아마 적당한 그리디 비슷한 전략을 구상해서 맞지 않을까 싶다. 나도 그렇게 접근을 해서 맞긴 했는데, 증명은 못 하고 냈었다.

끝점 중 하나라도 \(1 \ldots k\)에 속하는 간선들을 빨간색, 나머지를 파란색으로 칠하자. 그러면 빨간색 간선들만 골라서 최적해를 하나 만들 수 있음을 보일 수 있다. \(A\)를 파란색 간선의 개수가 최소인 최적해 중 하나라고 하자. 파란색 간선 중 하나를 \(A\)에서 제거했을 때도 조건을 만족하면 최적이라는 가정에 모순이므로, 이 간선을 포함하는 사이클 중에 어떤 것은 빨간색 간선 \(e\)를 포함하고 있어야 한다. 이제 파란색 간선을 \(e\)로 대치하여 \(A'\)을 만들자. \(e\)는 bridge였어야 하므로, 파란색 간선의 양 끝점은 bridge \(e\)에 대해 서로 반대편에 있었어야 한다. 따라서 같은 component 사이에서 bridge만 바꾼 셈이 되므로, 간선을 교환해도 다른 정점들 간에 연결 관계가 없다. 따라서 \(A\)는 애초에 빨간색 간선들로만 구성되게 할 수 있다.

이를 풀이로 바꾸는 방법은, 모든 간선을 순서대로 순회하면서 양 끝점이 둘 다 \(1 \ldots k\)가 아니면 그 간선은 최종 그래프에 항상 남길 수 있다. 사이클은 그래프의 연결성과 밀접하게 관련이 있으므로, 미리 파란색 간선들만 읽으면서 union-find 등으로 양 끝점들을 계속해서 합치자. 그러면 남은 간선은 빨간색들 뿐인데, 양 끝점이 아직도 다른 component에 남은 경우가 아닌 이상 그 간선은 최종 그래프에 포함시킬 수 없고, 다른 component인 경우에는 항상 최종 그래프에 남겨놓을 수 있다. 이를 그대로 구현하면 된다.

Vouchers

문제를 읽다 보니까, 한마디로 \(a\)명이 오면 총 구매량이 \(a^2\)이 되는 어이없는 문제길래 읽으면서도 확신이 안 들었다. 풀이의 핵심은 \(k\)명짜리 단체 손님들 중 관심 있는 손님은 \(\frac{10^6}{k}\)명밖에 없다는 것이다. 그 손님들에게 팔 수 있는 다음 물건의 크기를 관리하고 있으면, 최대 \(\sum_{i=1}^{10^6} \frac{10^6}{i}\)번만 정보가 갱신되므로 시간 안에 작동한다.

Fibonacci Representation

최적해가 \(S_+\)과 \(S_-\)라는 fibonacci number의 index 집합으로 표현된다고 하자. \(S_+\)는 부호가 \(+\)인 항에 대한 index, \(S_-\)는 부호가 \(-\)인 항에 대한 index들의 집합이다. 단 중복이 가능한 집합으로 생각하자. 그러면 내가 어떤 수를 표현했을 때, 문제에서 요구하는 것은 \(\lvert S_+ \rvert + \lvert S_- \rvert\)를 최소화하는 것이다.

관찰 1. \(S_+\)와 \(S_-\)에 같은 수가 들어가 있으면, 그 둘을 동시에 제거하는 게 이득이다.

관찰 2. 어떤 index가 2개 이상 같은 집합에 들어가 있을 수 없다.

증명은 typical한 편이다. \(2F_i = F_{i+1} + F_{i-2}\)이기 때문이다. 중복되는 index를 분리하는 작업을 반복하다 보면 언젠가 중복되는 index가 없어져야 한다. 이 과정이 무한히 반복될 수는 없는데, index의 합은 늘 1씩 감소하는 걸 관찰하자. 만약 \(F_1\)이 두 개 이상 생기면 \(F_3\) 하나로 바꿔주는 정도의 예외 처리는 필요한데, 최적해를 잡은 이후에 이 과정을 반복한다고 생각하면 문제는 없다.

관찰 3. 인접한 index 2개가 동시에 같은 집합에 들어가 있을 수 없다. 그 둘을 합치면 다음 피보나치 수가 나와서 개수가 줄어들기 때문.

관찰 4. 서로 인접하거나, 2만큼 차이나는 index 2개가 다른 집합에 각각 들어가 있을 수 없다. 그 둘을 뺀 다음에 하나만 더 넣어서 같은 값을 만들 수 있기 때문.

관찰 5. \(k\)를 표현하는 최적해가 있을 때, \(F_m \leq k < F_{m+1}\)이라고 하자. 이 때 \(m \in S_+\) or \(m+1 \in S_+\)이다.

\(M = \max S_+\)이라고 하자. \(M \geq m+2\)인 경우 표현 가능한 최소의 피보나치 수는 \(F_{m+2}-F_{m-1}-F_{m-3}-\ldots > F_{m+1}\)이므로 불가능하고, \(M < m\)이면 반대로 가능한 최대의 수가 \(F_m\)보다 작아서 불가능하다. 그러므로 여기까지만 보면 \(m\)이 큰 값부터 작은 값으로 보면서, 각 단계에서 어떤 수를 \(S_+\)가 가져가느냐로 대략 \(O(2^M)\) 정도의 풀이를 만들 수 있고, meet-in-the-middle을 쓰면 \(O(2^\frac{M}{2})\) 정도의 풀이를 만들 수 있다. 그러나 \(M \sim 90\)이므로 풀이가 매우 느리게 돌아간다.

관찰 6. \(F_m \leq k < F_{m+1}\)일 때, \(k-F_m \leq F_{m+1}-k\)이면 \(m \in S_+\)인 최적해가 있고, 반대이면 \(m+1 \in S_+\)인 최적해가 존재한다.

한 쪽 방향만 증명하자. 귀류법을 쓰는데, 관찰 5에 따라서 \(k\)가 \(m+1\ in S_+\)인 최적해를 가진다고 하자. 그 최적해에서 \(m+1\)만 빠진 어떤 집합 \(B\)가 존재하여 \(F_{m+1}-k\)를 표현한다. \(m \in S_+\)인 경우 최적해를 가지지 않는다고 가정했으므로, \(m\)만 빠진 집합 \(A\)가 존재하여 \(k-F_m\)이 표현되지만 \(\lvert A \rvert \geq \lvert B \rvert + 1\)이라고 하자. 여기서 재밌는 점은 \(B\)로 \(\lvert B \rvert + 1\) 크기의 \(k-F_m\)의 표현을 만들 수 있다는 점인데, \(k-F_m = F_{m-1} - (F_{m+1}-k)\)임을 관찰하면 \(B\)의 \(+\), \(-\) 구성을 뒤집은 다음 \(+\) 쪽에 \(F_{m-1}\)을 더 넣어주면 된다는 것을 알 수 있다. 그러므로 \(\lvert A \rvert = \lvert B \rvert + 1\)이고, \(m-1 \in A\)인 최적해를 가정하면 앞선 관찰에 따라 \(A\)에는 \(m-3, m-2, m-1, m, m+1\)이 전부 속하지 않아야 한다고 볼 수 있다. 이러면 \(m+2\) 이상이 속해있었을 때는 관찰 5와 같은 원리로 \(k-F_m\)을 표현할 수가 없었을 것이다.

따라서 \(A\)에 속한 최대의 index는 \(m-4\)이고, 이 때 표현 가능한 수의 최댓값은 \(F_{m-4} + F_{m-6} + \ldots < F_{m-3}\)이므로 \(k \geq F_m + F_{m-3}\)였다면 귀류 가정에 모순이다. 그러므로 \(k-F_m < F_{m-3}\)일 때만 고려하면 되는데, 이러면 \(F_{m+1}-k > F_{m-2}\)이므로 관찰 5와 \(B\)의 정의에 따라서 \(m-2 \in B\)이다. 그런데 이건 다시 앞과 같은 논리로 모순인데, \(B\)의 구성을 뒤집고 \(F_{m-1}\)을 더 넣을 때 \(m-2\)와 \(m-1\)이 어떤 방식으로든 합쳐졌을 것이므로 \(\lvert A \rvert \leq \lvert B \rvert\)가 되기 때문이다. 즉 어떤 상황이어도 모순이므로, 원래 관찰이 증명된다.

정리하자면 어떤 \(k\)가 주어졌을 때 항상 최적해에 포함되는 index를 결정할 수 있게 되므로, \(O(log^2k)\) 정도의 시간에 문제를 풀 수 있다.

Squarks

상황이 재밌는 문제다. 복원되는 수열이 \(a_1 \leq a_2 \leq \ldots \leq a_n\)이라고 하자. \(s_{i,j} = a_i + a_j\)라고 쓰자. 우선 입력으로 주어지는 수 중 최소인 값은 무조건 \(s_{1,2}\)에 대응되어야 한다. 또한 두 번째로 작은 수도 \(s_{1,3}\)에 대응될 수 밖에 없다. 문제의 핵심은 \(s_{2,3}\)이 어디에 대응되느냐와 큰 연관이 있다. 왜냐면 이 정보를 알 수 있을 경우, \(a_1, a_2, a_3\)를 전부 결정할 수 있기 때문이다. 이걸 알게 되면 \(s_{1,2}, s_{1,3}, s_{2,3}\)을 제외한 나머지 수들 중에서 가장 작은 값이 \(s_{1,4}\)가 되는데, 그러면 또 다시 \(s_{1,4}, s_{2,4}, s_{3,4}\)를 알게 되므로 이를 제외한 나머지 수들 중에서 가장 작은 값은 \(s_{1,5}\)가 되어 결국 반복적으로 모든 수를 결정할 수 있다.

이 때 \(s_{2,3}\)이 대응될 수 있는 위치는 최대 \(n-2\)개인데, 극단적으로 \(s_{1,2} \leq s_{1,3} \leq s_{1,4} \leq \ldots \leq s_{1,n} \leq s_{2,3}\)이 성립할 수도 있기 때문이다. 즉 \(s_{1,k} \leq s_{2,3}\)이 성립하는 최대의 \(k\)에 따라서 case work를 일일이 해보면 된다. 이런 방식으로 구해진 \(\{ a_i \}\)가 항상 모든 조건을 만족하는지는 잘 모르겠는데, 정 걸리면 마지막에 검증을 한 번 더 해보도록 하자.

이 문제에서 흥미로운 점 중 하나는, 답이 두 가지 이상의 가능성을 가지는 필요충분조건이 \(n\)이 2의 거듭제곱수 꼴이라는 것이다. \(n\)이 2의 거듭제곱수 꼴이면 \(n\)일 때의 입력으로 \(2n\)일 때의 그러한 입력을 만들어내는 것이 가능하고, 아니라면 대충 \(a_i\)들 간의 관계식을 \(n\)개만큼 찾을 수 있어서 해가 하나라던가 뭐 그런 논리였다. 자세한 증명은 에디토리얼을 참조.

Minimalist Security

connected라고 가정하자. 어떤 정점에 최종적으로 쓰일 수가 \(x\)가 된다고 하면, 그 정점과 연결된 다른 정점에 쓰일 수는 \(a-x\) 꼴로 나타난다. 만약 그래프가 이분 그래프라면 \(x+a\) 꼴로 수가 쓰일 정점과 \(-x+a\) 꼴로 수가 쓰일 정점이 분리되고, 모든 정점에 쓰인 수가 \(0\) 이상 \(z(v)\) 이하가 되도록 \(x\)의 범위를 구해서 최대/최소를 구하면 된다. 그래프가 이분 그래프가 아니라면, 어떤 간선이 존재하여 \((x+a) + (x+b) = b(u, v)\)와 같이 \(x\)의 값이 결정되는 간선이 존재할 것이므로, 음이 아닌 정수해가 존재하는지 판별해주면 된다. 이걸 모든 component에 대해서 시행해서 최대/최소를 합쳐주면 끝.

Warehouse Store

Greedy가 가능하다. 최적해 중에 하나가 \(A\)이고, 다음의 greedy 전략에 따라 만들어진 해가 \(B\)라고 하자. \(b_i\)가 작은 것부터 보면서 (tie breaking은 arbitrarily ok) 그 주문을 이행할 수 있으면 \(B\)에 추가하고, 아니면 건너뛰는 것이다. 그러면 \(B\)에 들어간 순서로 주문을 볼 때, \(b_i\)가 \(A\)에 포함되지 않은 최초의 주문이라고 하자. 즉 \(B\)에는 \(i\)에 할당된 \(b_i\)개만큼의 주문이 존재하는데, 이들이 \(A\)에서 \(\{ i_1, \ldots, i_k \}\)번째 주문들에 일부가 할당되게 되었다고 하자. \(A\)는 최적해이므로 \(\lvert A \rvert \geq \lvert B \rvert\)이고, 따라서 \(k=0\)일 수는 없다. 또한 \(b_{i_j} \leq b_i\)라면 \(i_j\)번째 주문을 포함하는 해가 존재하고, \(B\)를 구성해나갈 때 \(i\)번째 주문을 먼저 마주했을 것이므로 불가능한 상황이다. 그러므로 \(1 \leq j \leq k\)에 대해 \(b_{i_j} > b_i\)이다. \(i_j\) 중 \(i_1\)이 제일 작다고 하자. 그러면 \(A\)에서 \(i_1\)을 \(i\)로 대체한 뒤, 나머지 \(i_2, \ldots, i_k\)에 할당된 주문 중 \(B\)에서의 \(b_i\) 위치에 있던 주문을 전부 \(A\)에서의 \(b_{i_1}\)이 할당받은 주문 위치로 바꾸는 것이 가능하다. 따라서 항상 \(b_i\)를 포함하는 최적해가 있고, 이를 반복하면 \(B\)도 최적해임을 알 수 있다.