AtCoder Beginner Contest 096 解説備忘録

前書き

AtCoder Beginner Contest 096 を解いてみた．解けなかった問題の備忘録．

C問題

[問題はこちら]

・vector<int> dx{1,-1,0,0};，vector<int> dy{0,0,1,-1};でfor文を回せばまだ速かったかも．

D問題

[問題はこちら]

・一の位が1である素数を取り出せば良い，そうすればどの5つを取っても，その和の一の位は絶対5になるため，合成数(5の倍数)となる(気づかん)．

以下ACのコード：

main.cpp

# include <iostream>
# include <vector>
# include <algorithm>
# include <string>
# include <cmath>
# include <set>
# include <sstream>
# include <bitset>
# include <stack>
# include <cstdlib>

# define FOR(i,a,b) for(int i=(a);i<(b);++i)
# define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
    
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {// 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

int main() {
    
    int n;
    cin >> n;
    
    vector<int> ans(n,0);
    int i=1,j=0;
    while(ans[n-1]==0){
        int a;
        a = 1 + 10*i;
        if(IsPrime(a)){
            ans[j] = a;
            j++;
        }
        i++;
    }
    
    FOR(i, 0, n){
        cout << ans[i] << endl;
    }
    
    return 0;
}

あとがき

比較的簡単な回だった...？
精進します．