AtCoder Beginner Contest 038_D_プレゼント
青色の問題.Atcoder版蟻本に掲載されているやつです.何重のマトリョーシカを作れるか.
問題の説明
箱が個あり,それらを入れ子にします.ある箱が,それより縦・横ともに大きいサイズの箱にのみ入れられるとしたとき,最大で何重の入れ子が作成可能か答えよ.
条件
- 縦の長さ
- 横の長さ
考えた事
まず,弱い制約の場合の解法を紹介しよう.の場合,これは分かりやすいDPで実装できる.
={i番目の箱をもっとも外側に入れたときの入れ子の大きさ}]
とすれば,
=max(dp[j]+1)(ただし,j番目の箱はi番目より内側にある)]
として二重ループを書けばよい.計算量はである.
計算量の話から分かるように,この解き方をするとの制約では間に合わない.どうしようか.
話は戻るが,箱Aが箱Bより内側にあるとはどういう状態だろうか.問題の説明にある通り,Aの縦と横の長さがどちらもBより短いという事だ.ではどれがどれかの内側に入るかを一々具に調べあげるべきか.答えはノーだろう.
これがもし1次元,つまり縦の長さの大きい順だけで入れ子を作るならばすごく簡単な問題となるだろう.配列をsortすればいいだけである.*1
今回もそこから発想を膨らませていく.「どちらも」必要なのであるから,まず1つ,絶対に満たされていないといけない条件を潰していく.入れ子に使えそうなものを小さい順に決めてみよう.
まず縦(横でもいい)の長さでsortをかけ,並べていくのが自然であろう.少なくとも縦の長さが逆転する事はあってはならないので,このようにsortをかけて小さい順に並べておく.こうする事で箱をどの順に並べればいいかの指針がつく.
そして横の長さはどうすればいいだろうか.縦に絞って考えれば,sortをした事によって全ての条件を尽くして入れ子が完成している.ここから横の条件を入れて,入れ子にならない箱を取り除いていく.ここでLISの考え方が活きていく.
LISについては蟻本や,
を参照してもらいたい.今回の場合では縦の長さでsortした事によって配列の順番は確定しているのだから,入れ子となる横の長さは増加列となっていればよいと分かるだろう.
つまり,これは縦にsortをかけて配列の順番を固定しておき,そこから横の長さだけ抜き出してLIS問題を解けばいいとなる.
図にするとだいぶ分かりやすいだろう.まず縦で入れ子になるとした場合の順番を決め,次に横でLISを解けばいい.もちろんLISを解くときに箱の順番は入れ替わらないため,縦の条件も崩れない.LISは二分探索で解けるため,計算量はとなり,間に合う.
これで終わりだろうか.残念ながらこれだと上手くいかない時がある.
入力が
5
2 1
3 2
3 7
4 3
5 4
となっているとき,先ほどの方法だと入れ子は3個(2, 1)→(3, 2)→(3, 7)であるが,実際最大となるのは(2,1)→(3, 2)→(4, 3)→(5, 4)の4個である.どうやら縦の長さが同じであるとき,横の長さでLISをしただけでは上手くいかない事が分かる.なぜか.
答えは簡単である.例えば今までと同様に小さい順に入れ子を決めていくとき,
4
2 5
3 3
4 5
6 6
はどの順に入れ子にすればいいか明確であった.第一の優先順位として縦の長さがあるからだ.(2, 5)よりも内側に(3, 3)が来ることがあり得ない事は誰でも分かる.
一方で先程の例だと判断が難しくなる.2つ前の例に加えて(6, 10)があったとしたとき,序列としては(3, 2)が(3, 7)より優先されそうだが,どちらも(6, 10)の内側に来てしまう.入れ子の確定が難しくなる.
これをどう解消しよう.イメージとしては(3, 2)と(3, 7)のどちらも入れられる場合,とりあえず(3, 2)を入れた方が楽に感じるだろう.実はそれが正解なのだ.
つまり,縦の長さが同じであるとき,この問題は区間スケジューリング問題を解く事になる.
選べるもののうち,横の長さが最も小さいものを選んでいけばよいとなる.いわれてみれば当たり前の話で,縦の長さ3で入れられる箱は高々1個しかなく,横の長さでLISを行っているならば,なるだけ小さいものを入れる方が最善であるのは当たり前であろう.縦も同様であったからsortされているのだ.(2, 4)より(4, 4)を優先するケースはほとんどないだろう.
まとめよう.この問題はまず,縦の長さでsortをかけて,全ての縦の長さが異なっているとき,縦の長さを昇順で固定しながら横の長さを用いたLIS問題.縦の長さが同じものが含まれているときは+区間スケジューリング問題となる.理屈の部分の説明はこれで終わりである.
さて,これを実装しよう.ここからもなかなかタフである.縦の長さが同じであるものがないとき,これはLISであるから二分探索を用いて実装する事は上でも説明した.dpテーブルをINFで初期化し,
=長さi+1である,増加部分列の最終要素の最小値]
として,二分探索を用いて更新していけばよい.
vll dp(N + 1, INF);
rep(i, wh.size()) {
*lower_bound(ALL(dp), wh.at(i).second) = wh.at(i).second;
}
問題となるのは区間スケジューリング問題をどのように組み込むかである.ここが大きなポイントである.
最初,自分は縦の長さが同じもののうち,横の長さが最小のものを残せばいいと誤解し,mapを用いて縦と横の長さを管理していた.縦の長さが同じであるとき,CHMINを行い,より小さい方を残す寸法だ.
もちろんこれでは上手くいかない.
6
2 4
3 2
3 6
3 9
4 7
5 12
とあったとき,今の方法では(2, 4)→(4, 7)→(5, 12)の3個となってしまう.また,単純に横の長さでLISしても(3, 2)→(3, 6)→(3, 9)→(5, 12)となり誤った解答である.正解は(2, 4)→(3, 6)→(4, 7)→(5, 12)の順である.
なぜいけないか.区間スケジューリング問題の肝は「選べるもののうち」である.どちらも「選べるもののうち」という条件を無視している.ただいたずらに横の長さが小さいものを使えばいいわけではない.
では「選べるもののうち」はどこで決まるか.結局前の数字で決まってしまう.前に選ばれた箱の数字より大きい横の長さで一番小さいものだ.ではそれを一々探索していっては計算量は恐ろしい事になりそうである.*2
どうしようか.なるべく今までのギミックに組み込んで計算量を落としたい.
ここでLISの動きを見てもらおう.
線めっちゃ歪んでますね.
ともかく,LISを求めるためのdpは上のように動く.ここで大事なのは赤字で書かれた部分.dpの定数の長さを変えずに先端の数字をより小さいものに更新している.これを活かす.
6
2 4
3 2
3 6
3 9
4 7
5 12
と入力されていたとき,(3, 9)→(3, 6)→(3, 2)の順にみれば,横のDPテーブルのINFを消さずに横の長さで「選べるもののうち」,最も小さいものを選べるだろう.
こうする事でDPテーブルが適切なものとなる.「いやいやそれだとDPテーブルが選んだ順に並ばずおかしくならないか？」と気付いた人もいるかもしれない
確かに上だと横の長さでのDPテーブルの遷移は
となり,実際にどの順に入れ子になっているかの復元は不可能となる.しかし,ここで見てもらいたいのは最前の数字である.結局,LISの長さを求める場合において,増加部分列の最先端以外はどうでもいいのである.最先端が正確で,できる限り小さければ,LISの長さは求められる.途中が差し替えられていても構わないのだ.
これが成立する理由はもちろん,縦の長さが同じであるときは横の長さを降順に見ているからである.ここを降順で見る事で,lower_boundによるLISの最先端の要素を出来るだけ小さくするように狙う.
ここまで書けば実装の仕方も想像がつくだろう.縦,横の長さのペアを用意した配列を用意し,縦の長さを昇順に並べたのち,横の長さを降順とすればいい.
縦の長さを昇順に並べる実装にはもちろんsort函数を用いるのだが,これをそのまま使うと(2, 4)→(2, 7)→(2, 11)のように横の長さが短い順,つまり横も昇順となってしまう.
これを解消するテクニックとして,横の長さに-1を予めかけておくというものがある.そうすると,(2, -11)→(2, -7)→(2, -4)となるから,後はもう一度横の長さに-1をかけて,
(2, 11)→(2, 7)→(2, 4)の順にsortする事が出来る.自分はこれが中々思いつかず,30分くらいを費やしました.頭の片隅にでも入れておくといいかと思います.
長くなりましたがここまでお読みいただきありがとうございました.
プログラム
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define ALL(n) begin(n), end(n)
int main() {
ll N;
cin >> N;
vpll wh(N);
rep(i, N) {
cin >> wh.at(i).first >> wh.at(i).second;
wh.at(i).second *= -1;
}
sort(ALL(wh));
rep(i, N) { wh.at(i).second *= -1; }
vll dp(N + 1, INF);
rep(i, wh.size()) {
*lower_bound(ALL(dp), wh.at(i).second) = wh.at(i).second;
}
cout << lower_bound(ALL(dp), INF) - dp.begin() << endl;
}
