おはようございます。しほみんです。
おとといに引き続いて、ABC172の話をします。今日は、CとD問題です。
C問題はプログラミングっぽい問題ですが、数学的発想は確かに必要です。
D問題は発想の転換と数列の知識が必要です。
数学的な発想が必要なD問題は苦手な人は苦手そうです。
C問題
本を積んだタワーが二つあります。1つ目はM冊、2つ目はN冊積んであります。
それぞれの本は読むのにAi(i = 1~M),Bi(i = 1~N)分かかります。
本は、上からしか取り出せず、読むとき、どちらかの積んだタワーから選びます。
このとき、K分で読める本の最大数を求めなさい。
悩んだ問題です...とりあえず、読む冊数の組み合わせはNM通りあり、そのうちK以下の時間で読めるものの最大を求めるとかやってるとo(MN)で間に合わないぐらいは検討をつけたいところです。
ということで何かしらの工夫は必須です。
最初に思い付いたのは貪欲法です。
方法としては単純で、とりあえず、2つのタワーのうち読む時間が少ない方を取り出していく方法です。ただ、これだと条件を満たさない場合があります。
例えば、M=N=5冊で
M:10,250,10,10,10
N:10,20,100,150,180
とします。
このとき、300分としたら、Mが5冊、Nが1冊で、6冊が最大です。
しかし、このとき、250がボトルネックで押さえられるので、小さいほうだけを見てしまうと、Mが1冊、Nが4冊で、5冊にしかなりません。
ということで貪欲法では解けないです。
そうするとすっかり手詰まりになったのですが....もうちょっと問題を整理しましょう。
2つのタワーがあり、2つの状況を考えるのってそもそも難しく、解きにくいです。
ということで、1つのタワーの読み冊数を固定したとき、もう1つのタワーは何冊読めるか見てみましょう。
これは2変数関数の求め方において、1つを固定して考える考え方と同じです。（数学的によく出る手法なので覚えておいて損はないです）
つまり、M冊のタワーでは、0-M冊本を読むと決めて、
そのとき、N冊のタワーでは、何冊読めるか求め、それぞれの場合で読める冊数を決めればよいのです。
例えば、M冊タワーで、x冊読むとすると、x冊まで読んだ時間をtとして、N冊のタワーはk-t分だけ読めます。
あとはこの時間で最大何冊読めるか探します。ただ、普通に頭から計算して数えていると最悪o(N)となり、それをM回検討したら間に合いません。
そこで一回の計算をo(logN)まで落とす必要があります。ここで使えるのは二分探索です。
N冊のタワーでy冊まで読むのにかかる時間に変換すると、数字が小さい順に並べれば使えるのでこれでよくなります。(累積和の考え方)
まとめると、
1. M冊のタワーではi(i = 0 - M)冊読むと決める。
2. かかる時間を引いてN冊のタワーに当てられる時間を決める。
3. N冊のタワーはあらかじめi(i = 0-N)冊読んだときにかかる時間にしておく。これを二分探索して、読める冊数を求める。
4. 読める冊数を数えて、最大なら更新。1に戻る。
となります。まず、変数固定から考えないとならず、さらに累積和+二分探索を思いつかないとならず、かなり難しい部類でした。
D問題
Nの約数の数をf(N)とします。
1からNまでのi×f(i)の和を求めなさい。（問題文はΣ記号ですが意味合いは同じです）
約数の数はo(√N)で求められます。
（細かく言うと時間がかかりますが、基本、約数なら〇×〇と2つの積で表せることを利用していけばよいです。このとき、最大でも〇に入るのは√Nのため、そこまでの数を見ればよいことになります）
よって、1からNだとo(N√N)の時間で求められます。
ただ、今回制約がNの10の7乗となっていて、o(N√N)だと、10の10乗となり間に合いません。
なので、o(N)の計算量に落とさざるを得ないです。
となると、約数の個数なんて出している余裕はないです。この和の意味をうまく置き換える必要があります。
これはもうテクニックに近いのかと思いますが、
「xはyの約数ということは、yはxの倍数」という考え方で終わります。(ABC170でも最近ありました）
例えば、
1から6の約数を考えます
1: 1
2: 1, 2
3: 1 , 3
4: 1, 2 , 4
5: 1, , 5
6: 1, 2, 3 , 6
で、横で読む（問題文通り）と、1×1+2×2+3×2+4×3+5×2+6×4= 57です。
ただ、もう一つ読めます。実は縦に読むと、1の倍数である、1から6、2の倍数である、2と4と6みたいになります。
そのとき、(1+2+3+4+5+6)+(2+4+6)+(3+6)+(4)+(5)+(6)=57となります。上の書き方だと、ｉの約数の数だけiが出ていることに注目です。
ここから、iの倍数のとき、その数を足し合わせるって手法をとればよいってわかります。
また、iの倍数ということで、その公差はiの等差数列として見立てられます（数学Bだった気が...）
よって、（i+(Nまでのうち最大のiの倍数））×（Nまでのiの倍数の数）/ 2 となります。
まとめると、
i = 1からNまでの、（i+(Nまでのうち最大のiの倍数））×（Nまでのiの倍数の数）/ 2をもとめて、その和を出せばよいです。
これでo(N)となり、十分間に合います。
最後に....
これからもがんばって早くD問題まで解けるようになりたいものです。
ではでは。
