Codeforces Round #344 (Div.2)

寝ぼけてたのかよくわからないことになってしまった。(普通に実力がないだけ
A, Bを解いて2完。Cは落ちた。
1709 -> 1707(-2)。単調減少の開始。

A. Interview

問題概要

f(x, l, r) を x[l, r] の区間のORの値と定義する.
2 つの長さ N(1 ≦ N ≦ 1 000) の数列 a と b がある．l, r を適当に定めて, f(a, l, r) + f(b, l, r) を最大化せよ.

解法

N が 1000 以下なので, O(N^2) で全通り試せる. ので試す.
(実際は OR なので, 全部の区間をとるのが最大値なんだけど)

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int main()
{
  int64 N, A[1000], B[1000];
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for(int i = 0; i < N; i++) {
    cin >> B[i];
  }
  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    int64 AA = 0, BB = 0;
    for(int j = i; j < N; j++) {
      AA |= A[j];
      BB |= B[j];
      ret = max(ret, AA + BB);
    }
  }
  cout << ret << endl;
}

B. Print Check

問題概要

縦 n × 横 m (1 ≦ n, m ≦ 5000) の二次元グリッドがある. 最初は全てのマスが 0 で塗られている. 以下のクエリが k (1 ≦ k ≦ 100 000) 個与えられるので, すべて処理し, 最終的な盤面を求めよ.

Ri 行目をすべて Ai で塗る(上書き)

Ci 列目をすべて Bi で塗る(上書き)

解法

それぞれのセルごとに考えると. 分かりそう.
それぞれのクエリは上書きなので, そのマスに対して最終的に操作された色になるのは自明.
よって行別と列別それぞれに, 一番最後のクエリの色を保存しておけばこれはよさそう.

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int yoko[5000], yokoidx[5000];
int tate[5000], tateidx[5000];
int main()
{
  int W, H, K;
  cin >> H >> W >> K;
  for(int i = 1; i <= K; i++) {
    int A, B, C;
    cin >> A >> B >> C;
    --B;
    if(A == 1) {
      yoko[B] = C;
      yokoidx[B] = i;
    } else {
      tate[B] = C;
      tateidx[B] = i;
    }
  }

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(j > 0) cout << " ";
      if(yokoidx[i] < tateidx[j]) {
        cout << tate[j];
      } else {
        cout << yoko[i];
      }
    }
    cout << endl;
  }
}

C. Report

問題概要

長さ N の数列 A に対して, 以下のような数列を操作するクエリが与えられる. 最終的な数列 A を求めよ.

最初から Ri 個までの区間を昇順ソート

最初から Ri 個までの区間を降順ソート

解法

いろいろ考えたんだけど, 前問からの流れ的に, これもどうせ最後のクエリしか影響されないだろうという感じになる.
まず, max{Ri} 個より右の数列は不変なので, そのままということで例外処理.
それより左側は, 後ろから順に決めていけば良い. その要素に対して, 最後にどういうソートをしたかを保存しておくと, 残っている数値の中で最大か最小どちらかになる(日本語が難しい.

ソース

本番はなんか T[] の配列の大きさが 1 個足りなくてダメだったよね(何考えて 1-indexed にしたんだろ). multiset じゃなくても deque でできるよね(1.5 secだったので危うい.

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;


int main()
{
  int N, M, A[200005];
  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  int Reach = 0, T[200005], L[200005] = {};
  for(int i = 1; i <= M; i++) {
    int R;
    cin >> T[i] >> R;
    Reach = max(Reach, R);
    L[R - 1] = i;
  }
  for(int i = N - 2; i >= 0; i--) {
    L[i] = max(L[i], L[i + 1]);
  }

  int ptr = 0;
  int Array[200005];

  multiset< int > used;
  for(int i = N - 1; i >= Reach; i--) {
    Array[i] = A[i];
  }
  for(int i = 0; i < Reach; i++) {
    used.insert(A[i]);
  }
  for(int i = Reach - 1; i >= 0; i--) {
    if(T[L[i]] == 2) {
      Array[i] = *used.begin();
      used.erase(used.begin());
    } else {
      Array[i] = *--used.end();
      used.erase(--used.end());
    }
  }

  for(int i = 0; i < N; i++) {
    if(i > 0) cout << " ";
    cout << Array[i];
  }
  cout << endl;
}

このあと E やってたんだけど, 解けるはずないよね....

ei1333の日記

ぺこい

Codeforces Round #344 (Div.2)

A. Interview

問題概要

解法

ソース

B. Print Check

問題概要

解法

ソース

C. Report

問題概要

解法

ソース