競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。お金の大切さや今後の生き方も併せて伝えられたらと思います。

競技プログラミング~ABC172後半~

おはようございます。しほみんです。

 

おとといに引き続いて、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の倍数ということで、その公差はiの等差数列として見立てられます(数学Bだった気が...)

よって、(i+(Nまでのうち最大のiの倍数))×(Nまでのiの倍数の数)/ 2 となります。

 

まとめると、

i = 1からNまでの、(i+(Nまでのうち最大のiの倍数))×(Nまでのiの倍数の数)/ 2をもとめて、その和を出せばよいです。

 

これでo(N)となり、十分間に合います。

 

 

最後に....

これからもがんばって早くD問題まで解けるようになりたいものです。

 

ではでは。