足跡-sokuseki-

りかの日進月歩の記録

ABC038 D プレゼント

問題概要

 N 個の箱が与えられる。  i 番目の箱は縦  h_i cm × 横  w_i cmで、縦と横を入れ替えることはできない。
ある箱は縦・横ともにより大きいサイズの箱にのみ入れることができ、ある箱は1つまでしか他の箱を入れることはできない。
このとき、箱を最大で何重の入れ子にできるかを求めよ。

制約

 1 \le N \le 10^5
 1 \le h_i \le 10^5
 1 \le w_i \le 10^5

部分点は  N \le 1000

部分点解法

dp[i][j] :=  縦icm × 横jcm の箱に入る箱の数

としてdpをする。
 h_i  w_i は大きいのでそのままではdp配列の添字にはできない。よって、 N \le 1000 を利用して座圧を行う。

Submission #2825855 - AtCoder Beginner Contest 038

満点解法

「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」という性質から、入れ子にする箱を小さい順にならべると、  h_i  w_i がともに単調増加になっていることがわかる。つまり、縦の長さで昇順になるように並び替えた後、横の長さでも昇順になるように順番に箱を選んでいけばいいことがわかる。

ただし、縦の長さが等しい2つの箱があった場合、どちらか片方の箱しか選択できないことに注意しなければいけない。

普通の昇順ソートを行うと、キーを2つもつ場合は、 h_i = h_j かつ w_i < w_j のとき  i が先に来るように並び替えられてしまうが、これだと縦の長さでソートしたあとに横の長さだけに着目して箱を選ぶと、縦の長さが等しい箱を2つ以上選んでしまう危険性がある。
よって、 h_i = h_j かつ w_i < w_j のとき  j が先に来るように並び替えるようにする。
このように縦の長さでソートした後は、横の長さのみに着目しても「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」を達成することができる。

あとは横の長さを数列の要素とした最大増加部分列(LIS)を求めてあげると、それが答えとなる。


Submission #2856054 - AtCoder Beginner Contest 038

感想

この問題を機にLISを真面目に勉強してスライドをつくったので下手ですが見てください
LIS.pdf - Google ドライブ