Codeforces Round #368 (Div. 2)

ABCDの4完. Cが苦手.

A. Brain's Photos

問題概要

${n \times m (1 \le n, m \le 100)}$ の行列で表される画像がある.

行列の各要素は 6 つの色のいずれかである. 白黒灰色以外を含まない画像を白黒と定義するとき, 与えられた画像が白黒か判定せよ.

解法

問題文の通り実装する.

ソース

目立つように black-and-white とか書いてあって, 灰色は白黒でないと思ってしまった. 1 Hacked...

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M;
  cin >> N >> M;
  bool other = false;
  while(N--) {
    for(int i = 0; i < M; i++) {
      char c;
      cin >> c;
      other |= (c != 'W' && c != 'B' && c != 'G');
    }
  }
  if(other) cout << "#Color" << endl;
  else cout << "#Black&White" << endl;
}

B. Bakery

問題概要

${n(1 \le n \le 10^5)}$ 個の街があって ${1}$ から ${n}$ まで番号が振られている. ${m(1 \le m \le 10^5)}$ 個の街 ${a_i, b_i(1 \le a_i, b_i \le n, a_i \ne b_i)}$ 間を結ぶ長さ ${l_i (1 \le l_i \le 10^9)}$ の双方向に通行できる道がはられている.

${k(0 \le k \le n)}$ 個の頂点 ${a_i(1 \le a_i \le n)}$ には小麦粉やさんがある.

小麦粉やさんが存在しない街のいずれかにパン屋さんをオープンしたいと考えた. ただし少なくとも ${1}$ つの小麦粉やさんを任意の経路で選択し互いに通信できる必要がある.

小麦粉やさんとの距離を最小にするようパン屋さんをオープンしたいとき, その経路の長さを求めよ. どこにもパン屋さんをオープンできないとき, ${-1}$ を出力せよ.

解法

小麦粉やさんに隣接しているいずれかの街にパン屋さんをオープンするのが最適. ${1}$ 個の辺を通るだけで通信可能になる.

すべての小麦粉やさんにおいて, 隣接していて小麦粉やさんが置かれていない街を結ぶ辺のうち最小をとればよい.

ソース

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

struct edge
{
  int to, cost;
};

int main()
{
  int N, M, K;
  vector< edge > graph[100000];
  bool f[100000] = {};

  scanf("%d %d %d", &N, &M, &K);

  while(M--) {
    int u, v, l;
    scanf("%d %d %d", &u, &v, &l);
    --u, --v;
    graph[u].push_back((edge){v, l});
    graph[v].push_back((edge){u, l});
  }
  while(K--) {
    int a;
    scanf("%d", &a);
    f[--a] = true;
  }

  int ret = INF;
  for(int i = 0; i < N; i++) {
    if(!f[i]) {
      for(auto& e : graph[i]) {
        if(f[e.to]) ret = min(ret, e.cost);
      }
    }
  }

  if(ret == INF) puts("-1");
  else printf("%d\n", ret);
}

C. Pythagorean Triples

問題概要

3 辺の長さが全て整数の直角三角形を考える.

任意の一辺の長さ ${l(1 \le l \le 10^9)}$ が与えられる. 残りの ${2}$ 辺の長さを ${n, k}$ とする. ${1 \le n, k \le 10^{18}}$ となるような直角三角形が存在するとき, ${n, k}$ を出力せよ. 存在しない時 ${-1}$ を出力せよ.

解法

あまりにわからないのでぐぐってしまった.

が現れるので. それを写すだけ(証明も上のサイトで...

${l \le 2}$ のとき解は存在しないので注意.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 N;
  cin >> N;

  if(N <= 2) {
    cout << -1 << endl;
  } else if(N % 2 == 1) {
    cout << (N * N - 1) / 2 << " " << (N * N + 1) / 2 << endl;
  } else {
    N /= 2;
    cout << N * N - 1 << " " << N * N + 1 << endl;
  }
}

D. Persistent Bookcase

問題概要

${n(1 \le n \le 10^3)}$ 段で幅 ${m(1 \le m \le 10^3)}$ の本棚がある. 最初, 本棚には何も入っていない.

以下の ${q(1 \le q \le 10^5)}$ 個のクエリが与えられるので, それぞれの操作の終了時に本棚に本が何冊あるか出力せよ.

${1\ i\ j}$ : ${i}$ 段目の棚で位置 ${j}$ に本が存在しない時本を入れる.
${2\ i\ j}$ : ${i}$ 段目の棚で位置 ${j}$ に本が存在する時本を取り除く.
${3\ i}$ : ${i}$ 段目の棚を反転する. 位置 ${j}$ に本が存在する時本を取り除き, 本が存在しない時本を入れる.
${4\ k}$ : ${k}$ 回目の操作後に本棚の状態を戻す.

解法

問題文中で永続データ構造の説明がされているので, 永続したくなるけど永続はしない.

この問題の特性として, クエリが先読みできて ${1}$ 回だけ戻す逆操作が容易ということがある.

解法は木を作って DFS.

${i}$ 回目の操作が終了したとする. この状態から本棚が操作されるのは ${i + 1}$ 番目以降の操作と, クエリ ${4\ i}$ が存在すればそれ以降の操作である.

操作 ${i}$ から操作 ${x_i}$ に操作を進める部分問題を解いて, またもとの状態 ${i}$ に戻すことはそのままであるので, それぞれの操作についてそれをすると解ける.

反転を ${O(m)}$ でやったので, ${O(mq)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;


int N, M, Q;
int T[100005], I[100005], J[100005];
char buff[64];
vector< int > graph[100005];
bool reef[1005][1005];
int ans[100005];
int sz;


void Solve(int idx)
{
  bool update = false;
  switch(T[idx]) {
    case 1:
      if(!reef[I[idx]][J[idx]]) {
        reef[I[idx]][J[idx]] = true;
        update = true;
        ++sz;
      }
      break;
    case 2:
      if(reef[I[idx]][J[idx]]) {
        reef[I[idx]][J[idx]] = false;
        update = true;
        --sz;
      }
      break;
    case 3:
      for(int i = 1; i <= M; i++) {
        if(reef[I[idx]][i]) --sz;
        else ++sz;
        reef[I[idx]][i] ^= 1;
      }
      break;
    default:
      break;
  }
  ans[idx] = sz;
  for(int to : graph[idx]) {
    Solve(to);
  }
  switch(T[idx]) {
    case 1:
      if(update) {
        reef[I[idx]][J[idx]] = false;
        --sz;
      }
      break;
    case 2:
      if(update) {
        reef[I[idx]][J[idx]] = true;
        ++sz;
      }
      break;
    case 3:
      for(int i = 1; i <= M; i++) {
        if(reef[I[idx]][i]) --sz;
        else ++sz;
        reef[I[idx]][i] ^= 1;
      }
      break;
    default:
      break;
  }
}

int main()
{
  fgets(buff, sizeof(buff), stdin);
  sscanf(buff, "%d %d %d", &N, &M, &Q);

  T[0] = 114514;

  for(int i = 1; i <= Q; i++) {
    fgets(buff, sizeof(buff), stdin);
    sscanf(buff, "%d %d %d", &T[i], &I[i], &J[i]);
    if(T[i] == 4) {
      graph[I[i]].push_back(i);
    } else {
      graph[i - 1].push_back(i);
    }
  }

  Solve(0);

  for(int i = 1; i <= Q; i++) {
    printf("%d\n", ans[i]);
  }
}

E. Garlands

問題概要

${n \times m(1 \le n, m \le 2000)}$ の ${2}$ 次元グリッドがある.

${k}$ 個の複数の電球からなるチェーンがグリッドに置かれている. ${i}$ 番目のチェーンの長さは, ${len_i(1 \le len_i \le 2000)}$ で, それぞれの電球は ${(i_{j}, j_{j})}$ に置かれている. それぞれの電球の喜び度は ${w_{j}(1 \le w_{j} \le 10^9)}$ である. 最初すべての電球は点灯している.

${q(1 \le q \le 10^6)}$ 個のクエリが時系列順に与えられるのでそれをすべて処理せよ.

${SWITCH\ i}$ : ${i(1 \le i \le k)}$ 番目のチェーンに属する電球のすべてについて, 点灯しているなら消灯, 消灯しているなら点灯させる.
${ASK\ x_1\ y_1\ x_2\ y_2}$ : 左上が ${(x_1, y_1)}$ , 右下が ${(x_2, y_2)}$ である長方形内に含まれる点灯している電球の喜び度の和を出力する. このクエリの数は ${2000}$ 個を超えない.

解法

チェーン別にわけて考えることとする.

チェーン ${a}$ を処理する. チェーン ${a}$ に関係するクエリは, ${SWITCH\ a}$ と ${ASK}$ クエリのみであるので, 前計算で取り出しておく.

時系列順に処理していって, チェーン ${SWTICH\ a}$ のとき足すフラグを反転させていけば, ${ASK}$ クエリが現れた時, そのチェーンについて足すかどうかは瞬時に分かる.

${SWITCH\ a}$ クエリは ${O(1)}$ で処理できることがわかるのでこれはよさそう.

チェーンについて足すのが難しくて, これについて考える. 長方形内の和を求める一般的なテクとして二次元累積和があるので, それを使いたい気持ちになる. 二次元累積和は以下のようなテクである. (塗り忘れ 1 箇所あります><)

f:id:ei1333:20160821151946p:plain

累積和の取り方で右下全体に + を足す操作は, 2 次元 BIT を使うと ${O(\log^2 nm)}$ でできる.

各々のチェーンについて最初に前計算で 2 次元 BIT を使って累積和を求めておく. このときの計算量は ${O(\max(len_i) \log nm)}$ . 各 ${ASK}$ クエリは, 4 箇所のセルの値を持ってくるだけ. よってこれを答えるクエリは, ${ASK}$ クエリの数を ${p(1 \le p \le 2000)}$ とおくと, ${O(p \log^2 nm)}$ でできる.

よって全体の計算量は, ${O(k (\max(len_i) + p) \log nm)}$ となってちょうど間に合う.

ソース

2次元BITなんてものがあったな

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

struct BinaryIndexedTree
{
  vector< int64 > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  int64 sum(int k)
  {
    int64 ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, int x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

struct BinaryIndexedTree2D
{
  vector< BinaryIndexedTree > data;

  BinaryIndexedTree2D(int W, int H)
  {
    data.resize(++W, BinaryIndexedTree(H));
  }

  int64 sum(int k, int y)
  {
    int64 ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k].sum(y);
    return (ret);
  }

  int64 add(int k, int y, int x)
  {
    for(++k; k < data.size(); k += k & -k) data[k].add(y, x);
  }
};

int N, M, K, Q;
vector< tuple< int, int, int > > lines[2000];
int x1[1000000], y1[1000000], x2[1000000], y2[1000000];
int64 ret[1000000];

int main()
{
  scanf("%d %d %d", &N, &M, &K);

  for(int i = 0; i < K; i++) {
    int p;
    scanf("%d", &p);
    while(p--) {
      int x, y, z;
      scanf("%d %d %d", &x, &y, &z);
      lines[i].emplace_back(x, y, z);
    }
  }

  vector< int > flip[2000];
  vector< int > query;

  scanf("%d", &Q);
  for(int i = 0; i < Q; i++) {
    char buff[64];
    scanf(" %s", buff);
    if(buff[0] == 'S') {
      int idx;
      scanf("%d", &idx);
      flip[--idx].push_back(i);
    } else {
      scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
      --x1[i], --y1[i];
      query.push_back(i);
    }
  }

  BinaryIndexedTree2D bit(N + 2, M + 2);
  for(int i = 0; i < K; i++) {
    for(auto& k : lines[i]) {
      int x, y, z;
      tie(x, y, z) = k;
      bit.add(x, y, z);
    }
    bool add = true;
    int a = 0, b = 0;
    while(a < query.size()) {
      if(b == flip[i].size() || query[a] < flip[i][b]) {
        const int j = query[a++];
        if(!add) continue;
        ret[j] += bit.sum(x2[j], y2[j]) - bit.sum(x2[j], y1[j]) - bit.sum(x1[j], y2[j]) + bit.sum(x1[j], y1[j]);
      } else {
        add ^= 1;
        ++b;
      }
    }
    for(auto& k : lines[i]) {
      int x, y, z;
      tie(x, y, z) = k;
      bit.add(x, y, -z);
    }
  }

  for(int i : query) {
    printf("%I64d\n", ret[i]);
  }
}

ei1333の日記

ぺこい

Codeforces Round #368 (Div. 2)

A. Brain's Photos

問題概要

解法

ソース

B. Bakery

問題概要

解法

ソース

C. Pythagorean Triples

問題概要

解法

ソース

D. Persistent Bookcase

問題概要

解法

ソース

E. Garlands

問題概要

解法

ソース