脳log[20200628] AtCoder Beginner Contest 172／D 問題 Sum of Divisors

最終更新: 2020-07-05T23:55+0900

♪ [AtCoder] AtCoder Beginner Contest 172／D 問題 Sum of Divisors

コンテスト全体については順当に、冴えない結果であった。あまり書くことがないので１つだけ。

 「D 問題への Ruby による提出(実行時間昇順)」

他が概ね 1000 ms ほどかけているところ、１つだけおよそ半分の 515 ms で済ませている>提出 #14757268。

ループでは他と同じ式を使ってるんだけど、半分に割って足しているところが鮮やか。足し算の背後にある論理がわかりません。

N/2+1 から N までの数は掛ける２をするだけで N を超えてしまうので、その数自身しか数える必要がない、というあたりかな。ループの中の計算が必要ない。

こんな手の込んだことをしていながら提出時刻も早くて、Ruby の中では５番目なんだよね。一方の自分は、C 問題で脳死の愚直手続きスクリプトを書いていた>提出 #14743690。脳死のまま清書>提出 #14788308。ステートメントを減らそうとしてやりすぎた>提出 #14788890

 脳死といえば……

D 問題にも最初は脳死状態で挑んでいた。こういうスクリプト。

1. N 要素の配列を 0 で初期化する。
2. 1..N のそれぞれに対してそれ自身と倍数に対応する配列の要素を +1 する。
3. 最後にその配列を使って K×f(K) (K=1..N) を計算して合計する。

でもサンプル３が親切にも N の上限値で、このやり方では時間がかかりすぎることに気付かせてくれた。さもなくばずぼらと拙速の代償として TLE を１個拝領していたことだろう。

 「[AtCoder 参加感想] 2020/06/27:ABC 172 | maspyのHP」

D 問題。問題と格子点の関連がさっぱりわからなかったのだけど、ループでシミュレートしてるΣ計算に N の一般式を与えようとしたときに、Σの中に整数除算があるから、反比例のグラフと軸のあいだの格子点の数に興味があるの？ その前に、k*N/k*N/k を約分したり分解したりはできない？

 「ABC172D - 西尾泰和のScrapbox」

ところで、この縦に足す方法では、半分から先はどうせ1つしかないのにループを回して一つずつ足してしまう。ここを斜めに足せばループは半分で済む。しかしどうせ斜めに足すなら… 左上までしっかり斜めに足す。そうするとループの回数はルートNのオーダーになる。

画像が見えない(scrapbox も CSS を切らないと読めない)。まだ「斜めに足す」がわからない。√N のオーダーになるとは他所でも読んだが、わからなかった。

k*(N/k)*(N/k) の、N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる(それとΣの区間も変化する)とか、そういう話なんだろうか。いや、どう書いてあるかはざっと読んだんだけど、読んだだけで解れば世話がないわけで……(あとでスクリプトにして確かめよう)。

 スクリプトにして提出したら 997 ms だったものが 68 ms になった。(比較のため Python だと 32 ms)

しかし明らかにもっとすっきり書く方法がありそうなんだよな、っていうかそれはすでに Python スクリプトとして示されてるんだけど、理解できないのです。

自分がやったのはすでに書いた通り、「N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる」ということを利用して、k=1..N のループについて前から計算すると同時にループの反対側にある N/k==k (※)となるケースを計算して両端からループを進めようということ。繰り返し回数は 1,2,3,...,N/3,N/2,N の半分になるはずなんだけど、中間地点がどこにあるのか、全長がいくつになるのか、わかりません。

でもまあ、√N のオーダーになってるみたいだから、N=a*a だとして、1,2,...,a-1,a(=N/a),N/(a-1),...,N/2,N なんでしょう。

 整数への切り下げがなければ

m=N/k; n=N/(k-1) なのを利用して 68 ms のスクリプトのループの中の式を s+=N*(N+1)/2; s+=k*m*(m+1) と整理できそうなんだけど、そうするとこれまたどこかで見たような式(と定数)でさらに整理できそうな雰囲気があるんだけど、m と n の関係は通分したり約分したりできる関係ではたぶんないんだよね(答えが合わないから)。

 「AtCoder Beginner Contest 172 D - Sum of Divisors - Crieit」

図がわかりやすい。オーダーをちょっとずつ改善していく構成が付いて行きやすい。そして最後に見逃せないこれ>「なお、O(N^1/3)の方法もあるらしいです。」

格子点のやり方がこのオーダーらしい。さっぱり想像がつかない

じゃあね、せっかくリンクを張って紹介してくれた先(「格子点の数え上げの高速化 - memo」)を読みましょうよ、って話なんだけど、高速化云々より前に格子点がどのように関わってくるのかがまず知りたいよね。

 「格子点の数え上げの高速化 - memo」

まずここから(わかんない)。

1 から n までの約数の個数の総和（つまり、y=n/x の第一象限内の格子点の個数）は $2\cdot \left({\sum }_{i=1}^{\lfloor \sqrt{n}\rfloor }⌊\frac{n}{i}⌋\right)-\lfloor \sqrt{n}{\rfloor }^2$ などを用いて計算することが多く

• y=n/x と y=x の交点が (√n,√n)
• y=n/x は y=x を軸にして対称
• x=1..√n の範囲で y=n/x と y=x のあいだにある格子点を数えて２倍する？ (たぶん y=x 上の格子点を一度だけ数えるよう気を配るのが面倒くさい)
• x=1..√n の範囲で y=n/x と x 軸のあいだにある格子点を数えて２倍して、重複して数えた (1,1)から(√n,√n)を対角線とする正方形領域の格子点を引く

 「考え方」

• 曲線上にある格子点が列挙できたら
• 隣り合う格子点間を結んで斜辺とする各台形内の格子点を計算で求めるだけでいい
• 斜辺上にある格子点にだけ注意してね(「傾きが既約分数の場合」)
• 最初のステップの列挙には Stern–Brocot tree が使えるよ

 「求め方」

• わかりません。ニュートン法みたいな試行を繰り返すの？ むしろユークリッドの互除法？

 ループをまたいで式を整理した。

• Ruby 提出 #14878990 (137 Byte / 66 ms / 14296 KB)
  • 前の版 提出 #14847505 (157 Byte / 68 ms / 14320 KB)
• Python 提出 #14879054 (145 Byte / 29 ms / 9096 KB)
  • 前の版 提出 #14849513 (168 Byte / 32 ms / 9108 KB)

それというのも Python の方には２桁msの提出が１ページ以上もあって、オーダーは変わらないしブレもあるだろうとはいえ、28 ms と 32 ms のスクリプトのあいだには明らかに式の複雑さに差がある。

 「Python によるすべての提出(実行時間昇順)」

※ 実行時間昇順で並べたときだけ自分の 32 ms の提出がリストされない。降順だったり提出時刻だったりでソートすれば現れる。消えているときは代わりに他の人の 32 ms の提出が２回リストされている。

32 ms の１つは自分のだが、28 ms は例えばこれ>提出 #14788253。平均タイムからして明らかに速い。

未だ及ばずながらだいぶ迫ったのではないか。

 これで最後。

最後に÷４するのにループの中で無駄に×４してるのが気になったので。

• Ruby 提出 #14942722 (141 Byte / 65 ms / 14304 KB)
  • 前の版 提出 #14878990 (137 Byte / 66 ms / 14296 KB)
    • 前の前の版 提出 #14847505 (157 Byte / 68 ms / 14320 KB)
• Python 提出 #14944808 (151 Byte / 26 ms / 9148 KB)
  • 前の版 提出 #14879054 (145 Byte / 29 ms / 9096 KB)
    • 前の前の版 提出 #14849513 (168 Byte / 32 ms / 9108 KB)

これを最適化というのではないか。この問題でしか意味のないループになった。少なくとも自分は式の意味を、途中からは理解していない。

実は最終版の while ループの中身は一番最初の 997 ms の提出とそっくりになっている。戻ってきた。

 Python のこの提出 #14841471

Ruby で書くとこんな感じ。

N = gets.to_i
p (1..Math.sqrt(N)).sum{|k|
	n = N/k
	k*n*(n+1)-k*k*k
}

違いを見比べると $-k^3$ がループの中にあるか外にあるかの差なんだろう。Wikipedia による と ${\sum }_{i=1}^n{k}^3={\left(\frac{n(n+1)}{2}\right)}^2$ らしい。

k*[n*(n+1)-k*k] からは、何か、意味が読み取れそうな気がするね。数学力があれば見えるんだろうか。数学力があれば意味を保ったまま易々とたどり着けるんだろうか。

 結局これでいい。

ループ後のつじつま合わせの正体が $-\sum k^3$ だとわかったので……

N = gets.to_i
s,k,n = 0,1,N
while k<=n
	s += k*n*(n+1)
	k += 1
	n = N/k
end
s -= (k*(k-1)/2)**2
p s