ei1333の日記

ぺこい

Codeforces Round #419 (Div. 1)

1943->1945(+2).

o—- 370th.

ぐぬぬ. カレンちゃんは可愛いけど…

A. Karen and Game

codeforces.com

問題概要

 {n \times m(1 \le n, m \le 100)} のグリッドがあって,  {(i, j)} には  {g_{i,j}(0 \le g_{i, j} \le 500)} が書かれている.

全要素  {0} のグリッドに対し, ある列あるいは行に一様に  {1} 加算する操作を繰り返してグリッドを構成できるとき最小回数の操作例を出力せよ.

解法

わからないのでフィーリングで解いたら何か通った. 正当性が分からない. 何故通ったんだろう. きっと合ってるんだよね. うしししし.

以下の貪欲的な操作を繰り返す.

  1. すべての行と列を見て, 一様に  {1} 加算しても  {g_{i, j}} を上回らない行位置の最大値と列の最大値を挙げる.
  2. そのようなものが存在しない時おわり.
  3. 行か列片方存在する時はそれを使う.
  4. 行と列両方存在する時は  {n \gt m} のときは列, それ以外のときは行を使う.

計算量も  {O(nm \max g_{i, j}) } でちょっと怖い.

ソース

冷静に考えれば一番上の行の操作の回数を全通り試せば一意.

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int H, W;
  int mat[100][100];
  cin >> H >> W;
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) cin >> mat[i][j];
  }

  vector< string > dump;
  for(;;) {
    int latte = -1, malta = -1;
    for(int i = 0; i < H; i++) {
      bool flag = true;
      for(int j = 0; j < W; j++) flag &= mat[i][j] > 0;
      if(flag) latte = i;
    }
    for(int i = 0; i < W; i++) {
      bool flag = true;
      for(int j = 0; j < H; j++) flag &= mat[j][i] > 0;
      if(flag) malta = i;
    }
    if(latte == -1 && malta == -1) break;
    if(latte == -1) {
      for(int j = 0; j < H; j++) mat[j][malta]--;
      dump.emplace_back("col " + to_string(malta + 1));
    } else if(malta == -1) {
      for(int j = 0; j < W; j++) mat[latte][j]--;
      dump.emplace_back("row " + to_string(latte + 1));
    } else if(H > W) {
      for(int j = 0; j < H; j++) mat[j][malta]--;
      dump.emplace_back("col " + to_string(malta + 1));
    } else {
      for(int j = 0; j < W; j++) mat[latte][j]--;
      dump.emplace_back("row " + to_string(latte + 1));
    }
  }

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(mat[i][j] > 0) {
        cout << -1 << endl;
        return(0);
      }
    }
  }

  cout << dump.size() << endl;
  for(auto& s : dump) {
    cout << s << endl;
  }
}

B. Karen and Test

codeforces.com

問題概要

 {n(1 \le n \le 2 \times 10^5)} 個の整数  {a_i(1 \le a_i \le 10^9)} が並んでいる.

隣り合った整数を交互に足し引きした値を下の行に書く操作を整数が  {1} 個になるまで繰り返す.

最終的に残る整数の値を  {10^9 + 7} で割った余りで求めよ.

解法

実験を書く時間帯が遅すぎたためダメ. さらに実験のコードすらしばらく間違えていた. 悲しいね.

 {i} 番目の要素が最終的な整数に与える影響の度合いを実験で調べる.

ぐっと睨むと  {n} {4} で割った余りが  {3} のときに,  {{}_{{n-1}\%2} \mathrm{ C } _{{i-1}\%2} * {}_{(n-1)/2} \mathrm{C} _{(i-1)/2}} みたいないい感じの形なってるいることに気付ける.

 {n} {4} で割った余りが  {3} になるように, 最初の入力を  {O(n)} でシミュレーションして調整して, あとは式に投げれば良い.

ソース

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

inline int64 modCombination(int p, int q)
{
  static int64 fact[202020], rfact[202020];
  if(fact[0] == 0) {
    fact[0] = rfact[0] = 1;
    for(int i = 1; i < 202020; i++) {
      fact[i] = fact[i - 1] * i % mod;
      rfact[i] = modInv(fact[i]);
    }
  }
  if(q < 0 || p < q) return (0);
  return (fact[p] * rfact[q] % mod * rfact[p - q] % mod);
}

int main()
{
  int N, A[200000];
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  --N;

  int rest = N % 4;
  bool flip = false;
  while(rest > 0) {
    int B[200000];
    --N;
    --rest;
    for(int i = 0; i <= N; i++) {
      if(flip) (B[i] = A[i] - A[i + 1] + mod) %= mod;
      else (B[i] = A[i] + A[i + 1]) %= mod;
      flip ^= true;
    }
    swap(A, B);
  }

  int64 ret = 0;
  for(int i = 0; i <= N; i++) {
    (ret += modCombination(N % 2, i % 2) * modCombination(N / 2, i / 2) % mod * (A[i] + mod) % mod) %= mod;
  }
  cout << ret << endl;
}

C. Karen and Supermarket

codeforces.com

問題概要

 {n(1 \le n \le 5000)} 個の商品があって, それぞれのコストは  {c_i} である. また商品ごとに対応するチケットがあって, チケットを使用すると  {d_i} 割引される.

商品  {i(i \ge 2)} のチケットを使うためには, 商品  {x_i} のチケットも使わなければならない制約がある.

このときコスト {b} 以下で買える商品の個数の最大値を求めよ.

解法

 {O(n^2)} の木DP.

 {\mathrm{dp}[\mathrm{idx}][\mathrm{sum}][\mathrm{connect}] :=} 頂点  {\mathrm{idx}} の部分木内で商品を  {\mathrm{sum}} 個買うときのコストの最小値,  {\mathrm{connect} = 0} のとき根と繋がってなくて(頂点  {\mathrm{idx}} の商品は買わなくてもよくて, チケットを使えない),  {\mathrm{connect} = 1} のとき根と繋がっていて(頂点  {\mathrm{idx}} の商品を必ず買ってチケットを使う),  {\mathrm{connect} = 2} のときどちらでも良い とする.

まず  {\mathrm{connect} = 0} のときのDPの遷移は自明で, 子供たちの頂点の dp の  {\mathrm{connect} = 0} のアレを足し合わせる.

 {\mathrm{connect} = 1} のとき, 子どもたちの頂点のチケットの使用はどちらでもよいので dp の  {\mathrm{connect} = 2} のアレと足し合わせる.

 {\mathrm{connect} = 2} はどちらでもよいので, 自身の  {\mathrm{connect} = 0, 1} の min をとればよい.

直感的には  {O(n^3)} だが有名な某によって  {O(n^2)} となるため解ける.

ソース

にゃーーーーん, うーーーん, 解きたいねね.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

const int64 INF = 1LL << 60;

vector< int64 > operator*(vector< int64 > &x, vector< int64 > &y)
{
  vector< int64 > z(x.size() + y.size() - 1, INF);
  for(int i = 0; i < x.size(); i++) {
    for(int j = 0; j < y.size(); j++) {
      z[i + j] = min(z[i + j], x[i] + y[j]);
    }
  }
  return (z);
}

int main()
{
  int N, W;
  cin >> N >> W;
  vector< int > a(N), b(N);
  vector< int > g[200000];
  for(int i = 0; i < N; i++) {
    int par;
    cin >> a[i] >> b[i];
    b[i] = a[i] - b[i];
    if(i > 0) {
      cin >> par;
      g[--par].emplace_back(i);
    }
  }
  vector< vector< int64 > > dp0(N), dp1(N), dp01(N);
  function< void(int) > dfs = [&](int idx)
  {
    dp0[idx] = {0, a[idx]};
    dp1[idx] = {INF, b[idx]};
    for(auto &to : g[idx]) {
      dfs(to);
      dp1[idx] = dp1[idx] * dp01[to];
      dp0[idx] = dp0[idx] * dp0[to];
    }
    dp01[idx].resize(dp0[idx].size());
    for(int i = 0; i < dp0[idx].size(); i++) {
      dp01[idx][i] = min(dp0[idx][i], dp1[idx][i]);
    }
  };
  dfs(0);
  int ret = 0;
  for(int i = 0; i < dp01[0].size(); i++) {
    if(dp01[0][i] <= W) ret = i;
  }
  cout << ret << endl;
}

D. Karen and Cards

http://codeforces.com/contest/815/problem/Dcodeforces.com

問題概要

 {n(1 \le n \le 5 \times 10^5)} 枚のカードがある. それぞれのカードには  {a_i, b_i, c_i} {3} つのパラメータが割り当てられている.

ここで,  {i} 番目のカードに勝つカードは  {2} つ以上のパラメータで値が上回っているものである.

 {3} つのパラメータの上限はそれぞれ  {p, q, r(1 \le p, q, r \le 5 \times 10^5)} であるとき, 任意のカードに勝てるカードの種類数を求めよ.

解法

カード  {(a_i, b_i, c_i)} に勝てないものは

  •  {(0, 0, 0)} -  {(a_i, b_i, r)}.
  •  {(0, 0, 0)} -  {(a_i, q, c_i)}.
  •  {(0, 0, 0)} -  {(p, b_i, c_i)}.

というのはそう. あるパラメータがいずれかのカードの上記の範囲に入るとダメなのでこれは直方体の和集合の体積を求める問題そのもの.

 {n} 個の直方体の和集合の体積を  {O(n \log n)} で求める一般的なテク(?)を使う.

 {n} 個の長方形(右下  {(0, 0)}, 左上  {(a_i, b_i)}) が順に与えられるので, それぞれのタイミングで長方形の和集合の面積を求めよ.

上の問題が解けると, それぞれのタイミングで求まった面積に奥行きを掛けることで直方体の体積を求めることができるので, こっちを頑張って解く.

意味のある長方形の左上の点を map で管理しておき, 現在の和集合の面積も求まっているとする. これに新たな長方形(の左上の点)を  {1} 個加えることを考える.

言葉じゃ当然説明が無理(悲しいね)なので図にした.

f:id:ei1333:20170620170716p:plain
f:id:ei1333:20170620170740p:plain
f:id:ei1333:20170620170749p:plain
f:id:ei1333:20170620170836p:plain

以下ソースの addPoint がほぼそのままの実装.

あとははいをすると  {O(n \log n)}.

ソース

なんか冷静に考えれば C も D も解ける気がする(冷静に考えないため(B が難しすぎる.

ここのカレンちゃんかわいい.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

struct RectangleUnion
{
  map< int64, int64 > data;
  int64 sum;

  RectangleUnion() : sum(0)
  {
    data[0] = 1LL << 60;
    data[1LL << 60] = 0;
  }

  void addPoint(int64 x, int64 y)
  {
    auto p = data.lower_bound(x);
    if(p->second >= y) return;
    const int64 nxtY = p->second;
    --p;
    while(p->second <= y) {
      auto it = *p;
      p = --data.erase(p);
      sum -= (it.first - p->first) * (it.second - nxtY);
    }
    sum += (x - p->first) * (y - nxtY);
    data[x] = y;
  }

  int64 getSum()
  {
    return (sum);
  }
};

int main()
{
  int N, P, Q, R;
  scanf("%d %d %d %d", &N, &P, &Q, &R);
  vector< pair< int, int > > add[500001];
  for(int i = 0; i < N; i++) {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    add[P].emplace_back(B, C);
    add[A].emplace_back(Q, C);
    add[A].emplace_back(B, R);
  }

  int64 ret = 0;
  RectangleUnion ru;
  for(int i = P; i >= 1; i--) {
    for(auto &p : add[i]) ru.addPoint(p.first, p.second);
    ret += 1LL * Q * R - ru.getSum();
  }

  printf("%lld\n", ret);
}