University CodeSprint 2 - ei1333の日記

${94}$ 位. $75 で何買おう.

Breaking the Records

解法

寝ながら書く.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int n, cod;
  cin >> n;
  cin >> cod;

  int a = 0, b = 0;
  int s = cod, t = cod;
  for(int i = 1; i < n; i++) {
    int p;
    cin >> p;
    if(s < p) {
      s = p;
      ++a;
    }
    if(t > p) {
      t = p;
      ++b;
    }
  }
  cout << a << " " << b << endl;
}

Separate the Numbers

解法

${S}$ の部分文字列が連結される数値の一部なのでそれを総当り.

寝ながら書いたら謎(謎ではない)のWAをしたので起きた. なんか連続だけど, 最後で途中で切れているやつもOKみたいにしてた(伝わって).

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int q;
  cin >> q;
  while(q--) {
    string S;
    cin >> S;

    for(int i = 1; i <= S.size() / 2; i++) {
      int64 t = stoll(S.substr(0, i));
      string q;
      if(t == 0) break;
      for(int x = 0; x < 35; x++) {
        q += to_string(t + x);
        if(q == S) {
          cout << "YES" << " " << t << endl;
          goto foo;
        }
      }
    }
    cout << "NO" << endl;
    foo:;
  }

}

Game of Two Stacks

www.hackerrank.com

問題概要

スタック ${A = \{a_0, a_1, \dots, a_{n-1}\}}$ と ${B = \{b_0, b_1, \dots, b_{m-1}\}}$ がある.

両方のスタックの上から, 取り除いた要素の合計が ${x}$ を超えない範囲で上から取り除く.

取り除ける要素の個数の最大値を求めよ.

解法

こういうのは一方を固定すると大体上手くいく.

一方のスタックで取り除く範囲は総当りするとして, もう一方は二分探索でえいってできる( ${x-hoge}$ 以下の最大の値をもつ要素位置を求める問題になる).

${O(n \log m)}$

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 g, n, m, x, a[100001] = {}, b[100001] = {};

  cin >> g;
  while(g--) {
    cin >> n >> m >> x;
    ++n, ++m;
    for(int i = 1; i < n; i++) {
      cin >> a[i];
      a[i] += a[i - 1];
    }
    for(int i = 1; i < m; i++) {
      cin >> b[i];
      b[i] += b[i - 1];
    }

    int ret = 0;
    for(int i = 0; i < n; i++) {
      if(a[i] > x) break;
      int qs = upper_bound(b, b + m, x - a[i]) - b - 1;
      ret = max(ret, i + qs);
    }

    cout << ret << endl;
  }

}

The Story of a Tree

問題概要

${n(1 \le n \le 10^5)}$ 頂点の木が与えられる.

木の根はランダムに選択される.

また, ${g}$ 個の「頂点 ${v}$ の親は ${u}$ である」という推測の情報が与えられる. この情報のうち ${k}$ 個以上当たっていれば勝ちである.

このとき勝ちとなる確率を分数で求めよ.

解法

根となる候補は ${n}$ 個なので, ${n}$ 個の頂点すべてを根としたとき勝ちかどうかを試せば良い.

普通にやると ${O(n^2)}$ なので †全方位木DP†(これすき) をして ${O(n)}$ にする.

ある頂点から別の頂点に移動するとき, 正解の個数が変化するのはそれを結ぶ辺のみなので簡単（？）に求まる.

ソース

#include<bits/stdc++.h>

using namespace std;


int Q, N, G, K;
vector< int > g[100000];
set< pair< int, int > > s;
int isok[100000];

void dfs(int idx, int par = -1)
{
  for(auto &to : g[idx]) {
    if(to == par) continue;
    dfs(to, idx);
    isok[idx] += isok[to] + s.count({to, idx});
  }
}

int rec(int idx, int parsum, int par = -1)
{
  parsum += isok[idx];
  int ret = parsum >= K;
  for(auto &to : g[idx]) {
    if(to == par) continue;
    ret += rec(to, parsum - isok[to] - s.count({to, idx}) + s.count({idx, to}), idx);
  }
  return (ret);
}

int main()
{
  cin >> Q;
  while(Q--) {

    for(int i = 0; i < N; i++) g[i].clear();
    s.clear();
    memset(isok, 0, sizeof(isok));

    cin >> N;
    for(int i = 0; i < N - 1; i++) {
      int a, b;
      cin >> a >> b;
      --a, --b;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    cin >> G >> K;
    while(G--) {
      int a, b;
      cin >> a >> b;
      --a, --b;
      s.emplace(b, a);
    }

    dfs(0);
    int sum = rec(0, 0);
    int gcd = __gcd(N, sum);
    cout << sum / gcd << "/" << N / gcd << endl;
  }

}

Sherlock’s Array Merging Algorithm

問題概要

いくつかの配列 ${V_i}$ を入力すると, 擬似コード(問題参照) を通して ${1}$ つの配列 ${M}$ が生成される.

今この配列 ${M}$ が分かっている. もとの ${V_i}$ として考えられる組み合わせの個数を ${10^9 + 7}$ で割った余りで求めよ.

解法

† ${O(n^3/12)}$ †(は？.

ぐっと睨んで擬似コードが意味することを整理してみる.

もとの配列の個数が ${k}$ 個だったとする.
全ての配列 ${V_i}$ から ${1}$ 番目の要素を取り出して, それら ${k}$ 個の値をソートして ${M}$ に追加する.
空でない全ての配列 ${V_i}$ から ${2}$ 番目の要素を取り出して, それら ${s(\le k)}$ 個( ${k}$ 個より大きいとすると, ${1}$ 回目の操作も ${k}$ より大きくなるので) の値をソートして ${M}$ に追加する.
これを全ての配列が空になるまで繰り返す.

すると, 取り出す個数は単調減少で, ${1}$ 回で取り出す区間は単調増加ということがわかる.

任意の区間がソートされているか知りたい気持ちになるが, これは愚直にやると ${O(n^2)}$ でできる.

ここまで分かれば, あとは状態に「取り出す個数」と「配列 ${M}$ 上での現在の位置」を持って頑張ってDPすれば求めることができる.

ソース

なんかよくみたら ${O(n^3)}$ だったんだけど, はやいみたい.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

const int mod = 1e9 + 7;

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}

int N, M[1202];
bool sorted[1202][1202];
int dp[1201][1201];
int64 fact[1300], rfact[1300];

int rec(int idx, int sz)
{
  if(idx == N) return (1);
  if(~dp[idx][sz]) return (dp[idx][sz]);
  int64 ret = 0;
  for(int j = idx; j < N; j++) {
    const int nsz = j - idx + 1;
    if(nsz > sz) break;
    if(sorted[idx][j]) {
      int64 qual = fact[sz] * rfact[sz - nsz] % mod;
      ret += qual * rec(j + 1, nsz) % mod;
      ret %= mod;
    }
  }
  return (dp[idx][sz] = ret);
}

int main()
{

  fact[0] = rfact[0] = 1;
  for(int i = 1; i < 1300; i++) {
    fact[i] = fact[i - 1] * i % mod;
    rfact[i] = modInv(fact[i]);
  }

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> M[i];
  }

  for(int i = 0; i < N; i++) {
    sorted[i][i] = true;
    for(int j = i + 1; j < N; j++) {
      if(M[j - 1] > M[j]) break;
      sorted[i][j] = true;
    }
  }

  memset(dp, -1, sizeof(dp));
  int ret = 0;

  for(int i = 0; i < N; i++) {
    if(sorted[0][i]) {
      ret += rec(i + 1, i + 1);
      ret %= mod;
    }
  }
  cout << ret << endl;
}

ここからは全部部分点….

Querying Sums on Strings

問題概要

${f(s, w, l, r)}$ を, 文字列 ${w}$ の区間 ${[l, r]}$ の部分文字列をとってきたとき, これが ${s}$ の中で現れた個数と定義する.

文字列 ${s(1 \le |s| \le 10^5)}$ と ${m(1 \le m \le 10^5)}$ 個のペア ${l_i, r_i}$ , ${\sum_{ i = a_i }^{ b_i } f(s, w_j, l_i, r_i)}$ を求める ${q(1 \le q \le 10^5)}$ 個のクエリ ( ${w_j, a_j, b_j}$ ) ( ${|w_j|}$ の和は ${10^5}$ 以下) が与えれられるので全て求めよ.

解法

全ての制約が ${10^5}$ で怖いが ${|w_j|}$ の和は ${10^5}$ 以下なので, ${k, q}$ の大小で解法を変えると上手くいく. いく？いかなかった( ${47.5}$ 点).

${k \lt q}$ のときは ${O(mk^2)}$ で解く. ${k \ge q}$ のときは ${O(mq \log hoge)}$ で解けてほしい(log を消さないとダメ？).

どちらも Suffix Array と何かを組み合わせてごにょると解けるのは確か.

SA勉強しないとなぁ.

ソース

#include<bits/stdc++.h>

using namespace std;

struct SuffixArray
{
  vector< int > SA;
  string s;

  void Build_SA(const string &str)
  {
    s = str;
    SA.resize(s.size());
    iota(begin(SA), end(SA), 0);
    sort(begin(SA), end(SA), [&](const int &a, const int &b)
    {
      if(s[a] == s[b]) return (a > b);
      return (s[a] < s[b]);
    });
    vector< int > classes(s.size()), c(s.size()), cnt(s.size());
    for(int i = 0; i < s.size(); i++) {
      c[i] = s[i];
    }
    for(int len = 1; len < s.size(); len <<= 1) {
      for(int i = 0; i < s.size(); i++) {
        if(i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) {
          classes[SA[i]] = classes[SA[i - 1]];
        } else {
          classes[SA[i]] = i;
        }
      }
      iota(begin(cnt), end(cnt), 0);
      copy(begin(SA), end(SA), begin(c));
      for(int i = 0; i < s.size(); i++) {
        int s1 = c[i] - len;
        if(s1 >= 0) SA[cnt[classes[s1]]++] = s1;
      }
      classes.swap(c);
    }
  }

  int operator[](int k) const
  {
    return (SA[k]);
  }

  int size() const
  {
    return (s.size());
  }

  bool lt_substr(char *t, int len, int si = 0, int ti = 0)
  {
    int sn = s.size(), tn = len;
    while(si < sn && ti < tn) {
      if(s[si] < t[ti]) return (true);
      if(s[si] > t[ti]) return (false);
      ++si, ++ti;
    }
    return (si >= sn && ti < tn);
  }

  int lower_bound(char *t, int len)
  {
    int low = -1, high = SA.size();
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, len, SA[mid])) low = mid;
      else high = mid;
    }
    return (high);
  }

  pair< int, int > lower_upper_bound(char *t, int len)
  {
    int idx = lower_bound(t, len);
    int low = idx - 1, high = SA.size();
    t[len - 1]++;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, len, SA[mid])) low = mid;
      else high = mid;
    }
    t[len - 1]--;
    return (make_pair(idx, high));
  }
};

struct LongestCommonPrefixArray
{
  vector< int > LCP, rank;

  LongestCommonPrefixArray(SuffixArray &SA)
  {
    Build_LCP(SA);
  }

  void Build_LCP(SuffixArray &SA)
  {
    string &s = SA.s;
    rank.resize(s.size());
    for(int i = 0; i < s.size(); i++) {
      rank[SA[i]] = i;
    }
    LCP.resize(s.size() - 1);
    for(int i = 0, h = 0; i < s.size(); i++) {
      if(rank[i] + 1 < s.size()) {
        for(int j = SA[rank[i] + 1]; max(i, j) + h < s.length() && s[i + h] == s[j + h]; ++h);
        LCP[rank[i]] = h;
        if(h > 0) --h;
      }
    }
  }

  int operator[](int k) const
  {
    if(k < 0) return (0);
    return (LCP[k]);
  }

  int size() const
  {
    return (LCP.size() + 1);
  }
};

const int INF = 1 << 30;

template< class T >
struct RMQ
{
  vector< vector< T > > dat;

  template< class S >
  void build(S first, S last)
  {
    int n = last - first, m = 32 - __builtin_clz(n);
    dat.resize(m, vector< T >(n));
    dat[0].assign(first, last);
    for(int i = 0; i < m - 1; i++) for(int j = 0; j + (1 << i) < n; j++) dat[i + 1][j] = min(dat[i][j], dat[i][j + (1 << i)]);
  }

  T query(int l, int r)
  {
    int k = 31 - __builtin_clz(r - l);
    return min(dat[k][l], dat[k][r - (1 << k)]);
  }
};


struct CumulativeSum
{
  vector< int > data;

  CumulativeSum(int sz) : data(++sz, 0) {};

  inline void add(int k, int x)
  {
    data[k] += x;
  }

  void build()
  {
    for(int i = 1; i < data.size(); i++) {
      data[i] += data[i - 1];
    }
  }

  inline int query(int k)
  {
    if(k < 0) return (0);
    return (data[min(k, (int) data.size() - 1)]);
  }
};

int n, m, q, k;

string s;

int l[100000], r[100000];

string c[100000];
int a[100000], b[100000];
int start_pos[100000];

string all_str;

long long ans[100000];

void KQ()
{
  all_str += s;
  for(int i = 0; i < q; i++) {
    start_pos[i] = all_str.size();
    all_str += c[i];
  }

  SuffixArray sa;
  sa.Build_SA(all_str);
  LongestCommonPrefixArray lcp(sa);
  vector< int > vect(all_str.size());
  for(int i = 0; i < all_str.size(); i++) vect[i] = lcp[i - 1];
  RMQ< int > tree;
  tree.build(begin(vect), end(vect));
  vector< int > add[100001], del[100001];
  long long now_v[100001] = {};
  int st[100001] = {}, gt[100001];
  fill_n(gt, 100001, all_str.size());
  for(int i = 0; i < q; i++) add[a[i]].push_back(i);
  for(int i = 0; i < q; i++) del[b[i]].push_back(i);

  vector< vector< int > > corsac(k + 1, vector< int >(all_str.size() + 1, 0));
  vector< vector< int > > bits(k + 1, vector< int >(k + 1, 0));
  for(int substr_length = 1; substr_length <= k; substr_length++) {
    for(int pos = 0; pos <= n - substr_length; pos++) {
      int &low = st[pos];
      int high = lcp.rank[pos];
      while(high - low > 0) {
        int mid = (low + high) >> 1;
        if(tree.query(mid + 1, lcp.rank[pos] + 1) >= substr_length) high = mid;
        else low = mid + 1;
      }
      int low2 = lcp.rank[pos] + 1;
      int &high2 = gt[pos];
      while(high2 - low2 > 0) {
        int mid = (low2 + high2 + 1) >> 1;
        if(tree.query(lcp.rank[pos] + 1, mid) >= substr_length) low2 = mid;
        else high2 = mid - 1;
      }
      ++corsac[substr_length][low];
      --corsac[substr_length][low2];
    }
    int now = 0;
    for(int i = 0; i <= all_str.size(); i++) {
      now += corsac[substr_length][i];
      corsac[substr_length][i] = now;
    }
  }


  for(int i = 0; i < m; i++) {
    for(auto &idx : add[i]) {
      for(int j = 0; j < k; j++) {
        for(int z = 1; z <= k; z++) {
          now_v[idx] -= 1LL * bits[j][z] * corsac[z][lcp.rank[start_pos[idx] + j]];
        }
      }
    }
    bits[l[i]][r[i] - l[i] + 1]++;
    for(auto &idx : del[i]) {
      for(int j = 0; j < k; j++) {
        for(int z = 1; z <= k; z++) {
          now_v[idx] += 1LL * bits[j][z] * corsac[z][lcp.rank[start_pos[idx] + j]];
        }
      }
    }
  }

  for(int i = 0; i < q; i++) {
    cout << now_v[i] << endl;
  }

}

void MQ()
{
  all_str += s + "_";
  for(int i = 0; i < q; i++) {
    start_pos[i] = all_str.size();
    all_str += c[i] + "_";
  }

  SuffixArray sa;
  sa.Build_SA(all_str);
  LongestCommonPrefixArray lcp(sa);
  CumulativeSum sum(all_str.size());
  vector< int > vect(all_str.size());
  for(int i = 0; i < all_str.size(); i++) vect[i] = lcp[i - 1];
  RMQ< int > tree;
  tree.build(begin(vect), end(vect));

  for(int i = 0; i < all_str.size(); i++) {
    if(sa[i] < s.size()) sum.add(i, 1);
  }
  sum.build();

  for(int i = 0; i < q; i++) {
    for(int j = a[i]; j <= b[i]; j++) {
      int pos = start_pos[i] + l[j];
      int substr_length = r[j] - l[j] + 1;

      int low = 0, high = lcp.rank[pos];
      while(high - low > 0) {
        int mid = (low + high) >> 1;
        if(tree.query(mid + 1, lcp.rank[pos] + 1) >= substr_length) high = mid;
        else low = mid + 1;
      }

      int low2 = lcp.rank[pos] + 1, high2 = all_str.size();
      while(high2 - low2 > 0) {
        int mid = (low2 + high2 + 1) >> 1;
        if(tree.query(lcp.rank[pos] + 1, mid) >= substr_length) low2 = mid;
        else high2 = mid - 1;
      }
      ans[i] += sum.query(low2 - 1) - sum.query(low - 1);
    }
  }

  for(int i = 0; i < q; i++) {
    cout << ans[i] << endl;
  }
}

int main()
{

  cin >> n >> m >> q >> k;
  cin >> s;
  for(int i = 0; i < m; i++) {
    cin >> l[i] >> r[i];
  }
  for(int i = 0; i < q; i++) {
    cin >> c[i] >> a[i] >> b[i];
  }
  if(k < q) KQ();
  else MQ();

}

Minimum MST Graph

www.hackerrank.com

問題概要

${n}$ 頂点 ${m}$ 本の重み付き辺, 最小全域木のコストが ${s}$ のグラフで, グラフ全体の重みの和の最小値を求めよ.

解法

よくわからない…( ${56}$ 点)

適当に実験すると, 最小になるときのグラフの辺の重みの種類が高々 ${2}$ 種類ということがわかる. で, まだ色々法則がありそうで, 最終的には ${O(1)}$ になるらしいけど, ${O(1)}$ は競技プログラミングではない（過激派, 実験して法則を見つけるという意味ではそうかも).

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

const int64 INF = 1LL << 58;
int64 G, N, S, M;

bool ext;

int64 calc(int64 a, int64 b, int64 c, int64 d, bool f)
{
  int64 least = M, res = 0, rest = 0;
  int64 sum = b * (b - 1) / 2;
  sum += rest * b;
  rest += b;
  res += a * min(least, sum);
  least -= sum;
  if(least <= 0) {
    ext = true;
    return (res + S);
  }

  if(f) {
    sum = d * (d - 1) / 2;
    sum += rest * d;
    res += c * min(least, sum);
  }
  return (res + S);
}

int main()
{
  cin >> G;
  while(G--) {
    cin >> N >> M >> S;
    if(M + 1 == N) {
      cout << S << endl;
      continue;
    }
    M -= N - 1;
    int64 PS = N - 1, ret = INF;
    if(S % PS == 0) {
      ret = min(ret, calc(S / PS, PS, 0, 0, false));
    }

    {
      int j = 1;
      for(int64 i = 1; i < (N > 1000 ? 100000 : S); i++) {
        int64 sub = S - i;
        if(sub <= 0) break;
        if(sub % (PS - j) == 0) {
          if(i >= sub / (PS - j)) {
            ret = min(ret, calc(sub / (PS - j), PS - j, i, j, true));
          } else {
            ret = min(ret, calc(i, j, sub / (PS - j), PS - j, true));
          }
        }
      }
    }

    for(int64 j = min(100000LL,PS - 1); j >= 1; j--) {
      if(S % __gcd(j, PS - j) != 0) continue;
      for(int64 i = 1; i <= 1; i++) {
        int64 sub = S - i * j;
        if(sub % (PS - j) == 0) {
          if(i >= sub / (PS - j)) {
            ret = min(ret, calc(sub / (PS - j), PS - j, i, j, true));
          } else {
            ret = min(ret, calc(i, j, sub / (PS - j), PS - j, true));
          }
        }
      }
    }


    for(int64 i = 1; i < min(100000LL,S); i++) {
      int64 j = i * PS + PS - S;
      int64 sub = S - i * j;
      if(PS - j == 0) continue;
      if(sub < 0) continue;
      if(j >= PS) continue;
      if(j < 0) continue;
      if(sub % (PS - j) == 0) {
        if(i >= sub / (PS - j)) {
          if(i == sub / (PS - j)) continue;
          ret = min(ret, calc(sub / (PS - j), PS - j, i, j, true));
        } else {
          ret = min(ret, calc(i, j, sub / (PS - j), PS - j, true));
        }

      }
    }
    cout << ret << endl;

  }
}

Parallelogram Connectivity

問題概要

${n \times m(1 \le n, m \le 800)}$ の六角座標で, 各セルは白か黒で塗られている.

平行四辺形区間内の連結成分の個数を求める ${q(1 \le q \le 15000)}$ 個のクエリが与えられるので全て答えよ.

解法

C/C++ では ${1}$ 秒以内という制約があるが C++14 では適用されないという罠を見つける( ${35.29}$ 点).

ソース

#include<bits/stdc++.h>

using namespace std;

int vy[] = {-1, -1, 0, 1, 1, 0};
int vx[] = {0, 1, 1, 0, -1, -1};


int N, M, Q;
int a, b, c, d;
char S[800][801];
bool s[800][800];
int v[800][800];

inline void dfs(int y, int x, int idx)
{
  v[y][x] = idx;
  for(int i = 0; i < 6; i++) {
    int ny = y + vy[i];
    int nx = x + vx[i];
    if(ny < a || ny > c || nx < b || nx > d) continue;
    if(s[ny][nx] == s[y][x] && v[ny][nx] != idx) dfs(ny, nx, idx);
  }
}

int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%s", S[i]);
    for(int j = 0; j < M; j++) {
      s[i][j] = S[i][j] == 'B';
    }
  }
  scanf("%d", &Q);
  for(int k = 1; k <= Q; k++) {
    scanf("%d %d %d %d", &a, &b, &c, &d);
    --a, --b, --c, --d;
    int ret = 0;
    for(int i = a; i <= c; i++) {
      for(int j = b; j <= d; j++) {
        if(v[i][j] != k) dfs(i, j, k), ++ret;
      }
    }
    printf("%d\n", ret);
  }
}