AtCoder Beginner Contest 090 解説備忘録

3907 ワード
競技プログラミング abc ABC090 AtCoder C++ C++ テキストリンク

前書き

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;
}

あとがき

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