ei1333の日記

ぺこい

Codeforces Round #371 (Div. 1)

Codeforces

うーん

A. Sonya and Queries

問題概要

空の多重集合に対し, {t(1 \le t \le 100\ 000)} 個のクエリが与えられるので処理せよ.

  1. {+\ a_i:} {a_i(1 \le a_i \lt 10^{18})} を {1} 個集合に加える.
  2. {-\ a_i:} {a_i} を {1} 個集合から消す.
  3. {?\ s:} 集合の中で, パターン {s(1 \le |s| \le 18)} に一致する値の個数を数えて出力する. パターンは値を {10} 進表記したときの各桁の偶奇を指定している.

解法

{s} のパターンは {2^{18}} 通りしかない. また, {a_i} が定まれば {s} が一意に定まるのは明らか.

クエリ {1} と {2} のときに, どの {s} にマッチするかを見て, 対応するところに加えると良い.

ビットで各桁の偶奇を保存すると楽.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int sz[1 << 20];

int main()
{
  int T;

  cin >> T;
  while(T--) {
    char t;
    int64 S;

    cin >> t >> S;

    int bit = 0;
    for(int i = 0; i < 20; i++) {
      bit |= (S % 2) << i;
      S /= 10;
    }

    if(t == '+') ++sz[bit];
    else if(t == '-') --sz[bit];
    else cout << sz[bit] << endl;
  }
}

B. Searching Rectangles

問題概要

{n \times n(1 \le n \le 2^{16})} のセルからなる {2} 次元グリッドがある.

{2} 枚の長方形のシートがグリッド上のどこかに置かれている. シートはセルの縁にそっていて, {2} 枚のシートが重なり合うことはない.

長方形領域を指定して, 領域が何枚のシートを内包するかを質問することができる. {200} 回以下の質問で, このシートの位置を特定せよ.

解法

二分探索というのはすぐ分かるけどデバッグ難しい.

まず, シートが {2} 枚含まれていると大変なので, どのあたりに {1} 枚あるかを見つける. {2} 枚のシートの位置関係を考えると, グリッドをある列か行で直線で分断することが可能. この位置を適当に二分探索して見つける.

分断したら, それぞれのシートを二分探索で見つけるだけ.

ソース

#include <bits/stdc++.h>

using namespace std;

struct Rect
{
  int x1, y1, x2, y2;
};

int N;
map< tuple< int, int, int, int >, int > dp;

int check(int x1, int y1, int x2, int y2)
{
  if(dp.count(tie(x1, y1, x2, y2))) return (dp[tie(x1, y1, x2, y2)]);
  cout << "?" << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
  int k;
  cin >> k;
  return (dp[tie(x1, y1, x2, y2)] = k);
}

Rect getRect(int x1, int y1, int x2, int y2)
{
  Rect rect;
  int left = x1, right = x2;
  while(right - left > 0) {
    int mid = (left + right) / 2;
    if(check(x1, y1, mid, y2) == 0) left = mid + 1;
    else right = mid;
  }
  rect.x2 = left;
  left = y1, right = y2;
  while(right - left > 0) {
    int mid = (left + right) / 2;
    if(check(x1, y1, x2, mid) == 0) left = mid + 1;
    else right = mid;
  }
  rect.y2 = left;
  left = x1, right = x2;
  while(right - left > 0) {
    int mid = (left + right + 1) / 2;
    if(check(mid, y1, x2, y2) == 0) right = mid - 1;
    else left = mid;
  }
  rect.x1 = left;
  left = y1, right = y2;
  while(right - left > 0) {
    int mid = (left + right + 1) / 2;
    if(check(x1, mid, x2, y2) == 0) right = mid - 1;
    else left = mid;
  }
  rect.y1 = left;
  return (rect);
}

int main()
{
  Rect r1, r2;

  cin >> N;

  int left = 1, right = N;
  while(right - left > 0) {
    int mid = (left + right) / 2;
    if(check(1, 1, mid, N) == 0) left = mid + 1;
    else right = mid;
  }
  if(check(1, 1, left, N) == 1 && check(left + 1, 1, N, N) == 1) {
    r1 = getRect(1, 1, left, N);
    r2 = getRect(left + 1, 1, N, N);
  } else {
    left = 1, right = N;
    while(right - left > 0) {
      int mid = (left + right) / 2;
      if(check(1, 1, N, mid) == 0) left = mid + 1;
      else right = mid;
    }
    r1 = getRect(1, 1, N, left);
    r2 = getRect(1, left + 1, N, N);
  }

  cout << "! " << r1.x1 << " " << r1.y1 << " " << r1.x2 << " " << r1.y2 << " "
       << r2.x1 << " " << r2.y1 << " " << r2.x2 << " " << r2.y2 << endl;
}

C. Sonya and Problem Wihtout a Legend

問題概要

長さ {n(1 \le n \le 3\ 000)} の数列 {A_i} がある. 各要素を増減して狭義増加部分列にしたい. 要素を {±1} するごとにコストが {1} かかる. 最小コストを求めよ.

解法

典型っぽい. じょうしょうツリーなのでそれを貼るだけ(乱暴.

まず, 狭義増加(より大きい) だと大変なので 広義増加(以上) として考える. これは, {A_i - i} とすればよい.

あとは動的計画法でこの問題を解く.

{dp_{i,j}:=} {i} 番目の要素を値 {j} にするときの最小コスト

とすれば, この更新は, {dp_{i,j} = \min(dp_{i-1,k(\le j)}) + |A_i - j|}. {j} は座標圧縮すれば高々 {n} 個しかないので, {O(n^2)}.

ソース

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
  int N, A[3000];
  vector< int > nums;
  int64 dp[2][3000];

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] -= i;
    nums.push_back(A[i]);
  }
  sort(begin(nums), end(nums));
  nums.erase(unique(begin(nums), end(nums)), end(nums));

  fill_n(*dp, 2 * 3000, INF);
  auto& now = dp[0], & nxt = dp[1];
  now[0] = 0;

  for(int i = 0; i < N; i++) {
    int64 small = INF;
    for(int j = 0; j < nums.size(); j++) {
      small = min(small, now[j]);
      nxt[j] = small + abs(A[i] - nums[j]);
    }
    swap(now, nxt);
  }
  cout << *min_element(now, now + nums.size()) << endl;
}