読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

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");
}