Codeforces Round #401 (Div. 2)

はい.

A. Shell Game

解法

手.

ソース

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

ei1333の日記

ぺこい

Codeforces Round #401 (Div. 2)

A. Shell Game

解法

ソース

B. Game of Credit Cards

解法

ソース

C. Alyona and Spreadsheet

問題概要

解法

ソース

D. Cloud of Hashtags

問題概要

解法

ソース

E. Hanoi Factory

問題概要

解法

ソース