他カテゴリ

知ってたけど自分やっぱ天才かもしらん。

ぺにょお's icon'
  • ぺにょお
  • 2020/06/29 08:02
Content image

 

 

 

Atcoder の記事だとバレないサムネにしてやったわ!

 

そこのあなた、残念!開いてしまったね?

 

待った!閉じるんじゃないよ!諦めて読んでいきなさい。

 

 

 

 

土曜は麻雀に興じていたので Atcoder をサボってしまった。

 

しかし!

 

その後、問題を見て勉強をした。

 

Atcoder にストイックな男と呼んでくれ!

 

 

問題:

正の整数 x について、x の約数の個数を f(x) とする。

正の整数Nが与えられたとき、

Content image

を求めよ。

 

つまり、

 

  1×(1の約数の個数)+2×(2の約数の個数)+3×(3の約数の個数)+・・・・
                       ・・・・+N×(Nの約数の個数)

 

を求めろ、ということだ。

 

 

答えはこうらしい。

n = int(input())
s = 0
for i in range(1, n+1):
   q = n//i
   s += q*(q*i+i) // 2
print(s)

 

これ何なのかわかる??

 

わかる人は、以下もう読まなくても大丈夫だ。

 

 

 

僕はさっぱり意味がわからなかったので、こいつを読み解いて考え方を探るのは諦めることにして、自力で思い付く方法から地道に考えてみることにした。

 

 

 

 

さて、普通に考えるのならば、約数の個数を求めるべきだろう。

 

約数の個数の求め方は、素因数分解して、

Content image

とするのが一般的だが、

 

素因数分解して、指数にそれぞれ1を足して、掛け合わせて。

それを 1~N までの数に対して1つずつ行って。

如何にも時間が掛かる、この方針では間に合いそうもない。

 

 

そこで、こんなアルゴリズムがあるそうだ。

 

n = int(input())

table = [0] * n
   
for i in range(1, n+1):
   for j in range(i, n+1, i):
       table[j-1] += 1
       
print(table)

 

何をしているかと言うと、

 

Content image

 

1~n までのリストを用意しておき、

1の倍数、2の倍数、3の倍数・・・と順番にカウントしていく。

 

これで 1~n までの約数の個数を持ったリストが完成する。

 

こいつを使えば、元の問題も、これで終わりだ。

n = int(input())

table = [0] * (n+1)
   
for i in range(1, n+1):
   for j in range(i, n+1, i):
       table[j] += 1

ans = 0

for i, j in enumerate(table):
   ans += i*j

print(ans)

 

 

Content image

 

 

PyPy を使えば通るが Python だと時間オーバーになる。

 

もう少し工夫して Python で通るようにしたい。

 

Content image

 

今の状態は、それぞれ集計してから、Nを掛けて、それから和を求めている。

 

Content image

 

集計するのを止めて、直接的に和を求めた方が早いだろう。

 

N = int(input())

ans = 0    
for i in range(1, N+1):
   for j in range(i, N+1, i):
       ans += j

print(ans)

 

Content image

 

PyPy の実行時間はかなり早くなるが Python がほとんど変わらない。

 

 

もっと工夫しなければ。

 

 

Content image

 

ここで、

 

あ!!!!!!!!

 

わかった!!!!!!!

 

最初に載せた答えがどこから来てるのかわかったぞ!

 

 

なるほどぉぉぉ。

 

Content image

 

等差数列なので和の公式で求められる。

 

Content image

 

こっちの公式で出そう。

 

項数を q = N // i とすると、      ※ // は余りのある割り算の商を求める。

初項 i 、項数 q 、末項 q × i なので。

 

   q × ( i + q×i ) ÷ 2

 

という訳で。

N = int(input())

ans= 0

for i in range(1, N+1):
   q = N//i
   ans += q*(q*i+i) // 2

print(ans)

 

Content image

 

Pytnon でも通る、PyPy 早っ。

 

 

 

という訳だったんですね~。

 

これ我ながらよく結論まで辿り着けたと思っている、天才かもしらん。

 

 

 

約数の個数を列挙するアルゴリズムから出発して、徐々に今回の問題を解くことに特化したアルゴリズムに洗練されていく過程が面白かったので記事にしてみた。

 

 

僕が、あ!!!!わかった!!!!ってなった瞬間の感動が伝わっただろうか。

 

少しでも伝わっていると嬉しい。

 

 

 

Content image

 

Atcoder のキャッチコピーだが、コンテストに参加せず、しかも答えを最初に見てしまってから考えても、わかった!!が体験できるのだ。非常に良く出来たパズルだ。

 

さあ、みんなも Let's Atcoder !!

 

 

 

 

Supporter profile iconSupporter profile iconSupporter profile iconSupporter profile icon
Article tip 4人がサポートしています
獲得ALIS: Article like 118.89 ALIS Article tip 15.42 ALIS
ぺにょお's icon'
  • ぺにょお
  • @penyoo
少しばかり社会からぺにょってしまったものです。だめ人間です。生暖かい目で養ってください。https://twitter.com/penyoooooo

投稿者の人気記事
コメントする
コメントする
こちらもおすすめ!
Eye catch
他カテゴリ

機械学習を体験してみよう!(難易度低)

Like token Tip token
69.82 ALIS
Eye catch
他カテゴリ

警察官が一人で戦ったらどのくらいの強さなの?『柔道編』 【元警察官が本音で回答】

Like token Tip token
114.82 ALIS
Eye catch
グルメ

バターをつくってみた

Like token Tip token
124.75 ALIS
Eye catch
他カテゴリ

オランダ人が語る大麻大国のオランダ

Like token Tip token
46.20 ALIS
Eye catch
クリプト

Bitcoinの価値の源泉は、PoWによる電気代ではなくて"競争原理"だった。

Like token Tip token
159.32 ALIS
Eye catch
他カテゴリ

テレビ番組で登録商標が「言えない」のか考察してみる

Like token Tip token
26.20 ALIS
Eye catch
ビジネス

ブックオフで買ってきてアマゾンで売る仕事の1ヶ月の売り上げ公開

Like token Tip token
177.41 ALIS
Eye catch
クリプト

Bitcoin史 〜0.00076ドルから6万ドルへの歩み〜

Like token Tip token
947.13 ALIS
Eye catch
ゲーム

【初心者向け】Splinterlandsの遊び方【BCG】

Like token Tip token
6.32 ALIS
Eye catch
トラベル

無料案内所という職業

Like token Tip token
84.20 ALIS
Eye catch
他カテゴリ

SASUKEオーディションに出た時の話

Like token Tip token
35.87 ALIS
Eye catch
クリプト

17万円のPCでTwitterやってるのはもったいないのでETHマイニングを始めた話

Like token Tip token
46.60 ALIS