ABC162に参加してみました - インフラエンジニアの備忘録とか色々

初めに

こんにちわ！このご時世で家でやることが無かったのではてなブログを初めました。
今回は先週参加したAtCoderのABC 162で自分が回答出来たものについて書こうと思います。

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

A - Lucky 7

この問題は、3桁の整数Nが与えられた時に、Nのいずれかの桁に数字の7が含まれているか判定した結果を出力する問題です。

#include <bits/stdc++.h>

using namespace std;

int main(){

string N;

cin >> N;

if(N.find('7') != std::string::npos) cout << "Yes" << endl;
else cout << "No" << endl;

return 0;

}

入力を文字列として受け取り、文字列クラスstringのfind関数を使用して'7'が含まれているか判定をしています。 nposはfind関数で値が見つからなかった場合に戻り値として返す値が定義されており、その値を比較して判定結果を出力しています。

cpprefjp.github.io

B - FizzBuzz Sum

この問題は、整数Nが入力として与えられ、N項までFizzBuzzを行った際に下記ルールに該当しなかった整数の和を出力する問題です。

　①. 3 でも 5 でも割り切れるなら　→　FizzBuzz
　②. そうではなく 3 で割り切れるなら　→　Fizz
　③. そうではなく 5 で割り切れるなら　→　Buzz

#include <bits/stdc++.h>

using namespace std;

int main(){

long long N,ans = 0;

cin >> N;

for(long long i = 1;i <= N;++i){

    if(i%3 == 0 && i%5 == 0) continue;
    if(i%3 == 0) continue;
    if(i%5 == 0) continue;

    ans+=i;

}

cout << ans << endl;

return 0;

}

for文で1からN項までの整数をカウントしていき、上記ルールの①～③の何れかに該当した場合は処理をスキップします。
ルールに該当しなかった場合は変数ansにカウンタ変数iの値を加算し、その結果を出力しています。

・・・書いていて思いましたが、別に3つもif文を書く必要はないですね、、、 3か5で割り切れなかったら場合に変数ansにカウンタ変数iの値を加算すれば良いだけですね。 (コンテスト終わってから気付くことが多々あるんですよね、、、)

#include <bits/stdc++.h>

using namespace std;

int main(){

long long N,ans = 0;

cin >> N;

for(long long i = 1;i <= N;++i) if(i%3 != 0 && i%5 != 0) ans+=i;

cout << ans << endl;

return 0;

}

C - Sum of gcd of Tuples (Easy)

この問題は、整数Kが与えれた時に下記の式の通り3つの整数に対するgcd(最大公約数)を求め、その総和を求める問題です。

$\displaystyle{ \sum_{a=1}^k\sum_{b=1}^k\sum_{c=1}^kgcd(a,b,c) }$

#include<bits/stdc++.h>

using namespace std;

int main(){

long long K,ans = 0;

cin >> K;

for(int i = 1;i <= K;++i){
    for(int j = 1;j <= K;++j){
        for(int k = 1;k <= K;++k){

            ans += gcd(gcd(i,j),k);

        }
    }
}

cout << ans << endl;

return 0;

}

Σは総和を表す記号でforループで計算を行う事ができ、今回の場合は3重のΣの計算であったため3重のforループを書いています。 gcdはユークリッドの互除法というアルゴリズムで求められます。(C++ではgcd求める関数があるためそれを利用しています。)
3つの整数のgcdは何れかの2つの整数のgcdと残った1つとの整数とのgcdを計算すれば求める事が出来ます。

計算量がO(N³)でしたが、整数Kの制約が 1<=K<=200 であったためTLEは発生しませんでした。

mathtrain.jp

最後に

今回はD問題の回答を考えているところでタイムアップしていました。D問題は解けたり解けなかったりというのが続いているので、過去のD問題等を解いて安定的に解けるようになりたいですね。最終的にはA～F問題までの解いてブログに載せられればなぁと思っているので頑張ります。(いつになることやら、、、)