ARC 118 A - Tax Included Price 解説

atcoder.jp

問題

消費税T%のとき課税後の整数値として現れないN番目のものを出力せよ。

制約

• 
• 

解説

ある自然数Aがあって、T*A の結果、100の位へ繰り上げがあるなら、(100+T)*A/100-1 は登場しない整数値である。

なぜなら、T*A で100の位への繰り上げが生じるならば、 の差が2になるためである。

また、100の位への繰り上げが発生する A と、その次に繰り上げが発生する A' の差は、高々100なので（T=1の場合、例えば、A=100, A'=200 と差が100になる）、登場しない整数値のN番目を愚直に求めようとするならば計算量は O(N⁹*100) になる。

A=1 から始めて、 の値が始めて0になった時の値を A の値を B、1～B の範囲で登場しなかった整数値の個数を cnt とすると、B+1～2B、2B+1～3B、... における個数も同様に cnt 個になる。（この B、cnt を求める計算量は高々 O(100) で十分高速）

cnt が求まっているなら cnt 倍数番目の登場しない整数値を O(1) で求めることができ、例えば 2*cnt 番目は、 と求めることができる。よって、この問題を高速に解くためには、N/cnt 番目の登場しない整数値を求め、そこから更に、N%cnt 番目の登場しない整数値を求めればよい。

N%cnt 番目の登場しない整数値が と表せるとすると、求める解は となる。

実装

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  int t,n; cin>>t>>n;
  
  int b=1,cnt=1;
  
  int sum=0; // 100の位への桁上がり検査のため、t*bのmod100の値を持つ
  while(t*b%100){
    sum+=t;
    if(sum>=100){
      cnt++;
      sum-=100;
    }
    b++;
  }
  
  int d=0;
  if(b>1) {
    d=n/cnt;
    n%=cnt;
  }
  
  int c=0;
  sum=0;
  if(n) while(n--){
    while(sum<100){
      sum+=t;
      c++;
    }
    sum-=100;
  }
  
  cout<<((100+t)*((ll)d*b+c))/100-1<<endl;
}

感想

区間内にある条件を満たす要素の個数を高速に数え上げる典型手法に、ある周期ではその要素数が同じになる → 周期内、周期の余り部分で別々に数え上げるというものがあり、その良い事例だった。