D - Reconstruct Chocolate 解説 by en_translator
Imagine an empty region of height \(H\) and width \(W\), where we fill the pieces.
To get straight to the point, the problem can be solved by repeatedly placing a piece whose height or width coincides with those of the remaining empty region.
Justification
Let us call a set of pieces a **good $(H\times W)$-partition** when they can be obtained by repeatedly performing operations starting from a chocolate bar of height $H$ and width $W$.
- When $H=0$ or $W=0$, we regard an empty set as a good $(H\times W)$-partition.
Then, a good $(H\times W)$-partition $S$ satisfies the following:
- (a). $S$ contains a piece of height $H$ or width $W$.
- (b). For a piece in $S$ of height $H$ and width $t$, the set except for that piece is a good $(H\times (W-t))$-partition.
- (c). For a piece in $S$ of height $t$ and width $W$, the set except for that piece is a good $((H-t)\times W)$-partition.
Proof: (a). It is obvious because of the first piece placed on the desk. (b). When there are $k(\geq 1)$ pieces of height $H$, they are all placed during the first $k$ operations, and rearranging the order they are placed ultimately yields the same piece set. Thus, any height-$H$ piece can be considered placed first, and the remaining pieces form a good $(H\times (W-t))$-partition, thus proving (b). (c). Same as (b).
By (a), (b), and (c), the solution can be justified inductively.
As for implementation, it suffices to repeatedly fetch a piece with the maximum height and a piece with the maximum width, and place whatever fits. By sorting the pieces in descending order of \(h_i\) and \(w_i\) in \(O(N\log N)\) time in the first place, and skipping already-placed pieces, the total placement process can be completed in \(O(N)\) time.
Sample code (C++)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int H, W, N;
cin >> H >> W >> N;
vector<int> h(N), w(N);
for (int i = 0; i < N; i++) cin >> h[i] >> w[i];
// ord_h, ord_w: rearrangement of pieces
// h[ord_h[i]] >= h[ord_h[i + 1]]
// w[ord_w[i]] >= w[ord_w[i + 1]]
vector<int> ord_h(N), ord_w(N);
iota(ord_h.begin(), ord_h.end(), 0);
sort(ord_h.begin(), ord_h.end(), [&](int x, int y) { return h[x] > h[y]; });
iota(ord_w.begin(), ord_w.end(), 0);
sort(ord_w.begin(), ord_w.end(), [&](int x, int y) { return w[x] > w[y]; });
vector<int> ans_x(N, -1), ans_y(N, -1);
vector<bool> used(N, false);
auto ith = ord_h.begin();
auto itw = ord_w.begin();
for (int rem = N; rem > 0; rem--) {
// Skip if it is already used
while (used[*ith]) ith++;
while (used[*itw]) itw++;
// Piece i has height H or width W
int i = h[*ith] == H ? *ith : *itw;
// Place it to bottom-right
ans_x[i] = H - h[i] + 1;
ans_y[i] = W - w[i] + 1;
used[i] = true;
if (h[i] == H) {
W -= w[i];
} else {
H -= h[i];
}
}
for (int i = 0; i < N; i++) cout << ans_x[i] << " " << ans_y[i] << "\n";
}
投稿日時:
最終更新: