AtCoder Beginner Contest 172を見直す(その３）D - Sum of Divisors

問題

D - Sum of Divisors

Σ出てきたから問題をここに転記するのを諦めた。noteも数式対応してくれるといいのに。ちなみに「notion」は数式に対応しました。あんまり使わないけど。

解説動画を見て作った解答

N = int(input())
int_list = [0 for _ in range(N+1)]
ans = 0
for i in range(1, N+1):
   for j in range(i, N+1, i):
       int_list[j] += 1
for i, cnt in enumerate(int_list): ans += i*cnt
print(ans)

ちなみに、考え方は170のD問題と同じです、詳しい解説を以前してるので気になる方はどうぞ。

が、しかし

上記の回答では「TLE(Time Limit Exceeded 」です。ちなみに「C++」だと同じ計算量でも通ります。

 #include  <bits/stdc++.h> #define  rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;

int main() {
   int N;
   cin >> N;
   vector<int> div_list(N+1);
   for (int i = 1; i <= N; i++) {
       for(int j = i; j <= N; j += i) div_list.at(j) += 1;
   }
   ll ans = 0;
   for (int i = 1; i <= N; i++) ans += ll(i)*div_list.at(i);
   cout << ans << endl;
}

言語格差。。。むしろこのD問題「Python」で通してる人すごい。O(N)とかで通してるんじゃないだろうか。

Youtubeのコメントとかみてても紙とペンを使って解法を導き出している人がいるようなので、次回はiPadとApple pencilで挑戦してみようかな。