Codeforces Round #346 (Div. 2)

ABCDEで5完. 1661 -> 1763(+102). f:id:ei1333:20160331130033p:plain なんか山登り法してそう.

A. Round House

問題概要

円環の経路があり, その経路上に 1 から N までの整数が振られている. N と 1 は隣接している.
Vasya は番号 a から散歩する. b > 0 のとき, 番号が増加する方向に b だけ移動し, b < 0 のとき, 番号が減少する方向に |b| だけ移動する. 移動後 Vasya がいる番号を答えよ.

解法

計算しても出るらしいけど, シミュレーションしても間に合う.
b が 0 になるまで移動を繰り返すだけ.
O(B).

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;

int main()
{
  int N, A, B;
  cin >> N >> A >> B;
  if(B >= 0) {
    while(B > 0) {
      A++;
      if(A == N + 1) A = 1;
      --B;
    }
  } else {
    B = -B;
    while(B > 0) {
      A--;
      if(A == 0) A = N;
      --B;
    }
  }  
  cout << A << endl;
}

B. Qualifying Contest

問題概要

2人チームを決めるために M 個の団体, あわせて N 人で予選をした.
それぞれの所属する団体の番号(1 〜 M)と, 予選の得点(0 〜 800の範囲)が分かっている.
団体ごとに, 予選の得点上位 2 人でチームを組むが, 上位 3 人以上が同じ得点だと困る.
団体ごとに, チームが一意に定まればそれぞれの個人名, 定まらなければ '?' を出力せよ.

解法

微妙に英語が長くてReading面倒.
団体ごとにわけて考える(それはそう.
ソートして得点を見るだけ.得点の降順に 2 番目と 3 番目の得点が同じなら '?'. O(NlogN).

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;

int main()
{
  int N, M;
  cin >> N >> M;
  vector< pair< int, string > > regions[100000];
  for(int i = 0; i < N; i++) {
    string S;
    cin >> S;
    int x, y;
    cin >> x >> y;
    regions[--x].push_back({y, S});
  }
  for(int i = 0; i < M; i++) {
    sort(regions[i].rbegin(), regions[i].rend());
    if(regions[i].size() == 2) {
      cout << regions[i][0].second << " " << regions[i][1].second << endl;
    } else {
      if(regions[i][1].first == regions[i][2].first) {
        cout << "?" << endl;
      } else {
        cout << regions[i][0].second << " " << regions[i][1].second << endl;
      }
    }
  }
}

C. Tanya and Toys

問題概要

番号 1 〜 10^9 までの 10^9 種類のおもちゃがある. 番号 i のおもちゃの費用は i である.
費用 m(≦ 10^9) 以内でなるべく多くの種類のおもちゃを買いたい. その種類数を求めよ.
但し, おもちゃ ${a_1, a_2, ..., a_n}$ は持っているので買えない.

解法

安いおもちゃから順に買うけど, 既に持っているおもちゃは買わない. みたいな貪欲.
貪欲が成り立つ理由は自明. O(NlogN).

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;

int main()
{
  int N, M, A[100000];

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

  int ptr = 0;

  bool first = false;
  vector< int > nums;

  for(int i = 1; M - i >= 0; i++) {
    if(ptr < N && A[ptr] == i) {
      ++ptr;
      continue;
    }
    M -= i;
    nums.push_back(i);
  }
  cout << nums.size() << endl;
  for(int i = 0; i < nums.size(); i++) {
    if(first++) cout << " ";
    cout << nums[i];
  }
  cout << endl;
}

D. Bicycle Race

問題概要

f:id:ei1333:20160331122125p:plain
のようなものがある. それぞれの頂点は座標で与えられる.
頂点を曲がらない時, 池に落ちる地点の個数を求めよ(上図では(1, 1)の1 箇所).

解法

直線を進行方向に伸ばして, 池に突っ込めば(=多角形内に入れば) ダメ.
手元に幾何ライブラリがあったのでそれを貼って, Cointains() した. O(N^2).

ソース

幾何ライブラリは略.

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin >> N;
  Geometory::Polygon pl(N);
  for(int i = 0; i < N; i++) {
    cin >> pl[i];
  }
  cin >> pl[0];

  int ret = 0;
  for(int i = 0; i < N; i++) {
    int px = curr(pl, i).x, py = curr(pl, i).y;
    int nx = next(pl, i).x, ny = next(pl, i).y;
    double cx, cy;
    if(px == nx) {
      cx = nx;
      if(py < ny) cy = 0.5 + ny;
      else       cy = -0.5 + ny;
    } else {
      cy = ny;
      if(px < nx) cx = 0.5 + nx;
      else       cx = -0.5 + nx;
    }
    if(Geometory::Contains(pl, Geometory::Point(cx, cy))) ++ret;
  }
  cout << ret << endl;
}

E. New Reform

問題概要

N 頂点 M 無向辺の自己辺や多重辺を含まないグラフ(連結とは限らない)が与えられる.
それぞれの辺を任意の向きに定めて有向辺にする.
入次数が0の頂点の数の最小値を求めよ.

解法

まず, 辺の次数が 0 個の頂点は, 一意に移動できない頂点.
辺の次数が 1 個の頂点は, その辺は自身への向きにしないといけないのでする. その辺は使えなくする. すると連続的に, 辺の次数が 1 個の頂点や 0 個の頂点が生えてくるので, bfsっぽく処理する.
辺の次数が 2 個以上の頂点は, なんか適当にやってれば次数が0の頂点は生えなさそうなので何もしない(ここら辺は適当.
O(N + MlogM).

ソース

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

int main()
{
  int N, M;
  set< pair< int, int > > graph[100000];
  bool uped[100000] = {};

  queue< int > que;

  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    graph[x].insert({y, i});
    graph[y].insert({x, i});
  }

  int ret = 0;
  for(int i = 0; i < N; i++) {
    if(graph[i].size() == 0) {
      ++ret;
      uped[i] = true;
    } else if(graph[i].size() == 1) {
      que.push(i);
    }
  }

  while(!que.empty()) {
    int v = que.front(); que.pop();
    if(graph[v].empty()) {
      if(uped[v]++) continue;
      ++ret;
    } else {
      auto p = *graph[v].begin();
      uped[v] = true;
      graph[v].erase(graph[v].begin());
      graph[p.first].erase({v, p.second});
      if(graph[p.first].size() <= 1) que.push(p.first);
    }
  }
  cout << ret << endl;
}

F. Polycarp and Hay

問題概要

M × N (≦ 1000) のセルから成る長方形のテーブルがある.
それぞれのセルは倉庫であり, 干し草が大きさ $a_{i, j}$ で生えている.
この状態から, 干し草を任意の量だけ取り除いて, 次の条件に沿うようにする必要がある.

干し草の総量は k(≦10^18).
全てのストック(個数が 0 ではないセル)の干し草の大きさが等しくなるようにする.
少なくとも 1 つのストックの大きさは初期状態と同じ.
ストックは連結.

可能なら 'YES' と共にその盤面, 不可能なら 'NO' を出力せよ.

解法

例えば, 全てのストックの大きさを x(k の約数) に揃えるとする.
するとこの問題は, $a_{i, j}$ ≧ x のセルを連結であるように x / k 個以上選択できるかという問題に帰着する.
選択するセルの候補数は, x が減少するにしたがって単調増加なので, x を大きい方から順に試していくとよさそう.
すると, セルの追加は, 既存の連結成分に $a_{i, j}$ を追加するだけなので, UnionFind でやると楽.
$a_{i, j}$ が k の約数のときだけ, その連結成分の大きさが x / k 個以上かどうか見てそうならそれとなる.
O(NM(logNM + α))

本番は, x / k 個を適当に選択するフェーズで実装ミスしたよね><. 幅すら書けない.

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
struct UnionFindTree
{
  vector< int > data;
  UnionFindTree(int sz)
  {
    data.assign(sz, -1);
  }
  int find(int k)
  {
    if(data[k] < 0) return(k);
    return(data[k] = find(data[k]));
  }
  int size(int k)
  {
    return(-data[find(k)]);
  }
  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }
};
#define int long long
int N, M;
int64 K;
int A[1000][1000];
const int vy[] = {0, 1, 0, -1}, vx[] = {1, 0, -1, 0};

inline int get(int y, int x)
{
  return(y * M + x);
}

signed main()
{

  scanf("%I64d %I64d %I64d", &N, &M, &K);
  UnionFindTree uftree(N * M);
  vector< pair< int64, pair< int, int > > > pts(N * M);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      scanf("%I64d", &A[i][j]);
      pts[get(i, j)] = {A[i][j], {i, j}};
    }
  }
  sort(pts.rbegin(), pts.rend());
  for(auto e : pts) {
    int i = e.second.first, j = e.second.second;
    for(int k = 0; k < 4; k++) {
      int ni = i + vy[k], nj = j + vx[k];
      if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
      if(A[i][j] <= A[ni][nj]) uftree.unite(get(i, j), get(ni, nj));
    }

    if(K % e.first == 0) {
      int64 mul = K / e.first;
      if(uftree.size(get(i, j)) >= mul) {
        printf("YES\n");

        queue< pair< int, int > > que;
        int load[1000][1000] = {{}};
        que.push({i, j});
        while(!que.empty()) {
          auto p = que.front(); que.pop();
          if(load[p.first][p.second] > 0) continue;
          if(mul == 0) break;
          --mul;
          load[p.first][p.second] = e.first;
          for(int k = 0; k < 4; k++) {
            int ni = p.first + vy[k], nj = p.second + vx[k];
            if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
            if(A[i][j] <= A[ni][nj]) {
              if(load[ni][nj] > 0) continue;
              que.push({ni, nj});
            }
          }
        }
        for(int a = 0; a < N; a++) {
          bool first = false;
          for(int b = 0; b < M; b++) {
            if(first++) putchar(' ');
            printf("%I64d", load[a][b]);
          }
          puts("");
        }
        exit(0);
      }
    }
  }
  puts("NO");
}

ei1333の日記

ぺこい

Codeforces Round #346 (Div. 2)

A. Round House

問題概要

解法

ソース

B. Qualifying Contest

問題概要

解法

ソース

C. Tanya and Toys

問題概要

解法

ソース

D. Bicycle Race

問題概要

解法

ソース

E. New Reform

問題概要

解法

ソース

F. Polycarp and Hay

問題概要

解法

ソース