AtCoder Beginner Contest 090 解説備忘録

前書き

AtCoder Beginner Contest 090 を解いてみた．解けなかった問題の備忘録．

D問題

[問題はこちら]

・aについて固定するかbについて固定するか迷う所だが，bを固定したときのあまりa%bは，1,2,3,...,b-1,0を繰り返すという規則性があるため，bを固定して考える．

・bを固定して考えたとき，"1,2,3,...,b-1,0"のうちK以上のものを数えたいのだが，無論その時b-1とKの大小関係を考える必要がある．

・"1,2,3,...,b-1,0"はN/bセットある．最後のセットは"1,2,...,N%b"という並びである．

・cnt += max(0,n%b-k+1);は，k=0とk=1では違う結果が反映されるが，実際はk=0とk=1は同じ結果になるため，そこの場合分けが必要．

以下ACのコード：

main.cpp

# include <iostream>
# include <vector>
# include <algorithm>
# include <string>
# include <cmath>
# include <set>
# include <sstream>
# include <bitset>
# include <stack>
# include <cstdlib>

# define FOR(i,a,b) for(int i=(a);i<(b);++i)
# define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

int main() {
    
    int n,k;
    cin >> n >> k;
    
    ll cnt=0;
    
    FOR(b, 1, n+1){
            /*
             if(b-1<k){
             cnt += 0;
             }else{
             cnt += (n/b) * (b-k);
             }
             */
            
            cnt += max(0,b-k)*(n/b);
            cnt += max(0,n%b-k+1);
            if(k==0){
                cnt--;
            }
        }
    
    cout << cnt << endl;
    
    return 0;
}

あとがき

境界条件/初期条件 は必ず確認せよ!!!
精進します．