ei1333の日記

ぺこい

Codeforces Round #397 (Div. 1 + Div. 2 combined)

5完したけど, 解くのが遅いのでね….

222th. 2014->2068(+54).

A. Neverending competitions

解法

{n \% 2}.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  cin >> N;
  if(N % 2 == 0) {
    cout << "home" << endl;
  } else {
    cout << "contest" << endl;
  }
}

B. Code obfuscation

解法

文字列の先頭から, ab..z の順で現れるか見るだけ.

ソース

この辺は問題文を読むほうが時間がかかる.

#include <bits/stdc++.h>

using namespace std;

int main()
{
  string S;
  cin >> S;

  int num = 'a';
  bool killed[500] = {};
  for(int i = 0; i < S.size(); i++) {
    if(killed[i]) {
      continue;
    }
    if(S[i] != num) {
      cout << "NO" << endl;
      return (0);
    }
    for(int j = i; j < S.size(); j++) {
      if(num == S[j]) {
        killed[j] = true;
      }
    }
    ++num;
  }

  cout << "YES" << endl;
}

C. Table Tennis Game 2

問題概要

{2} 人でテニスをした.

各サーブでは, 勝者が {1} 点を得て敗者は何も得ない.

{1} セットは, 何サーブかで構成され最初に一方が {k} 点得るまで続く. セットが終わると得点がリセットされ, 新しいセットが始まる.

最終的に {2} 人が得た得点 {a, b(0 \le a, b \le 10^9, a + b \gt 0)} と {k(1 \le k \le 10^9)} が与えられるので, 矛盾があるか判定し, 矛盾がないなら考えられる最大セット数を求めよ.

解法

物理的にどちらか一方しか試合に勝てないとき, 勝つ側の点を {k} で割った余りが非 {0} ならばこれは矛盾している.

それ以外は {k - 0, 0 - k} のセットを大量に生成して, 余りを適当にどこかの試合に割り当てれば良いので {a / k + b / k} で良い.

ソース

なんか素直にやると条件付きの不等式がでてきてこれを最大化する問題に帰着できるのだが, どう考えてもヤバイ形なので困っていた.

こういう自明な問題にINF分溶かすと辛い….(あとこの問題でやる気を削がれて解いた後夕食を食べに行った)

#include <bits/stdc++.h>

using namespace std;

int main()
{
  long long k, a, b;
  cin >> k >> a >> b;

  long long mod1 = a % k, mod2 = b % k;
  if((a < k && mod2 != 0) || (b < k && mod1 != 0)) {
    cout << -1 << endl;
  } else {
    cout << a / k + b / k << endl;
  }
}

D. Artsem and Saunders

問題概要

ある整数に対応する値を返す関数 {f(1), f(2), \dots, f(n)} の値が与えられる.

{g(h(x)) = x (1 \le x \le m)} かつ {h(g(x)) = f(x) (1 \le x \le n)} を満たす 関数 {g(1), g(2), \dots, g(n)}, {h(1), h(2), \dots, h(m)} が存在すれば出力せよ.

解法

なにも分かっていないけどサンプルをあわせたら通ってしまった.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, F[100000], g[100000];
  vector< int > v[100000], h;

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> F[i];
    --F[i];
    v[F[i]].push_back(i);
  }

  for(int i = 0; i < N; i++) {
    if(v[i].empty()) continue;
    bool flag = false;
    for(int j : v[i]) {
      if(i == j) {
        flag = true;
      }
      g[j] = h.size();
    }
    if(!flag) {
      cout << -1 << endl;
      exit(0);
    } else {
      h.push_back(i);
    }
  }

  cout << h.size() << endl;
  for(int i = 0; i < N; i++) {
    cout << g[i] + 1 << " ";
  }
  cout << endl;
  for(int i = 0; i < h.size(); i++) {
    cout << h[i] + 1 << " ";
  }
  cout << endl;
}

E. Tree Folding

問題概要(公式の図を見たほうがはやいかも)

{n(2 \le n \le 2 \times 10^5)} 頂点の木が与えられる. この木に対し, ある頂点 {v}, disjoint のパス {a_0 = v, a_1, a_2, \dots, a_k}, {b_0 = v, b_1, b_2, \dots, b_k} を選んで {b_1, b_2, \dots, b_k} を取り除くという操作を何度か行い, 木をパスにしたい. 但し, {a_1, a_2, \dots, a_k, b_1, b_2, \dots, b_k} のそれぞれの頂点はパス以外の頂点と隣接してはいけない.

木をパスにできるとき, 最終的なパスの長さの最小値を出力せよ.

解法

適当な頂点を根にした根付き木として, 全方位木DPをする.

{1} 回目の dfs で, それぞれの部分木について, 一纏めにできるかを調べる. これは, 全ての子の部分木の深さが同じで,子も一纏めに出来るときに可能である.

{2} 回目 の dfs で親からのパスを加えたとき, それぞれの頂点で一纏めに出来るか見る. この最小値が最終的な解である(但しパスの長さが偶数の時は何回か折れるので {2} で割る).

ソース

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int N;
vector< int > g[200000];
int depth[200000];
bool malta[200000];

void dfs2(int idx, int par = -1)
{
  bool ch = true;
  set< int > vv;
  for(auto &to : g[idx]) {
    if(to == par) continue;
    dfs2(to, idx);
    if(!malta[to]) ch = false;
    depth[idx] = max(depth[idx], depth[to] + 1);
    vv.emplace(depth[to] + 1);
  }
  malta[idx] = ch && vv.size() <= 1;
}

int rec(int idx, int pardist, int par = -1)
{
  map< int, int > ds;
  vector< pair< int, int > > dists;

  int mz = 0;
  for(auto &to : g[idx]) {
    if(to == par) continue;
    ds[depth[to] + 1]++;
    dists.emplace_back(depth[to] + 1, to);
    mz += !malta[to];
  }

  dists.emplace_back(pardist, -1);
  if(pardist > 0) ds[pardist]++;
  sort(dists.rbegin(), dists.rend());

  int ret = INF;

  for(auto &to : g[idx]) {
    if(to == par) continue;
    int chdist = dists[dists[0].second == to].first + 1;
    ds[depth[to] + 1]--;
    if(ds.size() <= 1 || (ds[depth[to] + 1] == 0 && ds.size() <= 2)) {
      if(mz - (!malta[to]) == 0) ret = min(ret, rec(to, chdist, idx));
    }
    ds[depth[to] + 1]++;
  }

  if(mz == 0 && ds.size() <= 2) {
    int get;
    if(ds.size() == 2) get = ds.begin()->first + (--ds.end())->first;
    else get = ds.begin()->first;
    while(get % 2 == 0) get /= 2;
    ret = min(ret, get);
  }
  return(ret);
}


int main()
{
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs2(0);
  auto get = rec(0, 0);
  if(get == INF) cout << -1 << endl;
  else cout << get << endl;
}