https://yukicoder.me/problems/no/918
前提知識
解説
https://yukicoder.me/submissions/393911
Eのお絵かきのようす pic.twitter.com/oeQdMigeea
— satanic@競プロ🔥 (@satanic0258) October 25, 2019
天才だ…わかり易すぎる
どう手をつけていいかわからない問題構築では、ある種の仮定をすることで解けるようになってくる。
今回であれば、最長増加列は前半部分に昇順で作り、後半は降順にする。
あと、数列A,Bは降順の状態で考えることにする。
すると、結果的に作られる大小関係は、satanicさんのような図になる。
賢い。
あとは、この大小関係を満たすように順列を割り当てていくだけだが、これにはトポロジカルソートを使おう。
ソート順で大きい数から割り当てていけば、構築できる。
int H, W, A[404], B[404]; int ans[404][404]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W; rep(y, 0, H) cin >> A[y]; rep(x, 0, W) cin >> B[x]; sort(A, A + H, greater<int>()); sort(B, B + W, greater<int>()); TopologicalSort ts(H * W); rep(y, 0, H) { rep(x, 0, A[y] - 1) ts.add_edge(y * W + x, y * W + x + 1); rep(x, A[y] - 1, W - 1) ts.add_edge(y * W + x + 1, y * W + x); } rep(x, 0, W) { rep(y, 0, B[x] - 1) ts.add_edge(y * W + x, (y + 1) * W + x); rep(y, B[x] - 1, H - 1) ts.add_edge((y + 1) * W + x, y * W + x); } vector<int> ord; bool res = ts.sort(ord); assert(res); int num = 1; fore(i, ord) { int x = i % W; int y = i / W; ans[y][x] = num; num++; } rep(y, 0, H) { rep(x, 0, W) { if(x) printf(" "); printf("%d", ans[y][x]); } printf("\n"); } }