コード内容
P149の問題でやりたいことは理解していることを前提とします。
sort(ps , ps + (1<<n2));
int m = 1;
for (int i = 1; i < 1 << n2; i++) {
if(ps[m-1].second < ps[i].seocnd) {
ps[m++] = ps[i];
}
}
何をしているのか
短い文で結論を書くと
・mはまだ単調増加として更新していない配列の一番左の場所、m-1で単調増加の一番大きい値の場所になる
・iは今見ている品物で単調増加の内容に使用するかを調べたい
となっています。
まず前提として、二分探索をするために配列を単調増加にしたいです。これを図にすると右肩上がりの値だけを選ぶと捉えることができます。以下の図は横軸が重さ、縦軸が価値で、点が入力の各品物を表しています。それらの単調増加となっている部分だけ選びます。重さが同じものを選んでも問題ありません、二分探索をするときは価値をINFにして見つけた内容の一個前を見るので重さが被っても一番価値の大きいものが選ばれます。
で、本題はどうやって単調増加の配列を作成するか？という点です。このコードをわかりやすくするために配列を二つ用意します。
①元々の品物の情報が入ってソートされた配列→ps
②単調増加が成り立っている配列→a
②の配列はこの配列で二分探索をするのでそのことを覚えておいてください。何をするかというと①の中から必要な値だけ抜き出すということをします。まず②に①の一番最初の要素を追加します、というのも単調増加の配列を作成していくには、今見ている品物が単調増加になるかを調べるために、現在の単調増加の配列内の最大の値と比較する必要があるからです。単調増加の配列で最大の値はその配列の一番後ろの値になります。では①の一番目は既に入れたので二番目以降でこの品物を追加するかを調べていきます。そうなった場合、追加するかどうかの判定に必要な情報は、
・②の配列の一番大きな値、つまり一番後ろの値
・①の今見ている品物の値
の2つです。
②の配列をaとして図に表すとこうなります。重さは無視しています、仮に重さが同じ品物を二回単調増加の配列に入れていても二分探索したら同じ重さのとき価値が大きい方を選ぶようにするので問題ありません。
コードを書いてみるとこうなります。
vector<pair<int,int>>a;//この配列に単調増加になるように追加する
sort(ps , ps + (1<<n2));//psの配列を全てソートする sort(ps.begin(),ps.end())でも同じ
a.push_back(a[0]);//単調増加の比較のために一番目の品物を追加する
for (int i = 1; i < 1 << n2; i++) {//psの二番目以降の品物を見る
if(a.back().second < ps[i].seocnd) {//今見ている品物が単調増加なら配列に追加
a.push_back = ps[i];
}
}
という感じになります。(実際に動かしていないのでミスがあるかもしれません)
ここまで理解できたでしょうか？実はこの2つの配列を1つの配列にまとめたコードが蟻本のコードになっています。もう一度載せておきます。
sort(ps , ps + (1<<n2));
int m = 1;
for (int i = 1; i < 1 << n2; i++) {
if(ps[m-1].second < ps[i].seocnd) {
ps[m++] = ps[i];
}
}
ここから蟻本のコードについて説明します。
まず、3行目のfor文、つまりiが指しているものはわかると思います、「今見ている品物を単調増加に配列に追加するか？」と表現したときの「今見ている品物」の番号になっています。
となると最後に残る疑問はmです。これを理解するためにはまずpsという配列の意味を理解する必要があります。まず重要なことがあって、先ほど説明した2つの配列を1つにまとめるという変態行為をしています。どうするかというと配列を使い回していて、前から順番に単調増加の値を更新しています、そして二分探索をするときは配列のスタートからmまでを二分探索で使用してそれより後ろは使用しません、それらを前提として説明します。
まず、mというのはpsの配列のまだ単調増加の値を更新していない一番左の場所を指しています。m=1が0ではなく1なのは、前述した通り1番目の品物は単調増加の配列に使用すると決めているからですね、なのでm=0は既に使用しているのでまだ使用していないm=1が初期化になります。では、今配列で空いている、つまり新しく単調増加となる品物を追加するときにpsに更新させる場所はどこになるでしょうか？一番左のps[0]は既に使用しているので、その次の[1]が空いていますね。なのでもし次の単調増加の値が追加されるときは[m]に更新して、今見ているps[i]の品物と単調増加になっているかを調べるときは既に埋まっていて一番右、つまりps[m-1]の値を見ればいいです。ちなみにmが今見ているiを超えることはありません、コードを見れば当然だと思いますが。また、最初のpsの配列が最初から単調増加の場合はiとmが毎回一緒に+1されてpsの配列に変化はありません。
実際の動きを図にするとこうなります。内容が赤のときだけ単調増加の値を見つけたので更新しています。実際のコードを見ればわかりますが、単調増加の値を見つけたときにm++をしているので、いい感じに動いています。
二分探索は(ps.begin(),ps.begin()+m)の範囲を見てあげることで更新していない部分、つまり「単調増加ではないので使用したくない部分」を範囲から除外することができます。以上で蟻本のコードの説明を終わります。
もっと簡単で完結な別の方法がある
https://atcoder.jp/contests/abc032/tasks/abc032_d
類題の問題を見つけてその順位表の上位陣の提出をみるとこのようなものがコードにありました。
vector<pair<int,int>>a;//この配列に入力が入っているとします (重さ,価値)
sort(a.begin(),a.end());
for(int i = 1; i < size(a); i++) {
a[i].second = max(a[i].second, a[i - 1].second);//chmax(a[i].second,a[i-1].second)と同じ
}
やっていることとしては、rep文で[i]の値を今見ていて、[i]と[i-1]のmaxに更新するという感じです。言語化すると「自分より小さい重さで作れる価値は自分の重さでも作れると認識する」みたいな感じになります。
これをペイントで描いてみるとこんな感じになっています。dpみたいですね。なぜこれをしてうまく動くかというと、二つの品物があって、重さ=3で価値=100を作れる品物があったときと、重さ=5で価値=0があったとき、重さ=7で二分探索をすると重さ=3を選びたいのに、重さ=5が邪魔になります。ですが何らかの操作をして重さ=5の品物を消したとすると結局重さ=3のものを選ぶことになる、つまり「自分より重さの低い品物の価値から自由に選ぶ」というような操作をするので、あらかじめいちいち削除や全ての候補を見なくとも、自分の品物の価値さえ見てくれれば、それがその重さ以下の価値でmaxの値になっているようにお膳立てしておく、みたいなイメージです。
wは重さで、棒は価値を表しています、同じ重さが配列に合っても二分探索をするときはINFで調べて、見つけたその一個前を見るので重さが被っても問題ありません。
これなら重さと価値がどちらも単調増加になっているのでlower_boundなどの二分探索が使えそうです。
https://atcoder.jp/contests/abc032/submissions/51937249
ACの提出を載せておきます、問題の解法の関係でデータセットごとに場合分けしてます。pair型のfirst、つまり重さは変更せずに、secondの価値の値だけをchmaxすることに注意してください、あとpair型の配列でlower_boundするときに引数がint型になってて、pair型にするのを忘れるとエラーが起きるのでそれも注意してください(自戒)。
おわりに
蟻本のコードがわからず、解説放送で質問してsnukeさんに教えていただきました、snukeさんに感謝します。頭が上がりません。
https://www.youtube.com/live/EPWq-Fsjk6g?si=eVgqh3TzueWWw4Dy&t=12792