SRM630 div1 easy Egalitarianism3

概要

n頂点の重み付きの木が与えられる。集合の任意の2頂点の距離が等しくなるような頂点集合のうち、集合の要素数の最大を求めろ。

解法

ある頂点を根とした木で根からの距離を考える。根からの距離が等しい2頂点a, bでaとbのLCAが根であるような頂点であれば頂点集合に入れることができる。
根rの子を r[0], r[1], …, r[k] とする。r[i]を根とする部分木で根からの距離dの頂点が存在するならば頂点間の距離が2dであるような頂点集合S(2d)の要素数を1増やせる。r[i]の部分木の頂点の根から距離の集合Tをdfsで求めたあと、S(2d)に+1する。これを全てのr[i]について計算することで、根rから距離が等しくなるような頂点集合の取りうる要素数を求められる。

#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};

ll d[55][55];
vector<PII> g[55];
int v[1000010];
set<int> st;

void dfs(int v, int p, int r) {
  for(PII i: g[v]) {
    if(i.first == p) continue;
    st.insert(d[r][i.first]);
    dfs(i.first, v, r);
  }
}

class Egalitarianism3 {
   public:
   int maxCities(int n, vector <int> a, vector <int> b, vector <int> len)
  {
    if(n == 1) return 1;
    REP(i, n) g[i].clear();
    REP(i, n) REP(j, n) {
      if(i == j) d[i][j] = 0; else d[i][j] = INF;
    }
    REP(i, n-1) {
      g[a[i]-1].PB({b[i]-1, len[i]});
      g[b[i]-1].PB({a[i]-1, len[i]});
      d[a[i]-1][b[i]-1] = d[b[i]-1][a[i]-1] = len[i];
    }
    REP(k, n) REP(i, n) REP(j, n) chmin(d[i][j], d[i][k] + d[k][j]);

    int ans = 2;
    REP(i, n) {
      // 頂点iを根としたとき
      memset(v, 0, sizeof(v));
      int ret = 0;
      for(PII j: g[i]) {
        st.clear();
        st.insert(d[i][j.first]);
        dfs(j.first, i, i);
        for(int k: st) {
          if(k >= INF) continue;
          v[k]++;
          chmax(ret, v[k]);
        }
      }
      chmax(ans, ret);
    }

    return ans;
  }
};

SRM629 div1 easy RectangleCovering

概要

holeH、holeWの大きさの穴を複数の板を使って塞ぐ。板iの大きさはboardH[i]、boardW[i]である。板は重なっても良いが全ての角が穴の外に位置していなければならない。このとき塞ぐのに必要な最小枚数を答えろ。不可能なら-1を答える。

解法

holeH >= boardH && holeW >= boardW の板を使用することはできないので無視する。
holeHより一辺が大きい板を使って穴をふさいでいくとき、板が足りずふさぎきれなかったとする。このときまだ空いている穴を塞ぐには、holeWより一辺が大きい板を使用してふさぐ必要がある。しかし、holeWより一辺が大きい板でふさげるのであればholeHより一辺が大きい板を使用する必要はない。したがって、holeHより一辺が大きい板のみでふさぐか、holeWより一辺が大きい板のみでふさぐかの2パターンで独立に考えられる。
それぞれ、条件を満たす板を列挙しておきより広い範囲をふさげる板から貪欲に使用していけばよい。sortが一番時間がかかっていてO(nlogn)で計算できる。

最初 holeH+1 < max(boardH, boardW) がふさげる板の条件かと思ったけどサンプルが合わなくて悩んだ。よくよく考えると格子点上だけに板の角を配置できるわけじゃなさそう。

#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};

class RectangleCovering {
   public:
   int minimumNumber(int holeH, int holeW, vector <int> boardH, vector <int> boardW)
  {
    int n = boardH.size();
    vector<PII> v1, v2;
    REP(i, n) {
      if(boardH[i] > holeH && boardW[i] > holeH) {
        v1.PB({max(boardW[i], boardH[i]), min(boardW[i], boardH[i])});
      } else if(boardH[i] > holeH) {
        v1.PB({boardW[i], boardH[i]});
      } else if(boardW[i] > holeH) {
        v1.PB({boardH[i], boardW[i]});
      }

      if(boardH[i] > holeW && boardW[i] > holeW) {
        v2.PB({max(boardW[i], boardH[i]), min(boardW[i], boardH[i])});
      } else if(boardH[i] > holeW) {
        v2.PB({boardW[i], boardH[i]});
      } else if(boardW[i] > holeW) {
        v2.PB({boardH[i], boardW[i]});
      }
    }
    sort(ALL(v1)); sort(ALL(v2));
    reverse(ALL(v1)); reverse(ALL(v2));

    ll now = 0, ans = LLINF;
    REP(i, v1.size()) {
      now += v1[i].first;
      if(now >= holeW) {
        ans = i+1;
        break;
      }
    }
    now = 0;
    REP(i, v2.size()) {
      now += v2[i].first;
      if(now >= holeH) {
        chmin(ans, i+1);
        break;
      }
    }
    return ans == LLINF ? -1 : ans;
  }
};

SRM628 div1 easy DivisorsPower

概要

d(n) = (nの正の約数の個数)、h(n) = n^d(n)とする。x = h^-1(n) を求めろ。複数存在する場合は最も小さいものを求めろ。

解法

d(x) として使われうる値は20程度までしか存在しない。d(x)を決め打って、そのd(x)のときh^-1(n)が存在するか考える。nのm乗根を求めたあとd(nのm乗根) == mであるかどうか判定すればよい。nのm乗根は二分探索を用いてO(mlogn)、d(n)はO(sqrt(sqrt(n)))で計算できる。全体で O( max(d(x))(mlogn + sqrt(sqrt(n))) ) で計算できる。
オーバーフローに注意

#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};

//二分累乗法 xのe乗
ll binpow(ll x, ll e) {
  ll a = 1, p = x;
  while(e > 0) {
    if(e%2 == 0) {p = (p*p); e /= 2;}
    else {a = (a*p); e--;}
  }
  return a;
}

// nのm乗根 整数でなければ-1 O(mlogn)
ll root(ll n, ll m) {
  ll lb = 1, ub = n;
  while(ub-lb > 1) {
    ll mid = (lb+ub)/2, tmp = mid, prev = 1;
    REP(i, m-1) {
      if(tmp/prev != (tmp*mid)/tmp) {tmp = n+1; break;}
      prev = tmp;
      tmp *= mid;
    }
    if(tmp >= n) ub = mid;
    else lb = mid;
  }
  ll tmp = ub, prev = 1;
  REP(i, m-1) {
    if(tmp/prev != (tmp*ub)/tmp) {tmp = -1; break;}
    prev = tmp;
    tmp *= ub;
  }
  if(tmp == n) return ub;
  return -1;
}

class DivisorsPower {
   public:
   long long findArgument(long long n)
  {
    ll ret = INF;
    FOR(i, 2, 21) {
      ll sq = root(n, i);
      if(sq == -1) continue;
      // d(sq) = i であれば
      ll cnt = 0;
      for(ll k=1; k*k<=sq; ++k) {
        if(sq%k==0) {
          cnt++;
          if(k*k!=sq) {
            cnt++;
          }
        }
      }
      if(cnt == i) chmin(ret, sq);
    }
    return ret==INF ? -1 : ret;
  }
};

SRM627 div1 Easy HappyLetterDiv1

概要

文字列S(|S|<=50)が与えられる。この文字列から異なる文字の2つ組を取り除く処理を繰り返していき最後に残る可能性のある文字の集合を求めろ。

解法

文字cが最後に残る可能性があるかどうかについて考える。文字c以外を全て消せるかどうか判定できればよい。最大の文字の個数<=それ以外の文字の個数で文字数が偶数であれば全てぴったり消すことができる。最大の文字の個数<=それ以外の文字の個数で文字数が奇数であれば1文字残る。最大の文字の個数>それ以外の文字の個数であれば(最大の文字の個数)-(それ以外の文字の個数)が残る。
残る文字数より文字cの数が多ければ文字cが最後に残る可能性がある。

#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};

class HappyLetterDiv1 {
   public:
   string getHappyLetters(string s)
  {
    int n = s.size();
    int cnt[26] = {};
    REP(i, n) cnt[s[i]-'a']++;

    string ret = "";
    REP(i, 26) {
      if(cnt[i] == 0) continue;
      int ma = 0, su = 0;
      REP(j, 26) if(i != j) {
        su += cnt[j];
        chmax(ma, cnt[j]);
      }
      if(cnt[i] == 1 && su%2) continue;
      if(ma > su-ma) {
        if(ma - (su-ma) >= cnt[i]) continue;
      }
      ret += (char)('a'+i);
    }

    return ret;
  }
};

ARC055 C - ABCAC

問題ページ
C - ABCAC

公式解説のaとcを高速に求める方法について

解法

aとcをそれぞれ求めたあと a>0 && c>0 && a+c>=|y| を満たしていればABCACが構成できる文字列ABCの組み合わせは a+c-|y|+1 通りある。

SAとlcp配列とRMQ

SAとlcp配列を構築する。rank[sa[i]] = i とする。
文字列Sのi,jから始まる接尾辞の先頭共通文字数は区間 [rank[i], rank[j]) のうち最小のlcp配列の値なのでセグメントツリーなどを使えばO(logN)で求められる。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#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()

// suffix array
int n, k1;
int tmp1[200010], ran1[200010];

bool compare_sa1(int i, int j) {
  if(ran1[i] != ran1[j]) return ran1[i] < ran1[j];
  else {
    int ri = i+k1<=n ? ran1[i+k1] : -1;
    int rj = j+k1<=n ? ran1[j+k1] : -1;
    return ri < rj;
  }
}

// O(nlog^2n)
void construct_sa1(string s, int *sa) {
  n = s.size();
  REP(i, n+1) sa[i] = i, ran1[i] = i<n ? s[i] : -1;

  for(k1 = 1; k1 <= n; k1*=2) {
    sort(sa, sa+n+1, compare_sa1);

    tmp1[sa[0]] = 0;
    FOR(i, 1, n+1) {
      tmp1[sa[i]] = tmp1[sa[i-1]] + (compare_sa1(sa[i-1], sa[i]) ? 1 : 0);
    }
    REP(i, n+1) {
      ran1[i] = tmp1[i];
    }
  }
}

// O(n)
void construct_lcp1(string s, int *sa, int *lcp) {
  n = s.size();
  REP(i, n+1) ran1[sa[i]] = i;

  int h = 0;
  lcp[0] = 0;
  REP(i, n) {
    int j = sa[ran1[i] - 1];
    if(h > 0) h--;
    for(; j+h<n && i+h<n; ++h) {
      if(s[j+h] != s[i+h]) break;
    }

    lcp[ran1[i]-1] = h;
  }
}

int k2;
int tmp2[200010], ran2[200010];

bool compare_sa2(int i, int j) {
  if(ran2[i] != ran2[j]) return ran2[i] < ran2[j];
  else {
    int ri = i+k2<=n ? ran2[i+k2] : -1;
    int rj = j+k2<=n ? ran2[j+k2] : -1;
    return ri < rj;
  }
}

// O(nlog^2n)
void construct_sa2(string s, int *sa) {
  n = s.size();
  REP(i, n+1) sa[i] = i, ran2[i] = i<n ? s[i] : -1;

  for(k2 = 1; k2 <= n; k2*=2) {
    sort(sa, sa+n+1, compare_sa2);

    tmp2[sa[0]] = 0;
    FOR(i, 1, n+1) {
      tmp2[sa[i]] = tmp2[sa[i-1]] + (compare_sa2(sa[i-1], sa[i]) ? 1 : 0);
    }
    REP(i, n+1) {
      ran2[i] = tmp2[i];
    }
  }
}

// O(n)
void construct_lcp2(string s, int *sa, int *lcp) {
  n = s.size();
  REP(i, n+1) ran2[sa[i]] = i;

  int h = 0;
  lcp[0] = 0;
  REP(i, n) {
    int j = sa[ran2[i] - 1];
    if(h > 0) h--;
    for(; j+h<n && i+h<n; ++h) {
      if(s[j+h] != s[i+h]) break;
    }

    lcp[ran2[i]-1] = h;
  }
}

// 文字列S,T 接尾辞配列sa O(|T|log|S|) で文字列検索をする
bool contain(string s, string t, int *sa) {
  int a = 0, b = s.length();
  while(b-a > 1) {
    int c = (a+b)/2;
    if(s.compare(sa[c], t.length(), t) < 0) a = c;
    else b = c;
  }
  return s.compare(sa[b], t.length(), t) == 0;
}

template<class T>
class segmentTree {
public:
  int size_;
  vector<T> dat;
  T init__ = INT_MAX; // 単位元

  segmentTree() {}
  segmentTree(int n) {
    for(size_ = 1; size_ < n; size_ *= 2);
    dat.assign(2*size_-1, init__);
  }

  T calc(T d1, T d2) {
    return min(d1, d2);     // minnimum
    // return max(d1, d2);  // maximum
    // return d1+d2;        // sum
  }
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return init__;
    if(a <= l && r <= b) return dat[k];
    return calc(query(a, b, 2*k+1, l, (l+r)/2),
                query(a, b, 2*k+2, (l+r)/2, r));
  }
  T query(int a, int b) {return query(a, b, 0, 0, size_);}
  void update(int k, T a) {
    k += size_ - 1;
    dat[k] = a;      // max or min
    // dat[k] += a;  // sum
    while(k > 0) {
      k = (k-1) / 2;
      dat[k] = calc(dat[k*2+1], dat[k*2+2]);
    }
  }
};

int sa1[200010], lcp1[200010];
int sa2[200010], lcp2[200010];
signed main(void)
{
  string s;
  cin >> s;

  segmentTree<int> seg1(s.size());
  construct_sa1(s, sa1); construct_lcp1(s, sa1, lcp1);
  REP(i, n) seg1.update(i, lcp1[i]);

  string s2 = s;
  reverse(ALL(s2));
  segmentTree<int> seg2(s2.size());
  construct_sa2(s2, sa2); construct_lcp2(s2, sa2, lcp2);
  REP(i, n) seg2.update(i, lcp2[i]);

  ll ret = 0;
  FOR(i, 1, n) {
    if(i <= n-i) continue;
    int l = ran1[0], r = ran1[i];
    if(l > r) swap(l, r);
    int a = min(n-i-1, (ll)seg1.query(l, r));

    l = ran2[n-i], r = ran2[0];
    if(l > r) swap(l, r);
    int c = min(n-i-1, (ll)seg2.query(l, r));

    if(a>0 && c>0 && a+c >= n-i) ret += min(n-i-1, a+c-(n-i)+1);
  }
  cout << ret << endl;

  return 0;
}

z-algorithm

文字列SとS[i,|S|-1]の共通先頭文字数をO(|S|)で求めるという問題そのまんまなアルゴリズム。 snuke.hatenablog.com

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;

#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()

// z-algotirhm O(|S|)
VI Zalgo(string s) {
  VI v(s.size());
  v[0] = s.size();
  int i = 1, j = 0;
  while (i < s.size()) {
    while (i+j < s.size() && s[j] == s[i+j]) ++j;
    v[i] = j;
    if (j == 0) { ++i; continue;}
    int k = 1;
    while (i+k < s.size() && k+v[k] < j) v[i+k] = v[k], ++k;
    i += k; j -= k;
  }
    return v;
}

signed main(void)
{
  string s;
  cin >> s;
  int n = s.size();

  VI v1 = Zalgo(s);

  string s2 = s;
  reverse(ALL(s2));
  VI v2 = Zalgo(s2);

  ll ret = 0;
  FOR(i, 1, n) {
    if(i <= n-i) continue;
    int a = min(n-i-1, v1[i]);
    int c = min(n-i-1, v2[n-i]);

    if(a>0 && c>0 && a+c >= n-i) ret += min(n-i-1, a+c-(n-i)+1);
  }
  cout << ret << endl;

  return 0;
}

ローリングハッシュ

ローリングハッシュを使うとある2つの文字列が一致しているかどうかの判定はO(1)でできる。文字列xとyの先頭d文字が共通かどうかという判定問題に置き換えdを最大化すればaが求まる。この判定はO(1)ででき、単調性があるので二分探索が可能なのでO(log|S|)でaとcをそれぞれ求めることができる。合計でO(|S|log|S|)で解ける。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#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()

// rolling-hash
class rollingHash {
public:
  static const int MAX_N = 200010;
  // MOD と 基数
  ll mo[2] = {1000000007, 1000000009};
  ll base[2] = {1009, 1007};
  ll hash[2][MAX_N], power[2][MAX_N];

  rollingHash() {}
  rollingHash(string s) { init(s); }

  // O(|S|)
  void init(string s) {
    REP(i, 2) {
      power[i][0] = 1;
      FOR(j, 1, MAX_N) power[i][j] = power[i][j-1]*base[i]%mo[i];
    }
    REP(i, 2) REP(j, s.size()) {
      hash[i][j+1] = (hash[i][j]+power[i][j]*(s[j]-'a'))%mo[i];
    }
  }

  // [l1, r1) と [l2, r2) が一致するかの判定 (l1 < l2)
  bool equal(int l1, int r1, int l2, int r2) {
    REP(i, 2) {
      ll a = (((hash[i][r1]-hash[i][l1])%mo[i])+mo[i])%mo[i];
      ll b = (((hash[i][r2]-hash[i][l2])%mo[i])+mo[i])%mo[i];
      if(a*power[i][l2-l1]%mo[i] == b) return true;
    }
    return false;
  }
};

signed main(void)
{
  string s, s2;
  cin >> s;

  int n = s.size();
  s2 = s;
  reverse(ALL(s2));
  rollingHash hs1(s), hs2(s2);

  ll ret = 0;
  FOR(i, 1, n) {
    if(i <= n-i) continue;

    int lb = 0, ub = n-i;
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(hs1.equal(0, mid, i, i+mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    int a = lb;

    lb = 0, ub = n-i;
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(hs1.equal(i-mid, i, n-mid, n)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    int c = lb;

    if(a>0 && c>0 && a+c >= n-i) ret += min(n-i-1, a+c-(n-i)+1);
  }
  cout << ret << endl;

  return 0;
}

ARC056 C - 部門分け

問題ページ
C - 部門分け

考えたこと

• O(N!)すれば部分点40点ははい
• 部門数とか何か条件を決め打てばスコアが一意に定まるみたいなのを考える
• 部門数M = N からはじめてもっともスコアが上がる方法で M = N-1 につなぐ貪欲→明らかにだめなパターンが存在
• すでに同じ部門になってる社員のbitを1にしてbitDP→部門複数あるしbitで扱えなくない？
• すでにつないだやつをうまいこともって頑張れない？→O(N^N)にしかならないが
  -----解説を見た-----
• dp[S] = (頂点集合Sの解) としてDPをする
• 部分集合の部分集合はO(3^N)のため解ける

学び

• dp[S] = (頂点集合Sについて) みたいなDPの条件の取り方
• Sの部分集合Tのdp[T]から全列挙して遷移するようなのはO(3^N)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

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

int n, K;
int w[20][20];
int dp[1LL<<17], dp2[1LL<<17];

signed main(void)
{
  cin >> n >> K;
  REP(i, n) REP(j, n) cin >> w[i][j];
  // dp2[S] = (頂点集合Sの辺の重みの和)
  REP(i, 1<<n) {
    REP(j, n) FOR(k, j+1, n) {
      if((i&1<<j) && (i&1<<k)) {
        dp2[i] += w[j][k];
      }
    }
  }

  FOR(s, 1, 1<<n) {
    // 集合sの部分集合tを全列挙
    int t = s;
    do {
      // 差集合はs-tで求まる
      chmax(dp[s], dp[s-t] + K - (dp2[s] - dp2[s-t] - dp2[t]));
      t = (t-1) & s;
    } while(t != 0);
  }
  cout << dp[(1<<n)-1] << endl;

  return 0;
}

ABC084 D - 2017-like Number

問題ページ
D - 2017-like Number

考えたこと

• f(A) = (1からAのうち条件を満たす数) とすれば f(r) - f(l-1) として計算できるのでf(A)を前計算する
• 10^5までの素数をエラトステネスの篩で列挙して、条件を満たす数を1~10^5までで探せばよさそう
• 条件を満たす数が何かわかったので累積和でf(A)を計算する
• 各クエリをO(1)で求める

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int 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
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

//素数ならtrue
bool prime[1000000];
int dp[100010];

signed main(void)
{
  int q;
  cin >> q;

  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = false;
  for (int i = 2; i * i <= 1000000; i++) {
    if (prime[i]) {
      for (int j = 2 * i; j <= 1000000; j += i) {
        prime[j] = false;
      }
    }
  }

  FOR(i, 1, 100010) {
    if(i%2 && prime[i] && prime[(i+1)/2]) {
      dp[i] = 1;
    }
  }

  FOR(i, 1, 100010) dp[i] += dp[i-1];

  REP(i, q) {
    int l, r;
    cin >> l >> r;
    cout << dp[r] - dp[l-1] << endl;
  }

  return 0;
}