ei1333の日記

ぺこい

Codeforces Beta Round #83 (Div. 1 Only)

よくわからないやが.

2 完だった.

A. Dorm Water Supply

codeforces.com

問題概要

{n(1 \le n \le 1000)} 頂点と {p(0 \le p \le n)} 本の有向辺からなるグラフが与えられる.

{i} 番目の辺は異なる頂点 {a_i} から {b_i} を結んでいて容量が {d_i(1 \le d_i \le 10^6)} である.

それぞれの頂点で, 入次数と出次数が {1} 以下であることが保証される.

入寺数が {1} の頂点から出次数が {1} の頂点にフローを流す. このときに通る辺の容量が流すフローの容量を上回ってはならない.

このとき考えられる全てのフローについて, 最大流を求めよ.

解法

連結成分ごとに独立なので分けて考える.

それぞれの連結成分は {1} 本のパスになるか変なやつになるので, パスになる連結成分について連結成分を結ぶ辺の容量の最小をとればよい.

ソース

なんかソート忘れてWAしてしまった.

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

int main()
{
  int N, P;
  bool in[1000] = {}, out[1000] = {};
  int a[1000], b[1000], c[1000];

  cin >> N >> P;
  UnionFind tree(N);
  for(int i = 0; i < P; i++) {
    cin >> a[i] >> b[i] >> c[i];
    --a[i], --b[i];
    tree.unite(a[i], b[i]);
    out[a[i]] = true;
    in[b[i]] = true;
  }

  int ret[1000];
  int latte[1000], malta[1000];
  fill_n(ret, 1000, INF);
  memset(latte, -1, sizeof(latte));
  memset(malta, -1, sizeof(malta));
  for(int i = 0; i < N; i++) {
    if(in[i] && !out[i]) latte[tree.find(i)] = i;
    if(out[i] && !in[i]) malta[tree.find(i)] = i;
  }
  for(int i = 0; i < P; i++) {
    int k = tree.find(a[i]);
    ret[k] = min(ret[k], c[i]);
  }
  vector< tuple< int, int, int > > vs;
  for(int i = 0; i < N; i++) {
    if(tree.find(i) == i) {
      if(~latte[i] && ~malta[i]) {
        vs.emplace_back(malta[i], latte[i], ret[i]);
      }
    }
  }

  cout << vs.size() << endl;
  sort(begin(vs), end(vs));
  for(auto &p : vs) {
    int x, y, z;
    tie(x, y, z) = p;
    cout << x + 1 << " " << y + 1 << " " << z << endl;
  }

}

B. Basketball Team

codeforces.com

問題概要

{m(1 \le m \le 1000)} 個の部署があって, 部署 {i} には {s_i(1 \le s_i \le 100)} 人が属している.

部署 {h(1 \le h \le m)} に Herr Wafa さんがいる.

この中から {n} 人無作為に取り出して {n} 人のグループを組む. ただし, Herr Wafa さんは必ず取り出される.

取り出される人について, {h} の部署の人が {1} 人以上含まれている確率を求めよ.

解法

適当にえい.

{n-1} 人が全て {h} 以外の部署である確率を求めて, それを {1} からえいする.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M, H, S[1000];

  cin >> N >> M >> H;

  --H;
  --N;
  int all = -1;

  for(int i = 0; i < M; i++) {
    cin >> S[i];
    all += S[i];
  }

  if(all < N) {
    cout << -1 << endl;
    return(0);
  }

  int beet = all - (S[H] - 1);
  double ret = 1.0;
  for(int i = 0; i < N; i++) {
    ret *= 1.0 * beet / all;
    --beet;
    --all;
  }
  cout << fixed << setprecision(10) << 1.0 - ret << endl;
}

C. Arrangement

codeforces.com

問題概要

{n(1 \le n \le 16)} 人がいて, それぞれの人には {1} から {n} の番号がふられている.

{n} 個ある椅子に, 以下の {m(0 \le m \le 100)} 個の条件を全て満たしつつ, 2001年には辞書順最小の順番で座る.

  • {a_i, b_i} 番目の椅子に座る人の番号を {x, y} とすると, {x \lt y} を満たす

1 年ごとに, 現在の次に辞書順最小な順番に席替えされる.

{y(2001 \le y \le 10^{18})} 年の席順を求めよ. 但し, 考えられる順番を全て消費した時 The times have changed を出力せよ.

解法

{16} とみたら bitdp をしたくなって, 実際の解法も bitdp.

まず条件を満たす席順を全て数え上げたい気持ちになる. この個数が, {y - 2001} 未満だったら全て消費あるいはもともと存在しない.

左から {i} 番目の席が現在確定しているか否かを bit で表すこととする. また, 確定させる順番は, 人の番号の昇順とする.

すると現在の状態 bit のときに, {i} 番目の席を見た時に座れるかどうかは, 席 {i} より若いほげみたいな条件が全て埋まっているかどうかで判定できる( {i} 番目の席を埋めるとその条件を満たせなくなるので(人の番号の昇順に埋めているので)).

辞書順最小を求めるフェーズは, なんか気合いで辞書順っぽく遷移を阻止していい感じのところを見つける雰囲気(は？). 番号が若い人から順にその人が位置 {j} 以前の椅子に座ると決め打ちして そこからまた同じDPをして, {y} 年っぽいところをみつける.

ソース

なんか辞書順最小を求めるのがむずかしかった.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int64 N, Y, M;
int bad[16];
int64 dp[1 << 16];
bool graph[16][16];

int64 rec(int bit)
{
  if(~dp[bit]) return (dp[bit]);
  if(bit == (1 << N) - 1) return (dp[bit] = 1);
  int64 ret = 0, dep = __builtin_popcount(bit);
  for(int i = 0; i < N; i++) {
    if((bit >> i) & 1) continue;
    if(bad[i] & bit) continue;
    if(!graph[i][dep]) continue;
    ret += rec(bit | (1 << i));
  }
  return (dp[bit] = ret);
}


int main()
{
  cin >> N >> Y >> M;
  Y -= 2001;
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    bad[--a] |= 1 << --b;
  }
  memset(graph, true, sizeof(graph));
  memset(dp, -1, sizeof(dp));
  if(Y >= rec(0)) {
    cout << "The times have changed" << endl;
  } else {
    for(int i = 0; i < N; i++) {
      int low = 0, high = N;
      while(high - low > 1) {
        int mid = (low + high) >> 1;
        for(int j = 0; j < N; j++) graph[i][j] = j < mid;
        memset(dp, -1, sizeof(dp));
        if(Y < rec(0)) high = mid;
        else low = mid;
      }
      for(int j = 0; j < N; j++) graph[i][j] = j < low;
      memset(dp, -1, sizeof(dp));
      Y -= rec(0);
      for(int j = 0; j < N; j++) graph[i][j] = j == low;

      cout << low + 1 << " ";
    }

    cout << endl;
  }

}