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

問題

https://atcoder.jp/contests/abc090/tasks/arc091_b

f:id:peroon:20200409040549p:plain

AC code

https://atcoder.jp/contests/arc091/submissions/11678651

解説

f:id:peroon:20200409040700p:plain

  • 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

ノート

f:id:peroon:20181225082923j:plain

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

その他

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