はじめに
AtCoderBeginnerContest?のD問題辺りではよく、例えば0~Nをbで割った時余りがK以上である数の総数を求めるなど、
2変数を用いてループでしらみつぶしに数えていく(俗にいう愚直解)解法では時間がかかりすぎて正解にならないことが往々にしてある(ていうかそういう時にどうするかを考えるのが競技プログラミングなんやけど)。
昨日解いてた問題がちょうどそんな感じだったんで考えをまとめます！
問題
AtCoderBeginnerContest090のD問題(https://beta.atcoder.jp/contests/abc090/tasks/arc091_b)
N以下の正の整数の2つ組(a,b)の内,a%b>=Kとなるものの総数を求めよ。
【制約】 1 ≤ N ≤ 10^5 , 0 ≤ K ≤ N−1
ざっくり書くとこんな問題
愚直解
時間無視で解こうとすると
int main(){
long long N,K,a,b,count=0;
cin >> N >> K;
for(a=0;a<=N;a++){
for(b=0;b<=N;b++){
if(a%b>=K)count++
}
}
cout << count << endl;
return 0;
}
みたいな感じになるのかな(適当に書いたしコンパイルもしてないけど)。
Nが5乗だからこれだと２回ループ回したらタイムアウトすると思う。大体２秒制限だと8乗とか9乗ぐらいが限界だと思います。
で、ずーっと計算を簡単にしたり、まとめて計算できるところはまとめてしたり、ループの範囲とか色々工夫してみたけどどーーーもダメ。
みたいな感じやったけど、気付くと意外と単純だった！
解説
ではどうするか、こういう２変数の問題では片方を固定して一方を回すのがいい(のかな？)。
今回の問題、0~Nの数一つ一つをbで割った余りは、0~b-1の数を繰り返す。分からなかったら紙に書いて考えてみて。
その繰り返し単位を一つのグループとして、そのグループ一つの内、余りがK以上のものを数え上げればいい。
コード
#import <iostream>
using namespace std;
int main(){
long long N,K,a,b,group,sum=0;
cin>>N>>K;
//Kが0の時だけ分ける
if(K==0)sum=N*N;
//a,b両方動かすとあれなのでbだけ動かす
//あるbについて0~Nの数をそれぞれbで割った値は0~b-1を繰り返す
//そのグループ一つに関して条件を満たすのが何個あるか考える
else{
for(b=K;b<=N;b++){
//グループが何個できるか計算。
group=(N-N%b)/b;
//そのグループ一つで条件を満たすのは何個か数え、グループ倍
sum+=(b-K)*group;
//グループに入らんかった分計算して足す
if(N%b>=K)sum+=N%b-K+1;
}
}
cout<<sum<<endl;
return 0;
}
見辛かったらごめんなさい〜
最初のうちは、途中計算の一瞬でもint型越えるかもしれんなって思ったらlong long使った方がいいと思います。今回はどうなんだろ、intでいけたかも。
感想
今回の考えって汎用性あるんだろうか、面白かったからいいけど。
記事書き慣れてないしプログラミングも初心者なんで変なとこあったら教えてください！
よくわかんなかった人はまた聞いてください。