ABC212の感想
A,B,C,Dの3問解いて1000点という結果でした。
D問題を通したとき死ぬほど脳汁でた！
ABCの傾向が変わってABCDEFGHの8問構成になってました。
新ABC問題が旧ABC問題と同じ難易度で、新D問題が旧D問題よりちょっと易しい難易度に感じました。
C、D問題が解けたのは3週間の勉強したおかげだと思ってるので満足してます。
N個の要素からなる数列AとM個の要素からなる数列Bがあります。A、Bから要素を1つずつ選んだ時に、これらの差が最小になる値を求めてください。
1つずつ要素を選んで最小を求める時は、sortする！という話を聞いたことがあります。
例えば要素が（1, 10, 5, 8, 7）の数列Xを考えます。
唐突にXから2つの数字を選んで差を最小にしよう！と考えました。
頭から（1と10）（1と5）...と比べていくのは効率が悪いです。
なぜなら、10は5より大きいので（1と10）の差である9は（1と5）の差である4よりも大きくなります。1と残りの要素（10, 5, 8, 7）の差（9, 4, 7, 6）を求めて一番小さいのはなんだ...？と考えなくても、（10, 5, 8, 7）の中で5が一番小さいことを知っていれば、1と5の差を調べるだけで済みます。
また、10との差を小さくする数字を選びたい！と思った時も、10の次に大きい数字が8ということを知っていれば、10と残りの要素（1, 5, 8, 7）の差を調べる必要もなくなります。
7との差を小さくしたい！と思った時にも、小さい順で並べた時に7の隣にくる数字と比べた方が良いとわかるでしょう。
（1, 10, 5, 8, 7）を並べ替えて（1, 5, 7, 8, 10）とします。そして、1と5の差4、5と7の差2、7と8の差1...と差をそれぞれ求めて最小なものを求めてあげれば良いです。
並べ替える方法はvector sortとかで調べましょう！
今回は数列Xから1つずつじゃなくて数列Aと数列Bから1つずつ選ぶ問題なので、ここから一捻りする必要があります。
しかし、先程の方針は有効に思えるので数列Aと数列Bの要素を合わせて数列Cを作りましょう！
そして、数列Cの中から1つずつ選んで先程の手法で差を最小にすることを試みます。
この時にCから1つずつ選んだ数字C1とC2が、数列Aと数列Bから1つずつ選ばれている必要があります。条件を言い換えると「C1が数列Aに含まれている。なおかつC2が数列Bに含まれている。」もしくは「C1が数列Bに含まれている。なおかつC2が数列Aに含まれている。」となります。この赤色の条件を満たしている時はC1とC2の差を求めて、これを満たさない時は差を求めない（もしくは候補から除外する）ことを実装すればOKです。
ある数xが数列Xに含まれているかどうかを調べる方法にlower_boundがあります。
簡単にいうとlower_boundは小さい順に並べられている数列Xに対して利用します。
数列Xのx以上の要素のうち一番左の要素の位置を返します。
例えばX = （1, 2, 3, 3, 4, 5, 7）でxが3だったらXの要素の中で3以上のものは（3, 3, 4, 5, 7）となっています。この中で一番左のものは左にあるほうの3です。なのでX.begin() + 2と値を返します。この時にX[2] = 3となっているのでX[2] = xが成り立ちます。
また、X = （1, 2, 3, 3, 4, 5, 7）でxが6だったらXの要素の中で6以上のものは（7）となっています。この時はX.begin() + 6と値が返ってきます。この時はX[6] = 7となっておりX[6] = xは成り立ちません。
このようにしてlower_boundを用いてX[n] = x（nはlower_boundを使って求めた数）が成り立つかどうかで数字C1, C2が数列A,Bに含まれているか調べることができます。
これはlower_boundの雰囲気を伝えるための解説に過ぎないので、実際に実装する時はlower_boundとかで調べましょう！本当に雰囲気だけなのでプロの人が見たら違う解説をしてると思うかもしれません。
ちなみに私はこの問題のACを通すまでに50分くらいかかりました。
なんか色々操作しようぜ！って問題です。
そして色々操作した後に操作3で最小値を出力しよう！という問題です。
この問題の肝は全体攻撃は記憶することだと思います。
操作2の中で全てのボールに書かれた数字aにxを足してをaからa + xに書き換えるという動作が入ります。この時に全てのボールの値をaからa + xに書き換えていたら時間が足りません。
このような全体攻撃にはボールの値を変えずにsumxといった変数を用意して対処します。操作2が行われた時にsumxにxを足していくことで記録していきます。
操作3で最小値を出力することになります。操作3に対応するためにはsumxの値を考慮しながら全てのボールの値を小さい順に並べておく必要があります。
例えば100と書かれたボールを持っているとします。次に操作2によって数字を50増やすことになりました。この時、ボールの値は100のままですがsumx = 50になります。次に120と書かれたボールを獲得しました。100と120を比べると120の方が大きいですが、sumx = 50を考慮すると実際に書かれる数字は150になるはずなので100の方が大きくなります。120を獲得した際に100を150にすることも考えられますが、持っているボールの数が大きくなった時に全てのボールに50を加えてたら時間が足りなくなります。
そこで、すでに持っているボールにsumx = 50を加えるのではなく獲得したボールの値である120からsumx = 50を引いて70にすることで100との大小関係を維持することを考えます。
操作3で出力する時にはボールの最小の値にsumxを加えることで実際に書かれるはずだった値を出力することができます。
先週に引き続き真面目に解説してしまった。
いつまで解説のモチベが保たれるのだろうか。
来週までに典型90問の星3と星4の半分くらいを解き終えて今日と同じくらいのパフォーマンスを維持できるようにしたいです。
あと今日はAB問題に20分、C問題に50分、D問題に25分くらいかかってC問題が解けてなかった時間は精神が詰みかけていたのでなんとかしたい。
最近計算量を見積もれるようになった、sortはnlognであることを覚えたのは成長。
