読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

Codeforces Round #401 (Div. 2)

はい.

A. Shell Game

codeforces.com

解法

手.

ソース

#include<bits/stdc++.h>

using namespace std;
int main()
{
  vector< vector< int > > v;
  v.push_back({0, 1, 2});
  v.push_back({1, 0, 2});
  v.push_back({1, 2, 0});
  v.push_back({2, 1, 0});
  v.push_back({2, 0, 1});
  v.push_back({0, 2, 1});


  int n, x;
  cin >> n >> x;
  cout << v[n % v.size()][x] << endl;
}

B. Game of Credit Cards

codeforces.com

解法

貪欲を信じる.

ソース

#include<bits/stdc++.h>

using namespace std;

int a(string x, string y)
{
  int a[10];
  for(int i = 0; i < 10; i++) {
    a[i] = count(begin(y), end(y), (char)(i + '0'));
  }
  sort(begin(y), end(y));
  int ret = 0;
  for(int i = 0; i < x.size(); i++) {
    for(int j = x[i] - '0'; j <= 9; j++) {
      if(a[j] > 0) {
        --a[j], ++ret;
        break;
      }
    }
  }
  return(x.size() - ret);
}

int b(string x, string y)
{
  int a[10];
  for(int i = 0; i < 10; i++) {
    a[i] = count(begin(y), end(y), (char)(i + '0'));
  }
  sort(begin(y), end(y));
  int ret = 0;
  for(int i = 0; i < x.size(); i++) {
    for(int j = x[i] - '0' + 1; j <= 9; j++) {
      if(a[j] > 0) {
        --a[j], ++ret;
        break;
      }
    }
  }
  return(ret);
}
int main()
{
  int n;
  string s, t;

  cin >> n;
  cin >> s >> t;
  cout << a(s, t) << endl;
  cout << b(s, t) << endl;
}

C. Alyona and Spreadsheet

codeforces.com

問題概要

 {n \times m(1 \le nm \le 10^5)} {2} 次元グリッドがあり各セルには値  {a_{i,j}} が書かれている.

このグリッドに対し以下の  {q} 個のクエリに答えよ.

  •  {l_i} 行目から  {r_i} 行目を取り出したときに, ソートされている列が存在するか判定する

解法

列ごとにソートされている区間というのは, かんたんな尺取りで求めることが出来る. この集合の個数は  {O(nm)} 個.

dp[y]:=  {y} 行目が上端としたときのソートされている下端の最大値

を求めると, 各クエリに  {O(1)} で答えることが可能なので求める.

ソートされている区間の上端でソートしておく. すると, dp[y] = max(dp[y - 1], {上端が  {y} のうちの下端の最大値}) となる.

ソース

#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int n, m, q;

  cin >> n >> m;
  vector< vector< int > > a(n, vector< int >(m));
  vector< int > range(n, -INF);
  vector< int > bigs(n, -INF);

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }

  for(int i = 0; i < m; i++) {
    int begin = 0, pv = -1;
    for(int j = 0; j < n; j++) {
      if(pv > a[j][i]) {
        range[begin] = max(range[begin], j - 1);
        begin = j;
      }
      pv = a[j][i];
    }
    range[begin] = max(range[begin], n - 1);
  }

  int big = 0;
  for(int i = 0; i < n; i++) {
    big = max(big, range[i]);
    bigs[i] = big;
  }

  cin >> q;
  for(int i = 0; i < q; i++) {
    int c, d;
    cin >> c >> d;
    --c, --d;
    if(bigs[c] >= d) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

D. Cloud of Hashtags

codeforces.com

問題概要

 {n(1 \le n \le 500\ 000)} 個の文字列が縦に並んでいる.

これを辞書順にするために, 任意の文字列の文末から好きなだけ削除できる.

削除する文字列を最小化したとき, 最終的なこの文字列集合の一例を出力せよ.

解法

dp[idx][len]:=idx番目がlen文字のときの削除する文字数の最小値

として配るDP + 復元をする(ダメ, 踏みとどまって実装が軽い解法を考えよう)

dp[idx][len] からのDPの遷移は

  • s[idx][0,idx] = s[idx + 1][0,idx] のとき, dp[idx+1][j(≧ len)] = dp[idx][len] + ほげ
  • s[idx][0,idx] < s[idx + 1][0,idx] のとき, dp[idx+1][j(≧ s[idx] と s[idx + 1] のLCP)] = dp[idx][len] + ほげ
  • s[idx][0,idx] > s[idx + 1][0,idx] のとき, 遷移できない

をすればよくて, これはいい感じに線形オーダでできるので, これに加えて頑張って復元すれば良い(良くはない).

ソース

#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 29;

void chmin(int &a, int b)
{
  a = min(a, b);
}

int main()
{
  int n;
  string s[500000];

  cin >> n;
  for(int i = 0; i < n; i++) cin >> s[i];

  vector< vector< int > > dp(n);
  vector< vector< pair< int, int > > > rev(n);

  for(int i = 0; i < n; i++) {
    dp[i].assign(s[i].size(), i == 0 ? 0 : INF);
    rev[i].assign(s[i].size(), make_pair(-1, -1));
  }

  for(int i = 0; i < n; i++) {

    if(i > 0) {
      int move = INF;
      pair< int, int > pv;
      for(int j = 0; j < s[i].size(); j++) {
        if(dp[i][j] > move) {
          dp[i][j] = move;
          rev[i][j] = pv;
        }
        if(move > dp[i][j]) {
          move = dp[i][j];
          pv = {i, j};
        }
      }
    }
    if(i == n - 1) break;


    bool latte = false;
    int rock;
    for(int j = 0; j < s[i].size(); j++) {
      int cost = dp[i][j] + ((int) s[i].size() - j - 1);
      if(latte) {
        if(dp[i + 1][rock] > cost) {
          dp[i + 1][rock] = cost;
          rev[i + 1][rock] = {i, j};
        }
      } else if(j >= s[i + 1].size() || s[i][j] > s[i + 1][j]) {
        break;
      } else {
        if(s[i][j] < s[i + 1][j]) {
          rock = j;
          latte = true;
        }
        if(dp[i + 1][j] > cost) {
          dp[i + 1][j] = cost;
          rev[i + 1][j] = {i, j};
        }
      }
    }
  }

  int ret = INF;
  for(int i = 0; i < s[n - 1].size(); i++) {
    chmin(ret, dp[n - 1][i] + ((int)s[n - 1].size() - i - 1));
  }

  vector< string > sub;
  for(int i = 0; i < s[n - 1].size(); i++) {
    if(dp[n - 1][i] + ((int)s[n - 1].size() - i - 1) == ret) {
      pair< int, int > now = {n - 1, i};
      sub.push_back(s[n - 1].substr(0, i + 1));
      int remake = n - 1;
      while(rev[now.first][now.second] != make_pair(-1, -1)) {
        now = rev[now.first][now.second];
        if(remake != now.first) {
          remake = now.first;
          sub.push_back(s[remake].substr(0, now.second + 1));
        }
      }
    }
  }
  reverse(begin(sub), end(sub));
  for(auto& s : sub) cout << s << endl;
}

E. Hanoi Factory

codeforces.com

問題概要

 {n} 個のドーナツ型のアレがあって, それぞれ内径  {a_i}, 外径  {b_i}, 高さ  {h_i} である. 以下の条件を満たすように積んだ時の高さの最大値を求めよ.

  • ドーナツ  {i} の上に置けるものは  {b_j \le b_i} を満たす
  • ドーナツ  {i} の上に置けるものは  {b_j \gt a_i} を満たす

解法

まず, 以下のように並び替えることによって, いい感じにトポロジカルソートをする.

  • 置ける順は外径が大きいものからなので, 外径の降順.
  • 外径が同じものに対しては内径の降順.

ここまで分かれば, あとは座圧してセグ木でえい.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 58;

struct SegmentTree
{
  vector< int64 > seg;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, -INF);
  }

  int64 rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (-INF);
    if(a <= l && r <= b) return (seg[k]);
    return (max(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
                rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }

  int64 rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }

  void update(int k, int64 x)
  {
    k += sz - 1;
    seg[k] = max(seg[k], x);
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = max(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }
};

int main()
{
  int n;
  int a[100000], b[100000], h[100000];

  vector< int > nums;

  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i] >> b[i] >> h[i];
    nums.push_back(a[i]);
    nums.push_back(b[i]);
  }

  vector< int > latte(n);
  iota(begin(latte), end(latte), 0);
  sort(begin(latte), end(latte), [&](int x, int y)
  {
    if(b[x] == b[y]) return (a[x] > a[y]);
    return (b[x] > b[y]);
  });

  sort(begin(nums), end(nums));
  nums.erase(unique(begin(nums), end(nums)), end(nums));

  for(int i = 0; i < n; i++) {
    a[i] = lower_bound(begin(nums), end(nums), a[i]) - begin(nums);
    b[i] = lower_bound(begin(nums), end(nums), b[i]) - begin(nums);
  }

  SegmentTree tree(nums.size());
  for(int i = 0; i < nums.size(); i++) tree.update(i, 0);
  for(int i : latte) tree.update(a[i], tree.rmq(0, b[i]) + h[i]);

  cout << tree.rmq(0, nums.size()) << endl;
}