Codeforces Round #377 (Div. 2)

二重辺連結成分分解を覚えた.

A. Buy a Shovel

${10}$ burle のコインを無限個と, ${r(1 \le r \le 9)}$ burle のコインを ${1}$ 個持っている. ${1}$ 個 ${k(1 \le k \le 1\ 000)}$ burle のシャベルを複数買うことによって, お釣りなしにしたい. このとき, 買うシャベルの個数の最小を求めよ.

解法

買うシャベルの個数 ${x}$ を全探索することにする. ${xk}$ を ${10}$ で割った余りが ${r}$ か ${0}$ のとき明らかにお釣りなしで購入できる.

このことより ${10k}$ のときは必ず購入できるので ${1 \le x \le 10}$ の間で買える個数を判定する.

${O(1)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 K, R;
  cin >> K >> R;

  int64 curr = K, ret = 1;
  while(!(curr % 10 == R || curr % 10 == 0)) {
    curr += K;
    ++ret;
  }

  cout << ret << endl;
}

B. Cormen — The Best Friend Of a Man

問題概要

${n(1 \le n \le 500)}$ 日間あって, ${i}$ 日目には ${b_i (0 \le a_i \le 500)}$ 移動することが計画されている.

どの連続する ${2}$ 日間をとっても移動距離が ${k(1 \le k \le 500)}$ 以上にするとき, 追加で移動する距離長の最小と, その時のそれぞれの日の移動距離を出力せよ.

解法

貪欲法.

${1, 2}$ 日目の区間で移動量が不足しているとき, ${1}$ 日目で補うよりも ${2}$ 日目で補ったほうが良い.

このあと, ${(2, 3)}$ 日目の区間で移動量が不足している時, ${2}$ 日目で補うよりも ${3}$ 日目で補ったほうが良い.

同じように ${(n - 1, n)}$ 日目の区間まで成立する.

よって, ${1}$ 日目から順に見たとき, 不足時に後の日に足す操作を繰り返せばその結果が最適である.

${O(n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, K, A[500];

  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }

  int ret = 0;
  for(int i = 1; i < N; i++) {
    int get = max(0, K - A[i - 1] - A[i]);
    ret += get;
    A[i] += get;
  }

  cout << ret << endl;
  for(int i = 0; i < N; i++) {
    cout << A[i] << " ";
  }
  cout << endl;
}

C. Sanatorium

問題概要

何日か静養地で過ごし, 朝食, 昼食, 夕食をそれぞれ ${b, d, s (0 \le b, d, s \le 10^{18}, b + d + s \ge 1)}$ ずつ食べた. 静養地に出入りするタイミングは朝食前, 昼食前, 夕食前のいずれかである.

最小で食事を何回食べ逃したか求めよ.

解法

${b, d, s}$ のうち最大値を ${max}$ とする.

例えば ${max}$ が朝食だったとすると, 静養地に入るタイミングは朝食前と考えて良い. 出るタイミングは朝食前と昼食前と夕食前 ${3}$ 通り考えられ, それぞれ以下の回数となる.

${max, max, max}$ .
${max, max, max - 1}$ .
${max, max - 1, max - 1}$ .

この関係は朝食以外でも成立することが容易に分かる.

それぞれの食事の回数は上の ${3}$ ケースのみが認められるので, ${b, d, s}$ すべての差が ${1}$ になるようにするために加える最小和を計算すれば良い.

${O(1)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  long long A, B, C;
  cin >> A >> B >> C;
  long long big = max({A, B, C});
  cout << max(0LL, big - A - 1) + max(0LL, big - B - 1) + max(0LL, big - C - 1) << endl;
}

D. Exams

問題概要

${n(1 \le n \le 10^5)}$ 日間の試験期間がある. 試験期間の間に ${m(1 le m \le 10^5)}$ 個すべての教科の試験に合格する必要がある.

${i}$ 日目には試験 ${d_i(0 \le d_i \le m)}$ が行われる( ${d_i = 0}$ のときその日に試験は行われない). また教科 ${i}$ に合格するためには事前に丸 ${a_i(0 \le a_i \le 10^5)}$ 日勉強しなければならないことが分かっている.

それぞれの日で, その日に行われる試験を受けるか, 何かの試験に合格するための勉強をすることができる. 勉強する場合, ${1}$ 日で ${1}$ 種類の教科しか勉強はできないが順序は連続でなくても良い.

すべての教科に合格できるのであれば, そのときの最短日数を求めよ.

解法

${x}$ 日目までに合格できるとき, ${x + 1}$ 日目以降では必ず合格できるので, 解 ${x}$ を二分探索できる.

${x}$ 日目までに合格できるかの判定を考える.

各教科において ${[1, x]}$ 日目の区間で現れる最後の試験を受けるのが最適. このことによって勉強できる日と試験を受ける日は貪欲に決定できる.

あとはすべての教科について, 最後の試験以前に必要日数勉強できるかを見ればよいので ${O(n + m)}$ で判定できる.

総計算量は ${O((n + m) \log n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

int N, M, D[100000], A[100000];

bool last[100000];
int able[100000];

bool check(int right)
{
  memset(last, false, sizeof(last));
  memset(able, -1, sizeof(able));

  for(int i = right; i >= 0; i--) {
    if(~D[i]) {
      if(last[D[i]]++) continue;
      able[i] = D[i];
    }
  }

  for(int i = 0; i < M; i++) {
    if(!last[i]) return(false);
  }

  long long cost = 0;
  for(int i = right; i >= 0; i--) {
    if(~able[i]) cost += A[able[i]];
    else cost = max(0LL, cost - 1);
  }

  return (cost == 0);
}

int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%d", &D[i]);
    --D[i];
  }
  for(int i = 0; i < M; i++) {
    scanf("%d", &A[i]);
  }

  if(!check(N - 1)) {
    cout << -1 << endl;
  } else {
    int low = 1, high = N - 1;
    while(high - low > 0) {
      int mid = (low + high) >> 1;
      if(check(mid)) high = mid;
      else low = mid + 1;
    }
    printf("%d\n", low + 1);
  }
}

E. Sockets

問題概要

${n(1 \le n \le 200\ 000)}$ 個のコンピュータがありそれぞれの電力消費量は ${p_i(1 \le p_i \le 10^9)}$ である.

また ${m(1 \le m \le 200\ 000)}$ 個の受け口がありそれぞれ電力供給量 ${s_j(1 \le s_j \le 10^9)}$ はである.

任意の受け口にアダプタを指すことが出来る. またアダプタは直列に何個か指すことが出来る. アダプタを指すと, 現在の電力供給量を ${x}$ とすると ${\lceil x / 2 \rceil}$ になる.

電力供給量と電力消費量が等しい受け口 ${1}$ 個に対しコンピュータ ${1}$ 台を接続することができる. アダプタを何個か使うことによって接続できる数の最大値を出力せよ. また, その時のアダプタの数の最小値と接続状況を出力せよ.

解法

受け口には, アダプタを ${\log s_j}$ 個以上接続しても供給量が ${1}$ のまま変化しなくなるので, アダプタはそれ以上の個数を接続する必要はない.

またアダプタをつけると受け口の電力供給量は一様に減少するので, コンピュータの電力消費量が大きいものは早めに受け口と接続しておきたい気持ちになる.

以上のことを考えると次が成立してそれが解となる.

まだ接続されていない受け口全てにアダプタを ${1}$ 個接続する.
まだ接続されていないコンピュータのうち接続できる受け口があればそれと接続する. あるかどうかの判定に二分探索を使えば良い.

(日本語が怪しい)

計算量は ${O(m \log p_i \log n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M;
  set< pair< int, int > > P;
  int S[200000];
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    int p;
    scanf("%d", &p);
    P.emplace(p, i);
  }
  for(int i = 0; i < M; i++) scanf("%d", &S[i]);


  int Pans[200000], Qans[200000];
  memset(Pans, -1, sizeof(Pans));
  memset(Qans, -1, sizeof(Qans));
  int ret = 0, sum = 0;

  for(int i = 30; i >= 0; i--) {
    for(int j = 0; j < M; j++) {
      if(~Qans[j]) continue;
      if(i != 30) S[j] = (S[j] + 1) >> 1;
      auto p = P.lower_bound({S[j], -1});
      if(p == P.end() || p->first != S[j]) continue;
      Qans[j] = 30 - i;
      Pans[p->second] = j;

      P.erase(p);
      ++ret;
      sum += 30 - i;
    }
  }

  printf("%d %d\n", ret, sum);
  for(int i = 0; i < M; i++) {
    printf("%d ", max(Qans[i], 0));
  }
  puts("");
  for(int i = 0; i < N; i++) {
    printf("%d ", Pans[i] + 1);
  }
  puts("");
}

F. Tourist Reform

問題概要

${n(2 \le n \le 400\ 000)}$ 頂点 ${m(1 \le m \le 400\ 000)}$ 辺の連結で自己辺を持たないグラフが与えられる. ${i}$ 番目の辺は頂点 ${u_i}$ と ${v_i}$ を結んでいる.

すべての頂点に移動可能な方向を割り当てる. 任意の頂点から移動可能な頂点数の最小値を最大化するとき, その頂点数とそれぞれのの辺の向きを出力せよ.

解法

二重辺連結成分分解.

二重辺連結成分の頂点数の最大値が解. 最小の二重辺連結成分を考えるとこの成分はそれより大きい二重辺連結成分に流し込む必要があって, これを繰り返すと結果的に最大の二重辺連結成分に流し込まれる.

f:id:ei1333:20161019150603p:plain

(図を見ても分かる通り, 最大の二重辺連結成分に流し込む以外の方法で移動可能な頂点の最小値を最大にする方法はなさそう.)

二重辺連結成分分解して連結成分をつぶして橋だけを見ると一般に木になる. 最大の二重辺連結成分から dfs して, それぞれの橋が最大の連結成分に向かう向きになるようにすればよい.

各二重辺連結成分ではループを適当に dfs などで作っておいて任意の頂点間を移動可能にしておく.

計算量は ${O(n + m \log m)}$ . 本質部分は ${O(n + m)}$ だけど.

ソース

#include <bits/stdc++.h>

using namespace std;

struct UnionFind
{
  vector< int > data;

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

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }

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


struct BiconnectedComponents
{
  UnionFind uf;
  vector< vector< int > > g, tree;
  vector< pair< int, int > > edges, bridge;
  vector< int > used, ord, low, comp;

  BiconnectedComponents(size_t v) : uf(v), g(v), used(v, 0), comp(v), ord(v), low(v)
  {
  }

  void add_edge(int x, int y)
  {
    g[x].push_back(y);
    g[y].push_back(x);
    edges.push_back(minmax(x, y));
  }

  void dfs(int idx, int& k, int par = -1)
  {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];

    for(auto& to : g[idx]) {
      if(!used[to]) {
        dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        if(ord[idx] >= low[to]) uf.unite(idx, to);
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  size_t size()
  {
    return (g.size());
  }

  void build()
  {
    build(tree);
  }

  void build(vector< vector< int > >& t)
  {
    int kk = 0;
    dfs(0, kk);

    int ptr = 0;
    vector< int > cc(g.size());
    for(int i = 0; i < g.size(); i++) {
      if(i == uf.find(i)) cc[i] = ptr++;
    }

    t.resize(ptr);
    for(int i = 0; i < g.size(); i++) {
      comp[i] = cc[uf.find(i)];
    }
    for(auto& e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      t[x].push_back(y);
      t[y].push_back(x);
    }
  }

  void orr(int, int&, int par = -1);
};

map< pair< int, int >, int > vv;
vector< pair< int, int > > gg;
int v[400000];

void BiconnectedComponents::orr(int idx, int& k, int par)
{
  v[idx] = k++;
  for(int to : g[idx]) {
    if(to == par) continue;
    if((*this)[idx] == (*this)[to]) {
      if(~v[to]) {
        if(v[to] < v[idx]) gg.emplace_back(idx, to);
      } else {
        gg.emplace_back(idx, to);
        orr(to, k, idx);
      }
    } else {
      if(v[to] == -1) {
        gg.emplace_back(to, idx);
        orr(to, k, idx);
      }
    }
  }
}

int main()
{
  int N, M, Q;
  scanf("%d %d", &N, &M);
  BiconnectedComponents bc(N);
  for(int i = 0; i < M; i++) {
    int X, Y;
    scanf("%d %d", &X, &Y);
    bc.add_edge(--X, --Y);
    vv[minmax(X, Y)] = i;
  }

  vector< vector< int > > tree;
  bc.build(tree);
  vector< int > sz(tree.size(), 0), idx(tree.size());
  for(int i = 0; i < N; i++) sz[bc[i]]++;
  int p = *max_element(begin(sz), end(sz));
  memset(v, -1, sizeof(v));
  int k = 0;
  for(int i = 0; i < N; i++) {
    if(sz[bc[i]] == p) {
      bc.orr(i, k);
      break;
    }
  }
  printf("%d\n", p);
  vector< pair< int, int > > ans(M);
  for(auto& e : gg) ans[vv[minmax(e.first, e.second)]] = e;
  for(int i = 0; i < M; i++) {
    printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
  }
}

にゃんぱすー

ei1333の日記

ぺこい

Codeforces Round #377 (Div. 2)

A. Buy a Shovel

解法

ソース

B. Cormen — The Best Friend Of a Man

問題概要

解法

ソース

C. Sanatorium

問題概要

解法

ソース

D. Exams

問題概要

解法

ソース

E. Sockets

問題概要

解法

ソース

F. Tourist Reform

問題概要

解法

ソース