ABC179-C 備忘録 p.12

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

ABC179はリアルタイム参加できませんでした。残念

C - A x B + C

考察の流れ

N <= 10^6 なので、3重ループはさすがに間に合わない

ABC085-C をなんとなく思い出して、C はループせずに済みそう

無事(?)TLE…

#include <stdio.h>
#include <math.h>
int main(){
   long long n, cnt=0, c;
   scanf("%lld",&n);
   for(int a=1; a<=n; a++){
       for(int b=1; b<=n; b++){
       	if( a*b >= n ){ continue; } 
           c = n - a*b;
       	if( c && ceil(c) == floor(c) ){ cnt++; }
       }
   }
   printf("%lld",cnt);
   return 0;
}

謎の continue をやめ、B を N / A まで回す

#include <stdio.h>
#include <math.h>
int main(){
   long long n, cnt=0, c;
   scanf("%lld",&n);
   for(int a=1; a<=n; a++){
       for(int b=1; b<=n/a; b++){
           c = n - a*b;
       	if( c && ceil(c) == floor(c) ){ cnt++; }
       }
   }
   printf("%lld",cnt);
   return 0;
}

まとめ

・TLEするだろうな～と思いながら2重ループのまま投げたのは反省
・解説を見たらめちゃくちゃスマートに書かれていてひっくり返った
・解説を理解するまでに時間がかかった…こういう考察ができるようになりたい…

#note初心者 #備忘録 #AtCoder #ABC #競技プログラミング #競プロ #C言語 #計算量