【AtCoder】いろんな言語でやってみる C言語編

1. AtCoderって何？

AtCoderは、世界最高峰の競技プログラミングサイトです。3,000以上の過去問にいつでもチャレンジすることができるので、スキルを磨きたい場合や、新しい言語を学んだ際にトライすることで理解を深めることができます！自分もリアルタイムで競技に出たことは一度しかなく、大体過去問を説いています！

2. 問題（初級）

2020/10 AtCoder Regular Contest 106
実行時間制限: 2 sec / メモリ制限: 1024 MB (配点：300点)

例えば、入力Nが106であった場合、(A, B) = (4, 2)が挙げられます。

3. 問題に対する考え方（アルゴリズム）

（以下、noteでの表現上、累乗の記号を^で表します。）
皆さんはどのように考えたでしょうか？（コメントください！）
自分は、任意の数字Nに対して、AとBを1から順番に入れていく方法をまずは思いつきました。
加えてA, Bの制約について、Nの上限が10^18なので、

　3^38 > 10^18  ,    5^26 > 10^18

であることから、仮に解があったとしても、

　1 ≤ A ≤ 37 かつ 1 ≤ B ≤ 25

であるので、かなり範囲が絞れました！よっしゃ！
また、

答えが複数存在する場合はどれを出力してもかまわない。

とのことなので、AとBのペアで小さい値から見ていき、一つでもヒットすれば、処理をやめて終わらせることができますね。

考え方は良いとして、後はその考え方（アルゴリズム）をコード上で表現できるかです。初めてAtCoderの問題を解いた時に、まず「入力・出力ってなんぞや？」「考え方は分かったけど何をすればいいのや？」になりました（笑）
よって、ソースコード上にはコメントアウトにて書き方を記載しています。

4. 回答例

ローカル開発環境、ローカル実行環境
OS : macOS Catalina 10.15.6
プロセッサ：2.4 GHz デュアルコアIntel Core i7
メモリ：16 GB
ストレージ：256GB

# main.cというファイルを作成します。
自分のMacPC$ vim main.c 

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main() {   
  // 変数の定義
  long int N, A, B;

  //// 任意の数字の入力
  // 任意の数字を入力できる関数
  scanf("%lf",&n);

  //// やりたいこと：全パターン計算していきます
  // A, Bに1から繰り返して順番に値を入れて、式が成り立つか確認します
  // もし、式が成り立てば、プログラムを終了します

  // Bの条件は1 ≤ A ≤ 37なので、38回目以降は処理しないようにします
  for (A = 1; A < 38; A++) {
    // Bの条件は1 ≤ B ≤ 25なので、26回目以降は処理しないようにします
    for (B = 1; B < 26; B++ ) {
        // 式が成り立つか確認します。(3^a + 5^b = n)
    　　 if(N == (powl(3, A) + powl(5, B))) {
            // 式にマッチすれば、出力として表示します
            // この時、A ,Bはint型にキャストします
            printf("%d %d\n", (int)A, (int)B);
            // プログラムを終了します
            exit(0);
        } 
     }
  }
  // プログラムがexit(0)で終了されずにここまで来た場合は、
  // 解がなかったとして、-1を出力します
  if (count == 0) {
    printf("-1¥n");
  }
  return 0;
}

（注）¥nはそのまま貼り付けるとうまく貼り付けができない場合がありますのでご注意ください。

# いざ、実行！
# コンパイル
自分のMacPC$ gcc main.c

# N = 8の場合
自分のMacPC$ ./a.out
8
1 1
(想定どおり)

# N = 16の場合
自分のMacPC$ ./a.out
16
-1
（想定どおり）

# N = 10460353208の場合
自分のMacPC$ ./a.out
10460353208
21 1
（想定どおり）

実際にAtCoderでソースコードを提出してみる。

下記のようにソースコードを貼り付けて、「提出」をクリック。。。

ドキドキ。。。やったぁーークリア！300点GET!!!

5. 感想

うーん。初心者にはちょうどいいか少し難しいかも？for文やif文、関数、変数やオーバーフロについて当たり前のように問われるので、基本的な知識（ネットで調べえたらすぐわかるレベル）があれば解ける問題かと思いますが。。！
AtCoder系の掲載について、今後は簡単な問題・難しい問題というより、いい練習になる問題を解説していきたいともいます！
　今回のキーワードは下記です！

#AtCoder #C言語 #for文 #if文 #キャスト #pow関数 #コンパイル #オーバーフロー #プログラミング #競技プログラミング

6. 参考文献

AtCoderについて

7. お問い合わせ先

本投稿のコメントでも構いませんし、下記からお問い合わせいただいても大丈夫です。
note.tamolab@gmail.com