SRM 672 Div1 Easy - Procrastination

問題

TopCoder Statistics - Problem Statement

問題概要

とある巨大な会社には従業員が無限にいる。従業員には1,2,3,...と番号が振られている。番の従業員は仕事をし始める時は番のタスクを請け負っている。その会社の就業時間は無限にあり、仕事時間が1時間ごとに区切られている。

その区切られた時間を1時間目、2時間目、...と呼ぶことにして、2以上のに対して、時間目に以下のことを行う：

より大きく、で割り切れる番号(つまり、番)の従業員は自分の番号より1大きい人とタスクを交換する。 これを無限に繰り返していく時、番目のタスクを最終的に抱えている人は何番の従業員になるか求めよ。

• 

アイデア

まず、この操作は無限に続いていくが、番目の従業員がタスクを交換するタイミングはであるタイミングでしか起き得ないので、有限時間で終わらせることができることが分かる。

更に、番目の従業員がタスクを交換するタイミングはがかの約数となるタイミングだけであるから、そんなに交換する回数はに対して多くならないはずである。

のサイズ的に、を１つずつ増やしながらシミュレーションしていくと時間が足りないが、交換するタイミングだけに注目して計算できればそんなに約数の個数はどの数に対しても多くないので割と効率的に出来るのではないか、と考える。そうすると、番目の従業員に対して、交換が起きるタイミングはの約数との約数の中で以上のもののうち最小の値のタイミングで起きることが分かる。

の約数をリストで返す関数を作る。これはで実現できる。また、図をかいてシミュレーションしてみると同じような数に対して何度もこのアクセスが起こることが分かる。なのでmapで既に求めたものを保存しておけば、アクセス回数を減らすことが出来て効率的に計算できる。リストの中から、以上のものの中で最小値を探す動作はlower_boundが良い。

いまいち計算量の見積はむずかしいが、約数の数はそんなにおおくないのでこれで十分間に合う。

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

class Procrastination {
    public:
    //nの約数を返す
    vector<ll> factor(ll n){
      vector<ll> ret;
      ret.pb(1);
      for(ll i=2; i*i<=n; ++i){
        if(n%i==0) ret.pb(i);
      }

      int z=ret.size();
      for(int i=z-1; i>=0; --i) ret.pb(n/ret[i]);

      sort(ret.begin(),ret.end());
      ret.erase(unique(ret.begin(),ret.end()),ret.end());
      return ret;
    }

    long long findFinalAssignee(long long n) {
      if(n<=3) return n;

      //現在そのタスクを抱えている従業員
      ll ret=n;

      ll h=2;
      map<ll,vector<ll>> m;

      ll ct=0;
      while(h*2<=ret){
        vector<ll> now;
        vector<ll> pre;

        if(m.find(ret)==m.end()) now=m[ret]=factor(ret);
        else now=m[ret];

        if(m.find(ret-1)==m.end()) pre=m[ret-1]=factor(ret-1);
        else pre=m[ret-1];

        ll a = *lower_bound(now.begin(),now.end(),h);
        ll b = *lower_bound(pre.begin(),pre.end(),h);

        if(a<b){
          ++ret;
          h=a+1;
        }
        else{
          --ret;
          h=b+1;
        }

        //printf("ret= %lld, h= %lld\n",ret, h);
        //printf("a,b :%lld %lld\n",a,b);
      }

      return ret;
    }
};