University CodeSprint 5 - ei1333の日記

25th. 今回はやさしめだったっぽい.

Exceeding the Speed Limit

www.hackerrank.com

問題概要

びーとあいず

解法

たぷりす

ソース

#include <bits/stdc++.h>

using namespace std;

int main() {
  int s;
  cin >> s;
  if(s <= 90) cout << "0 No punishment\n";
  else if(s <= 110) cout << (s - 90) * 300 << " Warning\n";
  else cout << (s - 90) * 500 << " License removed\n";
}

Array Triplets

www.hackerrank.com

問題概要

長さ ${N(1 \le N \le 17)}$ の数列 ${a_i(|a_i| \le 10^9)}$ が与えられる.

和が等しい3つの空ではない部分集合に分割する方法の個数を求めよ.

解法

${O(3^N)}$ が間に合うためおわりです.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int64 N, A[17];

int64 rec(int64 X, int64 Y, int64 Z, int idx, int bit) {
  if(idx == N) return X == 0 && Y == 0 && Z == 0 && bit == 7;
  return rec(X - A[idx], Y, Z, idx + 1, bit | 1) +
         rec(X, Y - A[idx], Z, idx + 1, bit | 2) +
         rec(X, Y, Z - A[idx], idx + 1, bit | 4);
}

int main() {
  cin >> N;
  int64 add = 0;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    add += A[i];
  }
  if(add % 3 != 0) {
    cout << 0 << endl;
    return 0;
  }
  add /= 3;
  cout << rec(add, add, add, 0, 0) << endl;
}

a,b Special Points

www.hackerrank.com

問題概要

${n(1 \le n \le 3 \times 10^5)}$ 頂点 ${m(1 \le m \le min(\frac {n(n-1)} {2}, 3 \times 10^5)}$ 辺の単純無向グラフと整数 ${a, b(1 \le a, b \le 10^9)}$ が与えられる. ある頂点 ${v}$ について, 同じ連結成分内に ${a \times adj(u) \lt adj(v) \lt b \times adj(u')}$ となる頂点 ${u, u'}$ が存在するとき, その頂点を a, b Special Point と呼ぶ.

a, b Special Point の個数を求めよ.

解法

Union-Findをつかったりしながらやります.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct UnionFind {
  vector< int > data;

  UnionFind(int sz) {
    data.assign(sz, -1);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k) {
    return (-data[find(k)]);
  }
};


int main() {
  int N, M, A, B;
  cin >> N >> M >> A >> B;
  vector< int > g[300000];
  UnionFind uf(N);
  for(int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
    uf.unite(x, y);
  }
  vector< int > latte(N, M), malta(N);
  for(int i = 0; i < N; i++) {
    latte[uf.find(i)] = min(latte[uf.find(i)], (int) g[i].size());
    malta[uf.find(i)] = max(malta[uf.find(i)], (int) g[i].size());
  }
  int ret = 0;
  for(int i = 0; i < N; i++) {
    ret += 1LL * A * latte[uf.find(i)] < g[i].size() && g[i].size() < 1LL * B * malta[uf.find(i)];
  }
  cout << ret << endl;
}

Limit XOR

www.hackerrank.com

問題概要

長さ ${n(1 \le n \le 10^5)}$ の数列 ${a_i(1 \le a_i \le 10^9)}$ が与えられる.

xor が ${K(1 \le K \le 10^9)}$ 未満となる連続部分列の個数を求めよ.

解法

Trie を貼る. 各ノードにはそのノードに以下にある値の個数を持つ.

左の要素を追加していって, それぞれの要素の追加時にその要素を右端としたときに xor が ${K}$ 未満となる個数を計算できれば良くて, これは Trie をくだれば ${O(\log K)}$ でできる.

ソース

ライブラリマスターなので, ライブラリを貼るだけをすることができる.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

template< typename T >
struct BinaryTrieNode {
  int nxt[2];
  T lazy;
  int exist; 
  vector< int > accept;

  BinaryTrieNode() : exist(0) {
    nxt[0] = nxt[1] = -1;
  }
};

template< typename T, int MAX_LOG >
struct BinaryTrie {

  using Node = BinaryTrieNode< T >;
  vector< Node > nodes;
  int root;

  BinaryTrie() : root(0) {
    nodes.push_back(Node());
  }

  void update_direct(int node, int id) {
    ++nodes[node].exist; //notice!!
    nodes[node].accept.push_back(id);
  }

  void update_child(int node, int child, int id) {
    ++nodes[node].exist;
  }

  void add(const T &bit, int bit_index, int node_index, int id) {
    propagate(bit_index, node_index);
    if(bit_index == -1) {
      update_direct(node_index, id);
    } else {
      const int c = (bit >> bit_index) & 1;
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = (int) nodes.size();
        nodes.push_back(Node());
      }
      add(bit, bit_index - 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }

  void add(const T &bit, int id) {
    add(bit, MAX_LOG, 0, id);
  }

  void add(const T &bit) {
    add(bit, nodes[0].exist);
  }

  T query(int bit_index, int node_index, T K) {
    if(bit_index == -1 || node_index == -1) {
      return nodes[node_index].exist;
    } else {
      propagate(bit_index, node_index);
      T sum = 0;
      if((K >> bit_index) & 1) {
        if(~nodes[node_index].nxt[0]) sum += nodes[nodes[node_index].nxt[0]].exist;
        if(~nodes[node_index].nxt[1]) sum += query(bit_index - 1, nodes[node_index].nxt[1], K);
        return sum;
      } else {
        if(~nodes[node_index].nxt[0]) sum += query(bit_index - 1, nodes[node_index].nxt[0], K);
        return sum;
      }
    }
  }

  T query(int K) {
    return query(MAX_LOG, 0, K);
  }

  int size() const {
    return (nodes[0].exist);
  }

  int nodesize() const {
    return ((int) nodes.size());
  }

  void xorpush(const T &bit) {
    nodes[0].lazy ^= bit;
  }

  void propagate(int bit_index, int node_index) {
    const int c = (nodes[node_index].lazy >> bit_index) & 1;
    if(c) swap(nodes[node_index].nxt[0], nodes[node_index].nxt[1]);
    if(~nodes[node_index].nxt[0]) nodes[nodes[node_index].nxt[0]].lazy ^= nodes[node_index].lazy;
    if(~nodes[node_index].nxt[1]) nodes[nodes[node_index].nxt[1]].lazy ^= nodes[node_index].lazy;
    nodes[node_index].lazy = 0;
  }
};


int main() {
  int N, K, A[100000];
  cin >> N >> K;
  --K;
  for(int i = 0; i < N; i++) cin >> A[i];
  BinaryTrie< int, 30 > trie;
  trie.add(0);
  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    trie.xorpush(A[i]);
    ret += trie.query(K);
    trie.add(0);
  }
  cout << ret << endl;
}

Cube-loving Numbers

www.hackerrank.com

問題概要

${N(1 \le N \le 10^{18})}$ 以下の自然数のうち ${a^3 \times b(a \gt 1, b \ge 1)}$ とかけるものは何個あるか.

解法

まあこういうのはぐぐればでてくるため（完）.

メビウス関数を使えば良いことがわかるので使います.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 MAX_N = 1000000000000000000LL;
const int64 SQ_N = 1000000;

int p[SQ_N + 1], f[SQ_N + 1];

int main() {
  for(int i = 0; i <= SQ_N; i++) {
    p[i] = 1, f[i] = 1;
  }
  for(int i = 2; i <= SQ_N; i++) {
    if(p[i]) {
      f[i] = -1;
      for(int j = i + i; j <= SQ_N; j += i) {
        p[j] = 0;
        f[j] *= (j % (i * i) == 0) ? 0 : -1;
      }
    }
  }
  int T;
  cin >> T;
  while(T--) {
    int64 X;
    cin >> X;
    int64 sum = 0;
    for(int64 i = 1; i * i * i <= X; i++) sum += f[i] * X / (i * i * i);
    cout << X - sum << endl;
  }
}

Interesting Trip

www.hackerrank.com

問題概要

${n(1 \le n \le 2 \times 10^5)}$ 頂点 ${m(1 \le m \le 3 \times 10^5)}$ 有向辺のDAGが与えられる. それぞれの頂点にはあるアルファベット ${1}$ 文字が書かれている.

ある頂点 ${X}$ から ${Y}$ の経路について, 通った頂点の順番に文字を並べて文字列をつくる. このとき生成可能な辞書順最小文字列を求めよ.

解法

実　家　の　よ　う　な　安　心　感

とりあえずトポロジカルソートしておく.

愚直解法としては dp[i]:= 頂点 ${i}$ 以降に生成可能な辞書順最小の文字列として, 頂点 ${Y}$ に近いほうからこれを埋めていく解法が考えられる. 遷移としては dp[i] = ${S_i}$ + (頂点 ${i}$ から移動できるすべての頂点の dp[k] のうち最小のもの) となる. しかしこれだと計算量は ${O(N^2)}$ となって破滅する.

方針としてこのDPを高速化する解法が考えられる. 各頂点について辞書順最小の文字列を陽に持つとメモリが破滅するので, dp[i]:= 頂点 ${i}$ から移動できるすべての頂点のうち, 辞書順最小となるような頂点とする. これは頂点 ${i}$ から辞書順最小の頂点に辺を張る操作とみることができる. こうすることで最後に頂点 ${X}$ から頂点 ${Y}$ に dp 配列を用いて 1 文字ずつたどることで解を求めることが出来る.

辺を張る頂点を高速に求めたい. 今回は文字列比較の高速化をしたいのでローリングハッシュを使う方針をとることにする. ローリングハッシュを用いた文字列の大小比較は, ハッシュ値が一致する最長接頭辞 LCP を二分探索で求めて, LCP+1 番目の文字をみることで比較可能である.

したがって結局は, ある頂点から任意個辺を辿った先の頂点の文字とその頂点までのハッシュ値を求める問題に帰着される. これはダブリングをすることで求めることが出来る.

計算量は ${O(m \log^2 n)}$ .

ソース

うくちゃん.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int base = 29;
const int mod = 1e9 + 9;

vector< int > g[200000], f[200000], ord;
bool v[200000];
bool can_use[200000];
int dp[20][200001];
int sz[20][200001];
int64 hashed[20][200001];


int N, M, X, Y;
string S;

void dfs(int idx) {
  if(v[idx]) return;
  v[idx] = true;
  for(auto &to : g[idx]) dfs(to);
  ord.push_back(idx);
}

int main() {

  int64 power[202020];
  power[0] = 1;
  for(int i = 1; i < 202020; i++) {
    power[i] = power[i - 1] * base % mod;
  }

  cin >> N >> M;
  cin >> S;
  for(int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].push_back(y);
  }
  cin >> X >> Y;
  --X, --Y;
  g[Y].clear();
  dfs(X);

  if(!v[Y]) {
    cout << "No way" << endl;
    return 0;
  }

  memset(dp, -1, sizeof(dp));

  auto update = [&](int idx, int nxt) {
    can_use[idx] = true;
    dp[0][idx] = nxt;
    sz[0][idx] = 1;
    hashed[0][idx] = S[idx] - 'a';
    for(int i = 1; i < 20; i++) {
      if(dp[i - 1][idx] == -1) {
        hashed[i][idx] = hashed[i - 1][idx];
        sz[i][idx] = sz[i - 1][idx];
      } else {
        hashed[i][idx] = (hashed[i - 1][idx] + hashed[i - 1][dp[i - 1][idx]] * power[sz[i - 1][idx]] % mod) % mod;
        sz[i][idx] = sz[i - 1][dp[i - 1][idx]] + sz[i - 1][idx];
        dp[i][idx] = dp[i - 1][dp[i - 1][idx]];
      }
    }
  };
  update(X, -1);

  auto get_hashed = [&](int idx, int sz2) {
    int64 beet = 0, preadd = 0, beet2 = 0;
    for(int i = 19; i >= 0; i--) {
      if((sz2 >> i) & 1) {
        beet = (beet + hashed[i][idx] * power[preadd] % mod) % mod;
        preadd += sz[i][idx];
        idx = dp[i][idx];
      }
    }
    return beet;
  };

  auto compare = [&](int latte, int malta) {
    int64 lattesz = sz[19][latte], lattehashed = hashed[19][latte];
    int64 maltasz = sz[19][malta], maltahashed = hashed[19][malta];
    int64 low = 0, high = min(lattesz, maltasz) + 1;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      auto p = get_hashed(latte, mid);
      auto q = get_hashed(malta, mid);
      if(p == q) low = mid;
      else high = mid;
    }
    if(lattesz == low) return false;
    if(maltasz == low) return true;
    for(int i = 19; i >= 0; i--) if((low >> i) & 1) latte = dp[i][latte];
    for(int i = 19; i >= 0; i--) if((low >> i) & 1) malta = dp[i][malta];
    return S[latte] > S[malta];
  };

  update(Y, 200000);

  for(int i : ord) {
    vector< int > child;
    for(auto &to : g[i]) if(can_use[to]) child.emplace_back(to);
    if(child.empty()) continue;
    for(int j = 1; j < child.size(); j++) if(compare(child[0], child[j])) swap(child[0], child[j]);
    update(i, child[0]);
  }

  string ans;
  ans.push_back(S[X]);
  while(dp[0][X] != 200000) {
    ans.push_back(S[dp[0][X]]);
    X = dp[0][X];
  }
  cout << ans << endl;
}

Sword profit

www.hackerrank.com

問題

直線上に ${n(1 \le n \le 3 \times 10^5)}$ 個の店が順番に並んでいる.

${i}$ 番目の店では, クオリティ ${q_i(1 \le q_i \le 10^{12})}$ の剣が無限個売られている. 剣の値段は, その店で剣を買う個数によって変化する. 具体的には ${k}$ 個購入したとき ${k}$ 番目の剣の値段は ${a_i + k \times b_i(1 \le a_i, b_i \le 10^9)}$ ドルとなる. また隣接する店に移動するごとに, 持っている剣のクオリティはそれぞれ ${d_i(1 \le d_i \le 10^5)}$ 下がる.

また ${i}$ 番目の店では, 持っている剣を売ることもできる. 具体的にはクオリティ ${q}$ の剣を ${1}$ 個売るごとに ${q - r_i(1 \le r_i \le 10^9)}$ ドルを得る.

これから ${1}$ 番目の店から ${n}$ 番目の店まで順番に移動する. 後戻りはできない. 最大利益を ${10^9+7}$ で割った余りで求めよ.

解法

実　家　の　よ　う　な　安　心　感　２

それぞれの店で購入した剣をどうするかは独立に計算できるので, そうすることにする.

ある店 ${i}$ で剣を購入するとする. ${x}$ 個購入してする費用は等差数列の和の公式を使うと次の通りになる.

${\frac {n} {2} \times (2 \times (a_{i}+b_{i})+(x-1) \times b_{i}) }$

またこの剣を頂点 ${j(\ge i)}$ で売却するときの利益は次の通りになる.

${q_{i} - (j-i) \times d_i - r_j = q_{i} - j \times d_i + i \times d_i - r_j}$

利益を最大化するためには, ${j \times d_i + r_j}$ が最小となるような ${j}$ をみつければよい. これは明らかに ConvexHullTrick を使うことで求めることができるので, つかって求める.

あとは利益が最大となる ${x}$ を決める必要があるが, 購入費用と利益の式は ${x}$ に関する ${2}$ 次関数なので極大値的なことをすればもとまる(三分探索してもよい).

ソース

がんばって作問した感があふれてる. int128って便利だね.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

const int mod = 1e9 + 7;

template< class T >
struct ConvexHullTrickAddQueryMonotone {
  deque< pair< T, T > > L;
  int isdec;

  ConvexHullTrickAddQueryMonotone() : isdec(-1) {}

  inline T getX(const pair< T, T > &a, const T &x) {
    return (a.first * x + a.second);
  }

  inline bool check(const pair< T, T > &a, const pair< T, T > &b, const pair< T, T > &c) {
    return ((b.first - a.first) * (c.second - b.second) >= (b.second - a.second) * (c.first - b.first));
  }

  inline bool empty() { return (L.empty()); }

  void add(T a, T b) {
    pair< T, T > line(a, b);

    if(isdec == -1 && !L.empty()) {
      if(a < L[0].first) isdec = 1;
      else if(a > L[0].first) isdec = 0;
    }

    if(isdec == 1) {
      if(!L.empty() && L.back().first == a) {
        line.second = min(line.second, L.back().second);
        L.pop_back();
      }
      while(L.size() >= 2 && check(L[L.size() - 2], L.back(), line)) L.pop_back();
      L.emplace_back(line);
    } else {
      if(!L.empty() && L.front().first == a) {
        line.second = min(line.second, L.front().second);
        L.pop_front();
      }
      while(L.size() >= 2 && check(line, L[0], L[1])) L.pop_front();
      L.emplace_front(line);
    }
  }

  T getMinimumQuery(T x) {
    int low = -1, high = (int) L.size() - 1;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if((getX(L[mid], x) >= getX(L[mid + 1], x))) low = mid;
      else high = mid;
    }
    return (getX(L[high], x));
  }

  T getMinimumQueryMonotone(T x) {
    while(L.size() >= 2 && getX(L[0], x) >= getX(L[1], x)) {
      L.pop_front();
    }
    return (getX(L[0], x));
  }
};


int main() {
  int N, a[300000], b[300000], r[300000], d[300000];
  int64 q[300000];
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%lld %d %d %d %d", &q[i], &a[i], &b[i], &r[i], &d[i]);
  }

  ConvexHullTrickAddQueryMonotone< int64 > lattemalta;
  vector< int64 > beet(N);
  for(int i = N - 1; i >= 0; i--) {
    lattemalta.add(i, r[i]);
    beet[i] = lattemalta.getMinimumQuery(d[i]);
  }

  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    int64 get = max(0LL, q[i] + 1LL * i * d[i] - beet[i]);
    auto F = [&](int64 x) {
      __int128 val = (2 * get - ((__int128) 2 * (a[i] + b[i]) + (__int128) x * b[i] - b[i])) * x / 2;
      return val;
    };
    (ret += F(max(0LL, (get - a[i]) / b[i])) % mod) %= mod;
  }
  cout << ret << endl;
}