AtCoder Grand Contest 014 - ei1333の日記

2297->2328(+31). 橙が見えてきた? 見えてこないね.

A - Cookie Exchanges

agc014.contest.atcoder.jp

解法

エスパーその ${1}$ .

普通にシミュレーションすれば通る.

最小と最大の差が ${\frac {1} {2}}$ になっていることを考えると ${O(\log n)}$ らしい.

ソース

なんか最初見て, 式書いたけど全然わからなかったのでとばした(ア. 無理, 非自明.

300点問題なので自明を書くのはそれはそうだね…

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{

  int A, B, C;
  cin >> A >> B >> C;
  int a = A, b = B, c = C;
 
  int cost = 0;
 
  while(a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
    int latte = a / 2;
    int malta = b / 2;
    int beet = c / 2;
    a = malta + beet;
    b = latte + beet;
    c = latte + malta;
 
    ++cost;
    if(A == a && b == B && c == C) {
      cout << -1 << endl;
      return (0);
    }
  }
 
  cout << cost << endl;
}

B - Unplanned Queries

agc014.contest.atcoder.jp

解法

エスパーその ${2}$ .

エスパーすると, ある頂点が現れた回数が奇数ならダメで, すべて偶数なら良いことがわかる.

ソース

無理すぎる. 不可能. 最初, わからなかったので飛ばした(全部の問題飛ばしそう.

考えても分からなかったので解いてる人数と時間を考えて, それらしい解法を生成した.

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

int main()
{
  int N, M;
  int G[100000] = {};
 
  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    ++G[a];
    ++G[b];
  }

  for(int i = 0; i < N; i++) {
    if(G[i] & 1) {
      cout << "NO" << endl;
      return (0);
    }
  }
  cout << "YES" << endl;
}

C - Closed Rooms

agc014.contest.atcoder.jp

解法

移動を ${K}$ 回
壁を ${K}$ 個消す

だと難しいので

壁を ${K}$ 個消す
移動を ${K}$ 回

を考える. これはほとんど自明で, 2. の移動経路にある壁は必ず消すことができて, 壁は考えなくていいことがわかる.

また, 壁を考えなくて良いので, 上下左右直線に進んで最も近いところに移動するのが最適.

よって, 最初の ${1}$ ステップ目について, 壁を消さずに移動を ${K}$ 回行ったあと, 2.1.の順で考えれば良いので, えいってやる.

ソース

やっと僕が分かる問題が出てきた.

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1 << 30;
 
int vy[] = {0, 1, 0, -1}, vx[] = {1, 0, -1, 0};
 
 
int main()
{
  int H, W, K;
  string A[800];
  int sx, sy;
  int v[800][800];
  memset(v, -1, sizeof(v));
 
 
  cin >> H >> W >> K;
  for(int i = 0; i < H; i++) {
    cin >> A[i];
    for(int j = 0; j < W; j++) {
      if(A[i][j] == 'S') {
        sx = j;
        sy = i;
      }
    }
  }
 
  queue< pair< int, int > > que;
  que.emplace(sy, sx);
  v[sy][sx] = 0;
  while(!que.empty()) {
    auto p = que.front();
    que.pop();
    for(int i = 0; i < 4; i++) {
      int ny = p.first + vy[i], nx = p.second + vx[i];
      if(ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
      if(A[ny][nx] == '#') continue;
      if(~v[ny][nx]) continue;
      v[ny][nx] = v[p.first][p.second] + 1;
      que.emplace(ny, nx);
    }
  }
 
  int ret = INF;
 
  auto getCost = [&](int y, int x)
  {
    int res = INF;
    res = min(res, y);
    res = min(res, x);
    res = min(res, W - x - 1);
    res = min(res, H - y - 1);
    if(res < 0) throw (0);
    return (res);
  };
 
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(v[i][j] == -1) continue;
      int cost = v[i][j];
      if(cost > K) continue;
      ret = min(ret, (getCost(i, j) + K - 1) / K + 1);
    }
  }
 
  cout << ret << endl;
}

D - Black and White Tree

agc014.contest.atcoder.jp

解法

白は葉の親を塗りつぶす戦略が最適.

このあと, 黒は葉を塗りつぶさないと負けなので, 必ず葉を塗る必要がある.

葉が ${2}$ 枚以上あるときは, 同時に複数の葉を黒くできないので白が勝つことがわかる.

これが ${1}$ ステップで, この ${2}$ 頂点は最後の結果に影響しないので取り除く.

取り除くとまた木になる.

この操作を適当に繰り返すことを考えると, 頑張ってDFSすれば判定できる.

ソース

こういう漠然としてDFS苦手…

C<D<A<B だとおもうんだけど(過激派

#include <bits/stdc++.h>
 
using namespace std;
 
vector< int > g[114514];
 
int dfs(int idx, int par)
{
  int ret = 0;
  for(auto to : g[idx]) {
    if(to == par) continue;
    ret += dfs(to, idx);
  }
  if(ret >= 2) {
    cout << "First" << endl;
    exit(0);
  }
  return (ret ^ 1);
}
 
 
int main()
{
  int N;
  cin >> N;
  for(int i = 1; i < N; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if(dfs(0, -1)) cout << "First" << endl;
  else cout << "Second" << endl;
}

E - Blue and Red Tree

解法

${2}$ つの木のそれぞれの辺を青い辺と赤い辺とする.

ぐっと考察すると, ${n}$ 頂点が独立という状態から

異なる ${2}$ つの連結成分を繋ぐ青い辺と赤い辺を選んで併合する

という操作を繰り返して, 最終的に ${1}$ つの集合にできるかという問題に帰着できる.

「異なる ${2}$ つの連結成分を繋ぐ青い辺と赤い辺」がある連結成分を高速に求めれば良くて, これはマージテクとかを頑張れば効率的にできる.

ソース

これは解けなかった. 難しい(それはそう

#include <bits/stdc++.h>
 
using namespace std;
 
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);
    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;
  set< int > g[100000];
  cin >> N;
  queue< pair< int, int > > que;
  for(int i = 0; i < 2 * N - 2; i++) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    if(g[A].count(B)) que.emplace(A, B);
    g[A].emplace(B);
    g[B].emplace(A);
  }
  UnionFind tree(N);
  while(!que.empty()) {
    int a, b;
    tie(a, b) = que.front();
    que.pop();
    a = tree.find(a), b = tree.find(b);
    if(a == b) continue;
    if(g[a].size() > g[b].size()) swap(a, b);
    tree.unite(b, a);
    g[a].erase(b);
    g[b].erase(a);
    for(int to : g[a]) {
      g[to].erase(a);
      if(g[to].count(b)) que.emplace(to, b);
      else g[to].emplace(b), g[b].emplace(to);
    }
    g[a].clear();
  }
  if(tree.size(0) == N) cout << "YES" << endl;
  else cout << "NO" << endl;
}