競プロの回答がTLEとなる

https://atcoder.jp/contests/abc051/tasks/abc051_b
上記のAtcoderの問題の回答がTLE(実行時間制限超過)になってしまいます。
原因と対処法を教えて下さい。```c++
コード
#include<bits/stdc++.h>
using namespace std;
int main(){
int k,s;
cin >> k >> s;
int df = 0;
for(int x = 0;x <= k;x++){
for(int y = 0;y <= k;y++){
for(int z = 0;z <= k;z++){
int gh = x + y + z;
if(gh == s){
df++;
}
}
}
}
cout << df << endl;
}

pepperleaf

2019/08/13 07:56

ルール見ると、個人で戦う必要があります。とありますが、問題無いですか?

set0gut1

2019/08/13 08:03

コンテスト期間が終わった過去問については情報交換して大丈夫ということになっていると思います

行動規範の内容に同意します

回答2件

ベストアンサー

大方針:とにかく繰り返しの回数を減らすこと。特に多重ループは、掛け算で計算回数を増やします。できれば、繰り返し処理そのものを省ければ一番。

1.とりあえず、今のプログラムでひとつx+y+zの組み合わせを見つけたら、少なくともそれ以降のzの探索は確実に無駄ですから、

C++
1  for(int z = 0;z <= k;z++){
2    int gh = x + y + z;
3    if(gh == s){
4      df++;
5      break;
6    }
7  }

とするぐらいはノーヒントで思いついて欲しいと思います。

2.ループの範囲だって制限できるでしょう。
s-x<0だったりs-x>2kなら条件を満たすy,zはありません。
つまり、xの探索ループの下限値は0とs-2kの大きい方、上限値はkとsの小さい方、となります。
s-x>kなら、yがs-x-k未満には解はありません。
s-x<kのときには、yがs-xを超える解はありません。
言い換えれば、yの探索ループの下限値は0とs-x-kの大きい方、上限値はkとs-xの小さい方、となります。

x,yが決まったら、z=s-(x+y)として 0 ≦ z ≦ k であることを確かめればいいだけで、(ちゃぶ台返しになりますが)そもそもzについてループを回す必要はないでしょう。

3.さらに言えば、
xの範囲は上記で決まるとしてs-x=y+zを満たす整数y,zの組は
s-x≦kならs-x+1組
s-x>kなら2k-(s-x)+1組
になるんじゃないかしら。

これらを考え合わせると、ループなんて一つも使うこと無く求められるわけですよね。

つぶやき。
初心者にループを説明するときの例題に、1～nまでの和をforループでまじめに? 一つずつ足して求めるというのがありますよね。数列の和を求めるという視点では「不適切」と言っても過言ではないやり方を教えていることになると思うのですけれど。そういう型にハマってしまっていたりするのでしょうか。

投稿2019/08/13 09:58