AtCoder Beginner Contest 179を見直す

AtCoder Beginner Contest 179 - AtCoder

先週の土曜日にリアルタイムで挑戦した、「AtCoder Beginner Contest 179」を見直します。

全体の感想

50分でC問題まで解答できました、その後約1時間かけてD問題に挑戦したのですが解答できませんでした。難易度をみてみたところ、D問題はF問題よりもちょっと難しく、D、E共に「緑」の難易度でした。解答できたA,B,C問題は「灰」なので順当に解答できたといったところかと思います。

C問題見直し

C - A x B + C

問題

正整数nが与えられるので、a * b + c = nをみたす正整数の組み（a, b, c）がいくつあるか解答

提出したコード

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n;
   cin >> n;
   int r = sqrt(n);
   int cnt = 0;
   for(int i = 1; i <= r; i++){
       for(int j = i; j < n; j++){
           if(i * j < n) cnt++;
           else break;
           if( i != j) cnt++;
       }
   }
   cout << cnt << endl;
   return 0;
}

aとbが決まれば、cは自動的に決まるので考えなくて良いです。よって1以上n以下の各数字について確認を行なっています。なんとなく、多重ループにしなくても解ける気がしたんですが思いつかなかったです。

解説動画を見たところ以下のようにすると、多重ループにしなくても解けるようです。

解説を見て作成したコード

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n;
   cin >> n;
   int cnt = 0;
   for(int a = 1; a <= n; a++){
       cnt += (n - 1) / a;
   }
   cout << cnt << endl;
   return 0;
}

答えみると簡単なんですが、なかなか出てこないな。。。