Mail.Ru Cup 2018 Round 3 - ei1333の日記

ねねねねー

E. Check Transcription

codeforces.com

問題概要

01列 ${s(1 \le |s| \le 10^5)}$ が与えられる.

01をそれぞれ空ではない文字列 ${r_0, r_1 (r_0 \ne r_1)}$ に置換した場合, 文字列 ${t(1 \le |t| \le 10^6)}$ になるようなものは何通りか.

解法

${s}$ の 0 と 1 の総数 ${x, y}$ を求めておく.

文字数の関係を考えると ${r_0, r_1}$ のそれぞれの長さは ${x \times |r_0| + y \times |r_1| = |t|}$ を満たすようなもの.

これを満たすような長さを総当たりする.

長さが決まると, 最初の0と最初の1が何の文字列になるかが ${t}$ より求まる.

すべての0と1に対して、その文字列と一致しているかを確認できれば良い.

t のある部分文字列同士が一致しているかを高速に判定したくて、いつものをすればクエリ ${O(1)}$ でできる. ${10^6 \log 10^6}$ 回もRMQを投げない.

ソース

こういうのロリハはったほうがいいのかなー

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

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(string &t, int si = 0, int ti = 0) {
    int sn = s.size(), tn = t.size();
    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(string &t) {
    int low = -1, high = SA.size();
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    return (high);
  }

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

  void output() {
    for(int i = 0; i < size(); i++) {
      cout << i << ": " << s.substr(SA[i]) << endl;
    }
  }
};

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());
    LCP[0] = 0;
    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] + 1] = h;
        if(h > 0) --h;
      }
    }
  }

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

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

template< typename T >
struct SparseTable {
  vector< vector< T > > st;
  vector< int > lookup;

  SparseTable(const vector< T > &v) {
    int b = 0;
    while((1 << b) <= v.size()) ++b;
    st.assign(b, vector< T >(1 << b));
    for(int i = 0; i < v.size(); i++) {
      st[0][i] = v[i];
    }
    for(int i = 1; i < b; i++) {
      for(int j = 0; j + (1 << i) <= (1 << b); j++) {
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
    lookup.resize(v.size() + 1);
    for(int i = 2; i < lookup.size(); i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }

  inline T rmq(int l, int r) {
    int b = lookup[r - l];
    return min(st[b][l], st[b][r - (1 << b)]);
  }
};

int main() {
  string S, T;
  cin >> S >> T;

  int N = (int) S.size();
  int M = (int) T.size();

  int sum[2] = {};
  for(auto &p : S) p -= '0';
  for(auto &p : S) sum[p]++;

  vector< pair< int, int > > sz;
  for(int a = 1; a <= M; a++) {
    int64 rest = M - 1LL * sum[0] * a;
    if(rest <= 0) continue;
    if(rest % sum[1] != 0) continue;
    sz.emplace_back(a, rest / sum[1]);
  }

  int ret = 0;

  SuffixArray sa;
  sa.Build_SA(T);
  LongestCommonPrefixArray lcp(sa);
  SparseTable< int > sp(lcp.LCP);
  vector< int > rev(M);


  for(int i = 0; i < M; i++) rev[sa[i]] = i;


  for(auto &p : sz) {

    vector< int > range[2];
    int pos = 0;
    for(auto &q : S) {
      if(q == 0) {
        range[0].emplace_back(pos);
        pos += p.first;
      } else {
        range[1].emplace_back(pos);
        pos += p.second;
      }
    }

    if(p.first == p.second) {
      int latte = rev[range[0][0]];
      int malta = rev[range[1][0]];
      if(latte > malta) swap(latte, malta);
      if(sp.rmq(latte + 1, malta + 1) >= p.first) continue;
    }

    bool flag = true;
    for(int j = 1; j < range[0].size(); j++) {
      int latte = rev[range[0][j - 1]];
      int malta = rev[range[0][j]];
      if(latte > malta) swap(latte, malta);
      flag &= sp.rmq(latte + 1, malta + 1) >= p.first;
    }

    for(int j = 1; j < range[1].size(); j++) {
      int latte = rev[range[1][j - 1]];
      int malta = rev[range[1][j]];
      if(latte > malta) swap(latte, malta);
      flag &= sp.rmq(latte + 1, malta + 1) >= p.second;
    }

    ret += flag;

  }
  cout << ret << endl;
}

F. Write The Contest

codeforces.com

問題概要

${n(1 \le n \le 100)}$ 個の問題があって、 ${i}$ 番目の問題の難易度は ${a_i(1 \le a_i \le 10^4)}$ , 解くことによって得られるスコアは ${p_i(1 \le p_i \le 10)}$ である.

スキルレベル ${s}$ があって初期値は ${1.0}$ である. 最初に任意時間トレーニングすることができて, ${t}$ 分間トレーニングするとスキルレベルに ${Ct}$ 加算される.

問題は好きな順番で解くことができる. 問題 ${i}$ を解く時 ${\frac {a_i} {s}}$ 分かかる. 問題と問題の間では 10 分間のインターバルを入れる必要があり, その間にスキルレベルは現在の 90% になる.

${T}$ 分間で得られる最大スコアを求めよ.

解法

これはなんですか.

難易度が難しい問題から解くべきなので, 降順にソートしておく.

とりあえず ${s=1.0}$ として, 以下を求めるDPをする.

dp[解いた問題数][得たスコア]:= それを達成するための最短時間(10分間のインターバルを除く)

スキルレベル ${s}$ で問題を解き始めた場合, dpの結果を ${s}$ で割った値が最短時間である. この値が ${T}$ 以下であればそのスコアを時間内に達成できる.

${s}$ をどの値にするかなんですが, これは三分探索で最小化できるため.

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

void beet() {
  int N, A[100], P[100];
  double C, T;
  cin >> N;
  cin >> C >> T;
  vector< pair< int, int > > dat(N);
  for(auto &p : dat) cin >> p.first >> p.second;
  sort(dat.rbegin(), dat.rend());
  for(int i = 0; i < N; i++) tie(A[i], P[i]) = dat[i];
  double mat[100][101];
  for(int i = 0; i < N; i++) {
    mat[i][0] = A[i] / 0.9;
    for(int j = 1; j <= 100; j++) {
      mat[i][j] = mat[i][j - 1] / 0.9;
    }
  }

  vector< vector< double > > dp(1001, vector< double >(101, 1e50));
  dp[0][0] = 0;
  for(int i = 0; i < N; i++) {
    for(int k = 1000; k >= P[i]; k--) {
      for(int j = i; j >= 0; j--) {
        dp[k][j + 1] = min(dp[k][j + 1], dp[k - P[i]][j] + mat[i][j]); // j問解く
      }
    }
  }

  int ret = 0;
  for(int i = 0; i < 1001; i++) {
    for(int k = 0; k < 101; k++) {
      if(dp[i][k] >= 1e50) continue;

      double left = 0, right = T;

      auto f = [&](double t) {
        return t + dp[i][k] / (1 + C * t);
      };

      for(int j = 0; j < 100; j++) {
        double latte = (left * 2 + right) / 3;
        double malta = (left + right * 2) / 3;
        if(f(latte) < f(malta)) right = malta;
        else left = latte;
      }
      if(f(left)+10*k + (1e-9) <= T) {
        ret = max(ret, i);
      }
    }
  }

  cout << ret << endl;

}

int main() {
  int TC;
  cin >> TC;
  while(TC--) beet();
}