読者です 読者をやめる 読者になる 読者になる

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

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したコードもカウントアップちゃんと書けたし(?)
前よりは成長してる...はず...。


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