GCJ 2018 Round2 - ei1333の日記

ABCが通って393位.

A. Falling Balls

問題概要

${C(2 \le C \le 100)}$ 列の2次元グリッドがあって, 各列の一番上からボールを落下させる.

グリッドは '/', '\', '.' のいずれかから構成されて, '/' ならそこに落ちてきたボールは左の列に, '\' ならそこに落ちてきたボールは右の列に移動する. 他のボール同士は重なることができる.

一番下の ${i}$ 列目に到達したボールの個数は ${B_i}$ 個だった. 下の行と, 左右の列はすべて '.' で構成されていたことがわかっている. そのようなグリッドが存在するか判定し, 存在する時考えられる最小の行からなるグリッドの例を出力せよ.

解法

まず, 左右の列の ${B_i}$ が ${0}$ のとき, IMPOSSIBLE. 3秒考えるとそれ以外のときは必ず構成できることがわかる.

具体的な構成方法は, 左に落ちてくるボールの数から順番に調整する. その列に落ちてくるべきボールの列の範囲 ${[l, r)}$ がわかるので, 一番下のその列から斜め方向に適切な数だけ '\' と '/' を ${1}$ 本ずつ生やせば良い.

${O(TC^2)}$ .

#include<bits/stdc++.h>

using namespace std;

void beet() {
  int W, C[100];
  scanf("%d", &W);
  for(int i = 0; i < W; i++) {
    scanf("%d", &C[i]);
  }

  if(C[0] == 0 || C[W - 1] == 0) {
    puts("IMPOSSIBLE");
    return;
  }

  int t[110][110] = {{}};

  int l = 0;
  int pos = 1;
  for(int i = 0; i < W; i++) {
    if(C[i] == 0) continue;
    int r = l + C[i]; // [l, r)
    for(int j = 0; j < i - l; j++) {
      t[104 - j][i - j - 1] = 1;
      pos = max(pos, j + 2);
    }
    for(int j = 0; j < r - i - 1; j++) {
      t[104 - j][i + j + 1] = 2;
      pos = max(pos, j + 2);
    }
    l = r;
  }
  printf("%d\n", pos);
  for(int i = 0; i < pos; i++) {
    for(int j = 0; j < W; j++) {
      if(t[106 - pos + i][j] == 1) putchar('\\');
      else if(t[106 - pos + i][j] == 2) putchar('/');
      else putchar('.');
    }
    putchar('\n');
  }
}

int main() {
  int T;
  scanf("%d", &T);
  for(int i = 1; i <= T; i++) {
    printf("Case #%d: ", i);
    beet();
  }
}

B. Graceful Chainsaw Jugglers

問題概要

${R}$ 個の赤いチェーンソーと ${B(1 \le R, B \le 500)}$ 個の青いチェンソーがある. これを何人かで分け合うが, 次の条件を満たす必要がある.

すべての人は ${1}$ つ以上のチェーンソーを持つ必要がある.
ある人と赤の数も青の数がともに同数のチェーンソーを持っている人が存在してはならない.

最大で何人にチェーンソーを分け合えるか.

解法

なんか制約的にDPを疑う.

赤を ${k}$ 個と青を任意個のペアを作る前には, 赤を ${k-1}$ 個と青を任意個のペアを作っておいたほうがおとく.

そこで, 再帰関数 rec(k, r, b) を, 今までに赤を1人あたりの最大で ${k-1}$ 個使って, 赤が残り ${r}$ 個, 青が残り ${b}$ 個のときに得られる最大人数と定義する.

${k}$ 個の赤とペアリングする青は, ${0, 1, 2, 3, \dots}$ 個の順番にするのが最適なので, まあこれは赤の数を全探索して遷移させればできる.

複数テストケースが与えられるが, メモ化配列を毎回初期化せずに使い回せるので, 全体で ${O(R^2B \sqrt B +T \sqrt B)}$ くらいと見積もれば, 実際はもっと少なそうなので間に合う.

#include<bits/stdc++.h>

using namespace std;

int dp[505][505][505];

int rec(int blackcur, int black, int white) {
  if(~dp[blackcur][black][white]) return dp[blackcur][black][white];
  int ret = 0;
  for(int i = 1;; i++) {
    int blackrest = black - blackcur * i;
    int whiterest = white - i * (i - 1) / 2;
    if(blackrest < 0 || whiterest < 0) break;
    ret = max(ret, rec(blackcur + 1, blackrest, whiterest) + i);
  }
  return dp[blackcur][black][white] = ret;
}

void beet() {
  int x, y;
  scanf("%d %d", &x, &y);
  int ret = rec(1, x, y);
  for(int i = 1;; i++) {
    int whiterest = y - i * (i + 1) / 2;
    if(whiterest < 0) break;
    ret = max(ret, rec(1, x, whiterest) + i);
  }
  printf("%d\n", ret);
}

int main() {
  memset(dp, -1, sizeof(dp));
  int T;
  scanf("%d", &T);
  for(int i = 1; i <= T; i++) {
    printf("Case #%d: ", i);
    beet();
  }
}

C. Costume Change

問題概要

${N \times N(2 \le N \le 100)}$ のグリッドが与えられる. ${i}$ 行 ${j}$ 列目には ${A_{i, j} (-N \le A_{i,j} \le N, A_{i,j} \ne 0)}$ が書かれている.

次の操作がコスト ${1}$ でできる.

あるマスの符号を反転させる
あるマスの値を同符号の範囲で絶対値が ${1}$ 以上 ${N}$ 以下の数に変更する.

すべての行, 列をみたときに同じ値が存在しないようにしたい. このために必要な操作の最小回数を求めよ.

解法

貪欲は無理そうとなると, どうみてもフロー以外の選択肢は残されていないのでフローを考える.

変更するマスの数の最小化はつまり, 残すマスの数の最大化である. そこで, ${-N}$ から ${N}$ の値ごとに残すマスの数を最大化したい気持ちになるが, これは蟻本にも載っている一方に行, もう一方に列をおいた二部マッチングにより解ける.

使わなかったセルをどうしようかなーと思っていると, 適切に操作することでなんとなくコスト ${1}$ で変更できそうな気がしてきて, 変更できないと解ける問題には見えないので投げると通る(?).

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > dist, match;
  vector< bool > used, vv;

  Bipartite_Matching(int n, int m)
  {
    graph.resize(n);
    match.assign(m, -1);
    used.assign(n, false);
  }

  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
  }

  void bfs()
  {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a)
  {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }
};


void beet() {
  int N, X[100][100];
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      scanf("%d", &X[i][j]);
    }
  }
  int ret = 0;
  for(int i = -N; i <= N; i++) {
    Bipartite_Matching flow(N, N);
    for(int j = 0; j < N; j++) {
      for(int k = 0; k < N; k++) {
        if(X[j][k] == i) flow.add_edge(j, k);
      }
    }
    ret += flow.bipartite_matching();
  }
  cout << N * N - ret << endl;
}

int main() {
  int T;
  scanf("%d", &T);
  for(int i = 1; i <= T; i++) {
    printf("Case #%d: ", i);
    beet();
  }
}

D. Gridception

えーなんかたぶん誤読しているので(悲しいね