ei1333の日記

ぺこい

Codeforces Round #367 (Div. 2)

1871 -> 1932(+61). highest. 問題文読みやすいのですき.

A. Beru-taxi

問題概要

座標平面上に,  {n (1 \le n \le 1000)} 個のタクシーがあってそれぞれ  {(x_i, y_i)} にいて, 常に速度  {v_i} で動く.

それぞれのタクシーは最大速度で直接  {(a, b)} まで移動する. 最初のタクシーが  {(a, b)} に到達する時間を求めよ.

解法

それぞれのタクシーの到着時刻は, 距離を速度で割ればいいので  {\sqrt{ (a - x_i)^2 + (b - y_i)^2 }/ v_i} で求めることができる.

この中の最小値が答え.

 {O(n)}.

ソース

実数出力を普通に cout していて落ちている人が結構いてそうなんだとおもった.

#include <bits/stdc++.h>

using namespace std;

#define SQR(x) ((x) * (x))
int main()
{
  int a, b, n;

  cin >> a >> b;
  cin >> n;

  double ret = 1e9;
  while(n--) {
    int x, y, v;
    cin >> x >> y >> v;
    ret = min(ret, sqrt(SQR(a - x) + SQR(b - y)) / v);
  }
  cout << fixed << setprecision(10) << ret << endl;
}

B. Interesting drink

問題概要

 {n (1 \le n \le 10^5)} 個の店がある. それぞれコイン  {x_i(1 \le x \le 10^5)} で1個のボトルを購入できる.

 {q(1 \le q \le 10^5)} 日の間連続してドリンクを買う.  {i} 日目にはコイン  {m_i(1 \le m_i \le 10^9)} を使うことができる.

このとき, それぞれの日においてボトルを購入することができる店の数を求めよ.

解法

何をしてもできそう.

 {x_i} {10^5} 以下と小さめ.
 {K_i} をボトルをコイン  {i} 以下で購入できる店の数と定義する. これは累積和(いもす法?)っぽく前計算することができる.  {K_{i} = K_{i-1} +} (コイン  {i} で購入できる店) なので安い方からループで回せばOK.

そうすると  {K_{m_i}} を出力するだけとなる.

 {O(\max(x_i) + q)}.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, K[100001] = {};
  cin >> N;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    K[x]++;
  }
  for(int i = 1; i < 100001; i++) {
    K[i] += K[i - 1];
  }
  int Q;
  cin >> Q;
  while(Q--) {
    int m;
    cin >> m;
    cout << K[min(100000, m)] << endl;
  }
}

C. Hard problem

問題概要

 {n (1 \le n \le 10^5)} 個のアルファベット小文字のみから構成される文字列群  {s_i} がある. また文字列の長さの総和は高々  {10^5} である.

 {i} 番目の文字列を反転させることができて, このときコスト  {c_i(1 \le c_i \le 10^9)} かかる.

文字列を上から辞書順にするとき, 最小コストを求めよ. 辞書順に出来ないとき, -1 を出力せよ.

解法

動的計画法.

 {j = 0} のとき文字列をそのまま,  {j = 1} のとき反転とする. このとき上から  {i} 番目まで辞書順で  {i} 番目を  {j} にするときのコストを  {dp_{i,j}} とする.  {dp_{i,j}} へは,  {s_{i - 1} \le s_{i}} となるとき遷移できて, 反転する時は コストを  c_{i} 足すと良い.

 {O(n \sqrt{|s_i|})}.

ソース

#include <bits/stdc++.h>

using namespace std;

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

int N, C[100000];
string S[2][100000];
int64 dp[2][100000];
char buff[100005];

int main()
{
  fill_n(*dp, 2 * 100000, INF);

  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d ", &C[i]);
  }
  for(int i = 0; i < N; i++) {
    scanf("%s", buff);
    S[0][i] = buff;
    S[1][i] = S[0][i];
    reverse(begin(S[1][i]), end(S[1][i]));
  }

  dp[0][0] = 0;
  dp[1][0] = C[0];

  for(int i = 1; i < N; i++) {
    for(int j = 0; j < 2; j++) {
      for(int k = 0; k < 2; k++) {
        if(S[j][i - 1] <= S[k][i]) {
          int64 cost = dp[j][i - 1];
          if(k == 1) cost += C[i];
          dp[k][i] = min(dp[k][i], cost);
        }
      }
    }
  }
  int64 val = min(dp[0][N - 1], dp[1][N - 1]);
  if(val >= INF) val = -1;
  printf("%I64d\n", val);
}

D. Vasiliy's Multiset

問題概要

重複が許された集合(multiset)  {A} がある. 最初  {A} には  {0} のみが含まれる.

以下のいずれかをさす  {q(1 \le q \le 2 \times 10^5)} 個のクエリが与えられるのですべて処理せよ.

  • "+ x" : 集合  {A} に値  {x} を加える.
  • "- x" : 集合  {A} から値  {x} をもつものを 1 つ削除する.
  • "? x" : 集合  {A} に含まれる任意の値と  {x} のXOR(排他的論理和)をとることができるとき, そのXORの最大値を求めよ.

解法

とりあえず "? x" が大変そうなのでこれから考える.

一般に OR とか XOR とか書かれているときは 上の bit から決めていくと上手くいくのでそれに則る.

この問題では, なるべく上位の bit がたっていたほうが最大値に近づくので, 上位 bit から貪欲に  {1} にできないかどうか見ていく. XOR なので,  {x} {i} 桁目の bit が  {1} のとき,  {A} から探す値は  {i} 桁目が  {0} のほうがよくて,  {0} のとき  {1} のほうがよい. ダメだったらもう 1 方の bit にする.

よって,  {A} のうち  {i} 桁目の bit が  {y} である数字が存在するか分かれば良い. これはある区間に値があるかどうか求めることと同じ(ソースコード参照). 値の追加と値の削除があることを考えると, 問題文にもある multiset が使えそうで, 実際使うとできる. 追加/削除/区間に値があるかはすべて二分探索を使えば対数オーダでできる.

計算量は  {O(Q \log x \log Q)}. log が 2 つだけど間に合うらしい.

ソース

最初に  {0} があるの見えていなかったりして 2WAした><

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int Q;

  scanf("%d", &Q);

  multiset< int > sets;
  sets.insert(0);

  for(int i = 0; i < Q; i++) {
    char c;
    int val;
    scanf(" %c %d", &c, &val);
    if(c == '+') sets.insert(val);
    else if(c == '-') sets.erase(sets.find(val));
    else if(c == '?') {
      int now = 0;
      for(int i = 29; i >= 0; i--) {
        int low = now;
        int mid = now | (1 << i);
        int high = now + (1 << (i + 1));
        if((val >> i) & 1) {
          auto p = sets.lower_bound(low);
          auto q = sets.lower_bound(mid);
          if(p != q) now = low;
          else now = mid;
        } else {
          auto q = sets.lower_bound(mid);
          auto r = sets.lower_bound(high);
          if(q != r) now = mid;
          else now = low;
        }
      }
      printf("%d\n", now ^ val);
    }
  }
}

E. Working routine

問題概要

 {n(1 \le n \le 1000)} {m(1 \le m \le 1000)} 列の行列があって, 各マスには  {v_{i, j} (1 \le v_{i, j} \le 10^9)} が書かれている.

それぞれ左上を {(a_i, b_i), (c_i, d_i)}とした, 高さ {h_i}, 幅  {w_i} の 2 つの長方形領域を入れ替えるクエリが  {q(1 \le q \le 10000)} 個与えられるので順番に処理して, 最終的な行列を出力せよ.

解法

上下左右に双方向連結リストを使えば,  {O(q(n + m))} でできる感じがするので実装を頑張る.

 {(a, b), (c, d)} から長方形の枠を時計回りに辿るイメージをする.(リストなので  {(a, 0)} から右に  {x} 回辿れば,  {(a, x)} につく. このときの計算量は  {O(m)} なので大丈夫).

まず, 長方形の上辺をつなぎ替えることを考える. 長方形の上辺が持つ上方向のポインタ同士と, 長方形の上辺が持つ上方向のポインタが指すマスの下方向のポインタ同士を入れ替えればいいことがわかる.

右辺, 下辺, 左辺も方向が違うだけで考え方は同じ. 同じことの繰り返しなので考えることは少ない.

入れ替えるポインタの数は最大で  {4 \times (n + m)}. よって  {O(q(n + m))} で間に合う.

ソース

これは時間中に解けなかった...

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M, Q, V[1003][1003];
  pair< int, int > t[1003][1003], s[1003][1003], l[1003][1003], r[1003][1003];

  scanf("%d %d %d", &N, &M, &Q);
  for(int i = 0; i <= N + 1; i++) {
    for(int j = 0; j <= M + 1; j++) {
      t[i][j] = {i - 1, j};
      s[i][j] = {i + 1, j};
      l[i][j] = {i, j - 1};
      r[i][j] = {i, j + 1};
    }
  }
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      scanf("%d", &V[i][j]);
    }
  }

  queue< pair< pair< int, int >&, pair< int, int >& > > event;
  while(Q--) {
    int a, b, c, d, h, w;
    scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &h, &w);
    pair< int, int > AB(a, 0), CD(c, 0);
    for(int i = 0; i < b; i++) {
      AB = r[AB.first][AB.second];
    }
    for(int i = 0; i < d; i++) {
      CD = r[CD.first][CD.second];
    }
    AB = l[AB.first][AB.second], CD = l[CD.first][CD.second];
    for(int i = 0; i < w; i++) {
      AB = r[AB.first][AB.second];
      CD = r[CD.first][CD.second];
      auto pp = t[AB.first][AB.second], qq = t[CD.first][CD.second];
      event.emplace(s[pp.first][pp.second], s[qq.first][qq.second]);
      event.emplace(t[AB.first][AB.second], t[CD.first][CD.second]);
    }
    AB = t[AB.first][AB.second], CD = t[CD.first][CD.second];
    for(int i = 0; i < h; i++) {
      AB = s[AB.first][AB.second];
      CD = s[CD.first][CD.second];
      auto pp = r[AB.first][AB.second], qq = r[CD.first][CD.second];
      event.emplace(l[pp.first][pp.second], l[qq.first][qq.second]);
      event.emplace(r[AB.first][AB.second], r[CD.first][CD.second]);
    }
    AB = r[AB.first][AB.second], CD = r[CD.first][CD.second];
    for(int i = 0; i < w; i++) {
      AB = l[AB.first][AB.second];
      CD = l[CD.first][CD.second];
      auto pp = s[AB.first][AB.second], qq = s[CD.first][CD.second];
      event.emplace(t[pp.first][pp.second], t[qq.first][qq.second]);
      event.emplace(s[AB.first][AB.second], s[CD.first][CD.second]);
    }
    AB = s[AB.first][AB.second], CD = s[CD.first][CD.second];
    for(int i = 0; i < h; i++) {
      AB = t[AB.first][AB.second];
      CD = t[CD.first][CD.second];
      auto pp = l[AB.first][AB.second], qq = l[CD.first][CD.second];
      event.emplace(r[pp.first][pp.second], r[qq.first][qq.second]);
      event.emplace(l[AB.first][AB.second], l[CD.first][CD.second]);
    }
    while(!event.empty()) {
      swap(event.front().first, event.front().second);
      event.pop();
    }
  }

  for(int i = 1; i <= N; i++) {
    pair< int, int > p(i, 0);
    for(int j = 0; j < M; j++) {
      p = r[p.first][p.second];
      printf("%d ", V[p.first][p.second]);
    }
    puts("");
  }
}