Stacking Boxes 解けたー

やっと 103 Stacking Boxes が解けた! 解法はざっと次の通り。

多次元の直方体をマトリョーシカみたいにできるだけ多く重ねるという話です。次元の順番はどうでもいいので、それぞれの箱についてソート。次に全ての箱について最初の次元でソートして順序付けしておく（元の順番を保存しておくこと）。あとは Longest Increasing Subsequence をかければ所望の最長ネスト部分列が得られる。 N log N のアルゴリズムはよく分からなかったので N² の方でやりました。

重ね方にいくつか可能性がある場合は、どれでもいいのでそのうちの一つを出せばよい。

長かった…。大学の先輩から LIS の説明を聞いてやっと書けました。