D - Remainder Reminder (arc091_b) 丁寧に数え上げる

• 問題
  • https://atcoder.jp/contests/abc090/tasks/arc091_b

• AC code
  • https://atcoder.jp/contests/arc091/submissions/11678651

解説

• N=20, K=5で具体的に描いてみましょう
  • (Google spreadsheetの関数 ARRAYFORMULAというのを使ってみた)
• 右上の黄色い領域は数えやすそう・左下の赤い領域は数えづらそう・・・
• 列ごとに見ると良い
• 例えば b=7の列では、0～6が周期的に出て、その中の5, 6だけがK=5以上の条件を満たす
• 周期性があるので各列で数えるのはO(1)でできるので、bを全探索して全体ではO(N)で解くことができました

code

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin>>N>>K;

    if(K==0){
      p(N*N); return 0;
    }

    ll sum=0;
    FOR(b,2,N+1){
      // 本数
      ll num = (N+1)/b;
      // 1本あたり、いくつ（条件に合うものが）含まれるか
      ll a = max(0LL, b-K);
      sum += num*a;

      ll rest = (N+1)%b;
      sum += max(0LL, rest-K);
    }

    p(sum);

    return 0;
}

以下は古いメモ

提出

https://atcoder.jp/contests/abc090/submissions/3868505

ノート

• N = 11
• K = 3
• で見てください

その他

• 表を書くと規則性が見える
• 左下には塊でK以上が発生する
• 右上にもちらほら発生する
  • 1行ずつ（サーチではなく）計算で求めればO(N)で求まる
• 解答pdfは右上・左下で分けず、行ごとに見た規則性から数えている
  • でも似ている