No.311 z in FizzBuzzString / yukicoder

www.adventar.org

Advent Calendar Contest Advent Calendar 2015の問題で
★1があったので解けそう！！って思って解いてみました↓

#include<iostream>
using namespace std;
int main(){
    long long int n,count=0;
    cin >> n;
    for(long long int i=1; i<n+1; i++){
        if(i%15==0){
            count+=4;
        }else if(i%5==0 || i%3==0){
            count+=2;
        }
    }
    cout << count << endl;
    return 0;
}

提出したらTLE！

TLEって何！？ってなった。

(Time Limit Exceeded)は、実行時間切れです。
もっと時間効率のよいアルゴリズムを考えてみましょう。

って書いてあった(冷え
今まで実行時間を気にする様な問題を解いた事がなかったので
(簡単な問題しか解いてない為)
初めてのTLEだった！
※上記コードがTLEである事を除いて正しいかは不明(笑
※追記：for の中のiもlong long intに修正

入力に与えられる整数が　1<=N<=10^18　だったので、
きっとfor文で1個ずつ見ていくのがダメなんだろうと思ったけど、
頭の中はFizz Buzzのせいで(？)条件分岐しか思いつかず...
じゃあどうすればーーーーって所が全く浮かばなかった(眠かった)

先生「問題を分解してみよう」

言われた通りに分解した → (n/3+n/5)-n/15

あっ...！！ってなった...。

#include<iostream>
using namespace std;
int main(){
    long long int n;
    cin >> n;
    cout << (n/3*2)+(n/5*2) << endl;
    return 0;
}

それはそれはアッサリとAC出来た(完)
先生はいつも正解への誘導が上手です。

以上、TLEの勉強になったのでメモとして残しておきます。

でも...個人的には初めにTLEしたコードもカウントアップちゃんと書けたし(？)
前よりは成長してる...はず...。

@chiwawa_star 10^9とかそれ以上の値が制約に出てきたらとりあえず全部の整数をlong longにしておくと安全です（競プロ脳）

— なべさん (@nabedamamedofu) 2015, 12月 7

なべさんいつも正しい情報をありがとうです！！