ferinの競プロ帳

競プロについてのメモ

SRM672 div1 easy Procrastination

考えたこと

  • 操作回数が多いのでうまくまとめる系の問題
  • 時刻hで従業員nがtaskを持っているとき交換が起きるのはn-1,nの約数でh+1以上の最小の時刻
  • 約数の列挙はO(sqrt(n))でO(n)個分やってたら当然TLE
  • 交換回数がO(logn)とかO(sqrt(n))になってくれるとうれしい
  • 約数の個数の分しか交換が起きないと考えると交換回数がO(sqrt(n))くらいになるのでは?みたいな気持ちになるけど証明はできない
  • 交換回数が少なければ約数列挙する幅が小さくなって区間篩?みたいな気持ちになる
  • 素因数の列挙はいいけど約数の列挙はつらい
  • そもそも約数の列挙なら区間篩いらない
  • 操作回数が少なくて実は約数を列挙する必要がある数がめちゃくちゃ少ないとかじゃないと解けない気がしてくる
  • 遅延評価みたいな感じで必要なところだけ約数の列挙をするコードを書く
  • 投げたら通ってしまった
    -----解説を見た-----
  • 素数区間でしか交換が発生しないから約数を求める必要のある数の個数が抑えられている
  • 素数区間は結構せまい(10^10で高々400)
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

map<ll, VL> mp;
VL func(ll x) {
  if(mp.find(x) != mp.end()) return mp[x];
  VL v;
  for(ll i = 2; i*i <= x; ++i) {
    if(x%i == 0) {
      v.PB(i);
      if(i*i != x) v.PB(x/i);
    }
  }
  v.PB(LLINF);
  sort(ALL(v));
  mp[x] = v;
  return v;
}

class Procrastination {
   public:
   long long findFinalAssignee(long long n)
  {
    ll now = n, h = 1;
    while(true) {
      // (now-1, now) の約数を求める
      VL v1 = func(now-1), v2 = func(now);
      ll min1 = *lower_bound(ALL(v1), h+1);
      ll min2 = *lower_bound(ALL(v2), h+1);
      if(min1 == LLINF && min2 == LLINF) {
        break;
      } else if(min1 < min2) {
        now = now-1;
        h = min1;
      } else {
        now = now+1;
        h = min2;
      }
    }

    return now;
  }
};