おはようございます。しほみんです。
前回の続きで今回はD問題とE問題を振り返ります。
大体1週間遅れになって話していますが、微妙に理由があります。
・自分できちんと咀嚼して理解する時間が必要である。
・1週間おいても解法が思いつくかどうか確認するため。
結局仕事があるとなかなか競プロにも力を入れられないのでこんな形をとってます。まあ、早く解けるようになるとかは置いておいて引き続き頑張ってはいこうかなあと思います。
さて問題に移ります。
D問題
長さNの数列Aがあります。
次の性質を満たすi(1<=i<=N)の数をこたえてください。
・i ≠ j である任意のjにおいてAiはAjで割り切れない。
ちなみに任意という表現ですが、すべてのという意味です。なので、1つでもその数以外を考えたとき割り切れれば満たしません。
まあ普通に考えると、
全部の通りを見て約数かどうか判定する方法があります。
ただ、すべての組み合わせをやったらo(Nの2乗)で間に合いません。
確実に時間オーバーです。これをどうするか考えないとなりませんが、結局その考えにとらわれて解けませんでした。
もうちょっと考察を進めてみます。
AiよりAjが大きいときを考えてみましょう。このとき、AiはAjで割り切れないのは確かです。よって、Ai >Ajのときのみ考えればよいとわかります。
そこからソートして小さい順に並べれば、その数より小さいものを見れば何となくできそうです。しかし、これもo(Nの2乗)なので意味ないのです。
ここで、C問題がヒントになります。C問題では最初にダメな数をあらかじめ保存しておいてそのあと条件を満たす最小の数を探していました。
これと同じことをしてしまえばよいのです。つまり、大きい数から満たさない数を探すのではなく、小さい方の数から考えます。問題の条件的に小さい数の倍数となる大きい数は絶対に満たしません。（なぜなら大きい数から見たらその小さい数で割り切れてしまうから）。ということで小さい数から考えていくと解けることが分かります。
つまりこういうことです。
1.ソートして小さい順に並べます。
2.左からその数の倍数となるモノをすべて別の配列で記録しておく。
3.読んで、不適合であれば、その数は省いていっていく、そうでないならその倍数となるモノを記録していく。
4.このうち残った数だけを足して答えを出す。
ソートをすることで、選んだ数より右側の数字は等しいか大きく、選んだ数より右側は選んだものの約数になりえるからです。
つまり、
基本的な発想は
1. 左から見ていったときに、何かしらの別情報に変換する
2. 該当するものを見たとき、前の保持情報から条件を満たすか確認。満たすときは、情報を追加する。満たさないときは無視する。
3. 確認し終わったら結果を出す。
です。
約数倍数うんぬんよりどっちかというと計算量を減らすために、プログラム的にどう情報を残しておくかって感じの問題だったなあって感じです。
1の意識を高めると、今回みたいに該当範囲の配列保存や累積和、Union-find、木構造とかを意識して組めるようになります。
2のときにうまく出せればその情報保持は正しかったってことになります。
そういうところを確認するいい問題でしたね。
E問題
幼稚園が200000個あります。園児がN人います。それぞれのレートはAiです。
最初園児は、Biの幼稚園にいます。それぞれの幼稚園で園児がいるとき、一番強いレートの幼稚園児のレートをその幼稚園のレートとします。
このとき、Q回の転園を行います。1回の転園でCiの園児がDiの幼稚園に転園します。
このとき、1回の転園することに、幼稚園のレートで最小のものを求めなさい。
最強の園児問題ですね....D躓いている時点でまあ解けなくてしょうがないのですが、覚えればよいので振り返りました。
さっきの基本的な考えに基づいて考えてみましょう。
まずは、与えられたデータを何かしらの構造に変えるってところを意識します。
何となく問題を見ていると、転園ごとに毎回情報を更新しないとならず、
転園するごとに、転園する園児の強さを変えて、転園前後の園の強さ、全体の園の強さの最小を更新しないとならないってことに気が付きます。
これらをo(N)のオーダーでやってしまうと当然間に合わないので、
o(logN)かo(1)でこれら処理ができないとならない構造が必要とわかります。
つまり、何かしらのデータ構造があって、それの入力、削除、最大値、最小値取り出しをo(logN)でしないとならないです。
ここまで考えると、できる構造は平衡二分探索木に限られるってことに気がつきます。
二分木で数の大小をうまく管理するデータ構造です（詳しくは自分も理解できてないです...が使えるようにはした）。
C#では、SortedSetが平衡二分探索木ということで用意されています。それを使いましょう。
（最初の準備）
・幼稚園ごとにSortedSetを用意する。(配列でやると簡単）
・幼稚園ごとに最強幼稚園児を入れておくSortedSetを用意する。
・園児の上記条件から、幼稚園ごとの情報を更新
・最強の幼稚園児たちを集めておく。
（クエリごとの対応）
・転園する前の幼稚園から選ばれた最強の園児を削除。
・転園する前の幼稚園から選ばれた園児を削除。
・転園後の幼稚園から選ばれた最強の園児を削除。
・転園後の幼稚園に選ばれた園児を入れる。
・転園する前の幼稚園から最強の園児を選びなおす。
・転園後の幼稚園から最強の園児を選びなおす。
・最強の園児たちから最弱を選ぶ。
これを素直に実装するだけです（順番間違えると破綻します。
ただし、SortedSetは、削除するとき、該当するすべての数を消します。例えば、レート34の園児が2人いたときにレート34の園児を削除するとすると両方消えます。
よって、今回は、long型をつかって、上位32ビットはレート、下位32ビットは園児番号を記録して区別します。
最後に....
このDとEは今後是非解けるようになりたい問題だなあと思います。面白いですし、こういうのアルゴリズムの勉強になります。
ではでは。
