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";
}
投稿日時:
最終更新: