AOJ0157 Russian Dolls / ABC038 プレゼント
全く同じ問題をACしたことがあるのにさっぱり解けないのはまずいでしょ。
ということで、反省の意味も込めて問題の解説記事を書きます。
問題
Russian Dolls | Aizu Online Judge
D: プレゼント - AtCoder Beginner Contest 038 | AtCoder
問題概要
制約以外はほとんど同じ問題なので、制約がよりゆるいAOJの問題の説明をします。
これは、AOJでACする解法を高速化することでABC038でACすることができ、
この記事では高速化の部分については深く触れないためです。
マトリョーシカが2つある。
それぞれ人形がn, m個入れ子になっている。
それぞれの人形のパラメータ（高さ、半径）が与えられるので
最大でいくつの人形からなる一つのマトリョーシカを作れるだろうか？
入力
n : 1つ目のマトリョーシカを構成する人形の数
m : 2つ目のマトリョーシカを構成する人形の数
h_i, r_i : i番目のマトリョーシカのパラメータ（高さ、半径）
考察
2つのマトリョーシカを別々に考える必要はなく、
(n+m)個の人形を使って1つのマトリョーシカを構成することを考えればよい。
この時点で、制約以外が ABC038 プレゼント と一致します。
上の考えに基づいて問題を言い換えると...
パラメータ（h, r）を持つ n+m 個の要素の中から
全ての i, j について h_i < h_j かつ r_i < r_j （ただし i < j ）
を満たすような最長の要素の並びの長さ求める。
となります。
固く書くと逆にわかりづらいので、柔らかく書くと
人形の高さと半径の両方が左に行くほど小さくて、右に行くほど大きくなるように
並べた時、一番長くてどれくらいかな〜？って感じです。
これで伝わればいいなって思います。
解説
解説はAtCoder社のスライドがあり、それが完璧なので正直そっちでいいんですが、
スライドだけだとよくわからないという人もいると思うので（私です）、
説明下手マンなりにいい感じになるよう解説を頑張ります。
だんだん書くのがめんどくさくなってきました。
（AtCoderの解説が悪いわけではありません、最高です。悪いのは私の頭です。）
表現が具体的でなかったり、実装と一致しない部分がありますが、
実装はひとまず置いといてイメージしてみてください。
まず、人形（上で言う要素、マトリョーシカ人形）の高さが重複しない
場合を考えます。
つまり、背の高さが同じ人形がない時のことを考えます。
人形（上で言う要素、マトリョーシカ人形）を背の順に並べます。
すると、左から小さい順に人形が並びますが、幅はまちまちです。
この人形をえいってやるのですが、えいってするために配列を用意します。
配列 dp[幅] = 個数
この配列に、人形を先頭から掴んで、
配列の添字が人形の幅の値と等しい場所に入れていくのですが、
この時、今入れる人形の幅よりも小さい幅の人形が既にどれくらい入っているかを
考慮します。
今掴んだ人形より先に配列に入れられた、既に配列に入っている人形は
必ず今掴んでいる人形より背が低いです。
さらに、今から入れる場所よりも添字が小さい場所に入っている人形は
必ず今掴んでいる人形より痩せています。（幅が小さいです。）
幅と配列の添字が対応しているので、
（添字が小さい）＝（幅が小さい）
ということが必ず言えるので、
背の順に並べて、それを先頭から幅順にすると、
その時点でその人形より小さい人形（マトリョーシカできる人形）が分かる！
ということが分かります。
ここで、配列に代入する値ですが、
ある人形 A を手に取った時、それより小さい人形が全てわかるので、
何個マトリョーシカできるか分かる気がしてきませんか？
できるんです。
具体的には、
人形 A より小さい人形 のなかで 一番マトリョーシカできる人形 + 1
が dp[Aの幅] の中に入る値です。
一番マトリョーシカできる人形を、人形 A でマトリョーシカするので
今までで一番多い + 1 になるのは分かるかと思います。
実際に値をいじってみましょう。
例
人形：
A ( 1, 2 )
B ( 3, 4 )
C ( 4, 8 )
D ( 2, 6 )
配列：
int dp[10] = {0} // 全て0で初期化されている
①まずソートする
A ( 1, 2 ) A ( 1, 2 )
B ( 3, 4 ) D ( 2, 6 )
C ( 4, 8 ) → B ( 3, 4 )
D ( 2, 6 ) C ( 4, 8 )
②１番目の人形（ A ）を手に取る
③配列に入れる
A ( 1, 2 )
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|０|０|０|０|０|０|
dp[2] = 1; となった。2より幅が小さい人形がないので、
人形1個目ということで、値は1。
④２番目の人形（ D ）を手に取る
⑤配列に入れる
D ( 2, 6 )
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|０|０|２|０|０|０|
dp[6] = 2; となった。6より幅が小さい人形が1つ（Aのみ）あるので、
人形Dの中に人形Aを入れることができる、という意味で配列の値は2になる。
⑥３番目の人形（ B ）を手に取る
⑦配列に入れる
B ( 3, 4 )
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|２|０|２|０|０|０|
dp[4] = 2; となった。4より幅が小さい人形が1つ（Aのみ）あるので、
人形Bの中に人形Aを入れることができる、という意味で配列の値は2になる。
この時、人形Dが既に配列に入っていて、人形Dのほうが幅が大きいので
人形Dの中に人形Bを入れられると思うかもしれないが、
今人形は背の順に処理されているため、配列に既に入っている人形は
今手に持っている人形を中に入れることができないことに注意。
⑧４番目の人形（ C ）を手に取る
⑨配列に入れる
C ( 4, 8 )
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|２|０|２|０|３|０|
dp[8] = 3; となった。8より幅が小さい人形が2つ
（AとBもしくはAとD, 配列で見ると dp[4] か dp[6] それぞれ A in D, A in B の意味）
あるので、
人形Aが中に入った 人形Bか人形D を人形Cの中に入れることができる、という意味で配列の値は3になる。ここで、何個マトリョーシカできるか、が知りたいので、
どれがマトリョーシカするか（すなわち人形Bか人形Dか）は気にしなくて良い。
どっちが中に入っていようと、一番外側は人形Cにるので、
これから先により大きい人形が来ても
気にしなければならないのは、一番外側の大きさのみだから、である。
（一番外側のマトリョーシカのサイズ次第で入れられるかが決まるため）
操作は以上だが、出来上がった配列を見てみると何がメモされているか分かる。
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|２|０|２|０|３|０|
dp[2] = 1; これは、一番外側が幅２の、中に何も入っていない人形がある
dp[4] = 2; これは、一番外側が幅４の、中に人形が1つ入った人形がある
dp[6] = 2; これは、一番外側が幅６の、中に人形が1つ入った人形がある
dp[8] = 3; これは、一番外側が幅８の、中に人形が2つ入った人形がある
それぞれ上記を示している。
これより先に入ってくる人形がもしあれば、それは
高さがいままでのどの人形よりも大きくなければならない。
ここまでが高さに重複がない場合。
高さに重複がある場合は、少し工夫が必要である。
高さが重複する場合
今までは全ての人形の高さが違ったため、
人形を背の順にならべて小さいものから操作することで、
既に配列に入っている人形が、必ず全て現在操作している人形より小さい、
という状況を作ることができていました。
しかし、高さが同じ人形が存在すると、
高さが同じ2つの人形をマトリョーシカすることはできないので、
既に配列に入っている人形の中にも、マトリョーシカできない
人形が存在してしまうかもしれない状況ができてしまいます。
上記のことが、一様に人形を操作できなくなる原因なので、それを取り除きましょう。
これはちょっとした工夫で可能です。
人形を背の小さい順にならべ、高さが同じ人形は幅が大きい順に並べます。
こうすることで上手く処理ができるようになります。
これはなぜかというと、
ある人形を操作する時、その人形の幅を見て配列に人形を入れます。
この時、その人形の幅よりも幅が小さい人形についてのみ、
最大で何個マトリョーシカできるかを調べます。
なので、幅が大きい物から処理をすれば、必ず配列のより添字がより小さい方には
高さが同じ人形が存在しなくなるのです。
実際に操作をしてみると、今配列が以下のようになっているとします。
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|２|０|２|０|３|０|
ここに、A (10, 9 ), B (10, 6 ), C (10, 2 ) の人形を入れていくことを考えます。
人形の操作のルールに基づき、今既に配列に入れられた人形は、みな
高さが10より小さいです。
①まずA (10, 9 ) を入れます。
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|２|０|２|０|３|０|
↑ ココに入る
人形の幅は9なので、 dp[9] が入れる箇所です。
操作のルールどおり、dp[0] ~ dp[8] の中で最大値を探すと、dp[8] = 3 が
最大である事が分かります。よってdp[9] = 4 となります。
②次にB (10, 6 ) を入れます。
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|２|０|２|０|３|４|
↑ ココに入る
人形の幅は6なので、 dp[6] が入れる箇所です。
操作のルールどおり、dp[0] ~ dp[5] の中で最大値を探すと、dp[4] = 2 が
最大である事が分かります。よってdp[6] = 3 となります。
この時、高さが同じだった人形Aは、Bより幅が大きいので、
最大値を探す範囲 ( dp[0] ~ dp[5] ) に存在しない ( dp[9]にいる ) 事が言えます。
なので、今までどおり高さを気にせず操作することができます。
ちなみに、この時 dp[6] には既に２が入っていますが、
これから操作される人形は必ずいま配列の中にいるどの人形よりも背が高いので、
背の高さの条件を必ず満たすので幅についてだけ考慮すれば良く、
どのような人形を上にかぶせても3マトリョーシカの人形にかぶせたほうが
必ずマトリョーシカ数が大きくなります。よって配列の中にはより大きい値を
常に採用していけば良いのです。
③同様の操作で C ( 10, 2 ) を入れます。
添字 |０|１|２|３|４|５|６|７|８|９|
dp |０|０|１|０|２|０|３|０|３|４|
↑ ココに入る
同様にするだけです。 dp[2] = 1となり値は変わりません。
解法のまとめ
①背が小さい順、背が同じなら幅が大きい順に人形を並べる。
②先頭から人形を手に取り、配列の添字がその人形の幅の値と一致する部分に人形を入れることを考える。
③その添字より小さい添字の中から、配列の中の値の最大値を調べる。
④調べた値 + 1 が配列のその人形が入る部分の値となる。
⑤人形がなくなるまで②に戻って繰り返し操作をする。
⑥人形がなくなったら、配列全体の最大値が答えとなる。
以下ソースコード
