ARC106 参戦記録 p.27

itsukiです。
AtCoder Regular Contest 106 に参戦した様子です。解説記事ではありません。

AtCoder Regular Contest 106 - AtCoder

結果は A (3WA) の 1完でした。

考察の流れ

A. 106

A - 106

～迷走ここから～
10^18 なので、全探索は無理？
3^A = ( N^(1/A) - 5^(B/A) )^A になるから、
3 = N^(1/A) - 5^(B/A) になればいいか？あれ？
～迷走ここまで～

高々 3^38 > 10^18, 5^26 > 10^18 か！全探索問題だった！！
ということで、二重ループで全探索してみる
WA…（1回目）; ACx12, WAx10

無駄に 3^40, 5^30 までループを回してみる
色々キャストを入れてみる
WA…（2回目）; ACx12, WAx10

(A,B) は正の整数の組か！ループを 0(乗) から回していたことに気づく
WA…（3回目）; ACx16, WAx6

誤差が出るような問題じゃないし…まさかオーバーフロー…？
pow() の返値が double であることに気づく
powl() を使い、かつ「3^A = N - 5^B」となるかを判断する

#include <stdio.h>
#include <math.h>
typedef long long ll;
typedef long double ld;
int main(){
   ll n;
   scanf("%lld",&n);
// for(ll a=0; a<39; a++){
   for(ll a=1; a<39; a++){
//     for(ll b=0; b<27; b++){    
       for(ll b=1; b<27; b++){
//         if( pow(3,a) + pow(5,b) == n ){
//         if( (ll)pow(3,(double)a) + (ll)pow(5,(double)b) == n ){    
           if( (ll)powl(3,(ld)a) == n - (ll)powl(5,(ld)b) ){
               printf("%lld %lld\n",a,b);
               return 0;
           }
       }
   }
   printf("-1\n");
   return 0;
}

まとめ

・初動が遅れた　もう少し早く全探索に気づけたはず…反省
・さすがに 3WA はやりすぎ　特に2回目の WA は防げたはず
・問題の定義をよく見て（正の整数に0は入らない…）
・本番で300点を通せたのは成長！ということに

引き続き、のんびり精進します。

#note初心者 #備忘録 #参戦記録 #AtCoder #ARC #プログラミング #競プロ #C言語