CodeChef September Challenge 2016

Chef and digits of a number

問題概要

${0, 1}$ からなる数字列 ${D(1 \le |D| \le 10^5)}$ がある. ${1}$ 桁を変更して全て同じ数字にできるかを判定せよ.

解法

${0}$ か ${1}$ の数が ${1}$ つのときのみ同じ数字にできる.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
void Calculation()
{
  string D;
  cin >> D;
  int one = 0;
  for(char c : D) one += (c == '1');
 
  if(one == 1 || one + 1 == D.size()) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}
 
int main()
{
  int T;
  cin >> T;
  while(T--) Calculation();
}

Faded Palindromes

問題概要

['a'-'z'] と '.' のみからなる文字列 ${S(1 \le |s| \le 12345)}$ が与えられる. '.' の部分に上手くアルファベットを埋めることによって回文文字列にできるか判定し, 可能であれば辞書順最小の文字列を出力せよ.

解法

回文で対応する文字は, ${i}$ 番目と ${|s| - i}$ 番目の文字である. それぞれの対応する文字について,

両方 '.' なら 'a' を入れる.
片方が '.' ならもう一方の文字を入れる.
両方 ['a'-'z'] なら同じかどうか判定する.

をする.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
void Calculation()
{
  string S;
  cin >> S;
 
  if(S.size() % 2 == 1 && S[S.size() / 2] == '.') {
    S[S.size() / 2] = 'a';
  }
 
  for(int i = ((int)S.size() - 1) / 2; i >= 0; i--) {
    char &p = S[i], &q = S[S.size() - i - 1];
    if(p == '.' && q == '.') {
      p = q = 'a';
    } else if(p == '.' && isalpha(q)) {
      p = q;
    } else if(isalpha(p) && q == '.') {
      q = p;
    } else if(p != q) {
      cout << -1 << endl;
      return;
    }
  }
  cout << S << endl;
}
 
int main()
{
  int T;
  cin >> T;
  while(T--) Calculation();
}

Chef and calculation

問題概要

${N(1 \le N \le 100)}$ 人がいて, それぞれクッキーを ${C_i}$ 枚持っている. それぞれ, 自分が持っているクッキーを箱詰めして輸送したい.

クッキーを ${1}$ 枚詰めるごとに ${1}$ 点得られる. また, クッキーは ${6}$ 種類あって, 詰め方によって以下のようなボーナス点が設定されている.

異なる ${4}$ 種類のクッキーの箱は追加で ${1}$ 点
異なる ${5}$ 種類のクッキーの箱は追加で ${2}$ 点
異なる ${6}$ 種類のクッキーの箱は追加で ${4}$ 点

それぞれがクッキーを最適に詰める時, 勝者を求めよ.

解法

貪欲法で解けて, 種類数が大きい箱から順に作っていけばよい.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1 << 30;
const int additional[] = {0, 0, 0, 0, 1, 2, 4};
 
void Calculation()
{
  int N;
  cin >> N;
  vector< int > point(N);
  for(int i = 0; i < N; i++) {
    int C;
    cin >> C;
    point[i] = C;
    vector< int > sum(6, 0);
    for(int j = 0; j < C; j++) {
      int t;
      cin >> t;
      sum[--t]++;
    }
    for(int j = 6; j >= 4; j--) {
      for(int k = 0; k < 1 << 6; k++) {
        if(__builtin_popcount(k) != j) continue;
        int p = INF;
        for(int l = 0; l < 6; l++) {
          if((k >> l) & 1) p = min(p, sum[l]);
        }
        point[i] += p * additional[j];
        for(int l = 0; l < 6; l++) {
          if((k >> l) & 1) sum[l] -= p;
        }
      }
    }
  }
  int win = max_element(begin(point), end(point)) - begin(point);
  if(count(begin(point), end(point), point[win]) > 1) {
    cout << "tie" << endl;
  } else if(win == 0) {
    cout << "chef" << endl;
  } else {
    cout << win + 1 << endl;
  }
}
 
int main()
{
  int T;
  cin >> T;
  while(T--) Calculation();
}

Chef and Friends

問題概要

${N(1 \le N \le 10^3)}$ 人いて, ${1}$ から ${N}$ までの番号がつけられている. また, ${A_i}$ と ${B_i}$ が互いに知り合いであるという情報が ${M(1 \le M \le 10^6)}$ 個与えられる.

すべての人がお互いに知り合い同士となるようにグループを組みたい. ${N}$ 人を ${2}$ つのグループに分割できるか判定せよ.

解法

補グラフを考える. 辺 ${u}$ , ${v}$ が存在すれば別のグループである必要がある.

一般化すると, これは頂点彩色問題. すべての頂点を, 隣合った頂点が別の色となるように ${2}$ 色で塗りたい.

これは ${2}$ 部グラフ判定をすれば解ける. ${2}$ 部グラフ判定は union-find を使うといいかも. 補グラフの辺を張るフェーズが重くて ${O(N^2)}$ .

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
struct UnionFind
{
  vector< int > data;
 
  UnionFind(int 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]));
  }
};
 
void Calculation()
{
  int N, M;
  scanf("%d %d", &N, &M);
  vector< vector< bool > > connect(N, vector< bool >(N, true));
  for(int i = 0; i < M; i++) {
    int A, B;
    scanf("%d %d", &A, &B);
    --A, --B;
    connect[A][B] = connect[B][A] = false;
  }
  UnionFind tree(N + N);
  for(int i = 0; i < N; i++) {
    for(int j = i + 1; j < N; j++) {
      if(connect[i][j]) {
        tree.unite(i, N + j);
        tree.unite(N + i, j);
      }
    }
  }
 
  for(int i = 0; i < N; i++) {
    if(tree.find(i) == tree.find(i + N)) {
      cout << "NO" << endl;
      return;
    }
  }
 
  cout << "YES" << endl;
}
 
int main()
{
  int T;
  scanf("%d", &T);
  while(T--) Calculation();
}

Dividing Machine

Type 0 Operation

Update(L,R):
    for i = L to R:
        a[i] = a[i] / LeastPrimeDivisor(a[i])

Type 1 Operation

Get(L,R):
    result = 1
    for i = L to R:
        result = max(result, LeastPrimeDivisor(a[i]))
    return result;

ここで LeastPrimeDivisor(x) は ${x}$ の最小の素因数を返す. これが存在しなければ ${1}$ を返す.

長さ ${N(1 \le N \le 10^5)}$ の数列 ${A_i(1 \le A_i \le 10^6)}$ と, ${M(1 \le M \le 10^5)}$ 個の操作の情報が与えられる. 各操作は上記の ${2}$ 種類のいずれかである. すべての操作を処理し Type 1 について戻り値を出力せよ.

解法

Get() は区間の最大値なのでセグメント木を使うと良い.

Update() について考える. 素数定理より, 最大で ${O(\log A_i)}$ 回素因数で割ればそれ以降 ${A_i}$ はずっと ${1}$ になることが分かる. よって. Update() による要素の更新は ${O(N \log A_i)}$ 回であるので, ${1}$ つずつ愚直に更新しても間に合うので頑張る.

また各値についての最小素因数は ${(N \log \log N)}$ で前計算しておく.

ソース

なんか最初, 闇Segtreeを実装しててアレだった.

#include <bits/stdc++.h>
 
using namespace std;
 
 
int to[1000001];
 
void init()
{
  for(int i = 1; i <= 1000000; i++) {
    to[i] = i;
  }
  for(int i = 2; i * i <= 1000000; i++) {
    if(to[i] == i) {
      for(int j = i + i; j <= 1000000; j += i) {
        to[j] = min(to[j], i);
      }
    }
  }
}
 
 
struct SegmentTree
{
  vector< int > seg;
  int sz;
 
  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, 1);
  }
 
  int rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (1);
    if(a <= l && r <= b) return (seg[k]);
    int ll = rmq(a, b, 2 * k + 1, l, (l + r) >> 1);
    int rr = rmq(a, b, 2 * k + 2, (l + r) >> 1, r);
    return (max(ll, rr));
  }
 
  int rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }
 
  void update(int k, int x)
  {
    k += sz - 1;
    seg[k] = x;
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = max(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }
};
 
void Calculation()
{
  int N, M;
  scanf("%d %d", &N, &M);
  SegmentTree tree(N);
  vector< int > A(N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    tree.update(i, to[A[i]]);
    A[i] /= to[A[i]];
  }
  set< int > sets;
  for(int i = 0; i <= N; i++) {
    sets.insert(i);
  }
 
  bool first = false;
  for(int i = 0; i < M; i++) {
    int T, L, R;
    scanf("%d %d %d", &T, &L, &R);
    --L;
    if(T == 0) {
      auto k = sets.lower_bound(L);
      while(*k < R) {
        int now = *k;
        tree.update(now, to[A[now]]);
        if(to[A[now]] == 1) k = sets.erase(k);
        else ++k;
        A[now] /= to[A[now]];
      }
    } else {
      if(first++) putchar(' ');
      printf("%d", tree.rmq(L, R));
    }
  }
  puts("");
}
 
int main()
{
  init();
  int T;
  scanf("%d", &T);
  while(T--) Calculation();
}

JosephLand

問題概要

${N(1 \le N \le 10^5)}$ 頂点の有向木がある. すべての頂点から頂点 ${1}$ に到達することができる.

${M(1 \le M \le 10^5)}$ 個のチケットがあってそれぞれ頂点 ${v_i}$ でコスト ${w_i}$ で買うことができる. チケットを使用して ${v_i}$ から ${k_i}$ 本以下の道路を通って移動することができる. チケットは一度に複数所有することは出来ない.

${Q(1 \le Q \le 10^5)}$ 個のクエリが与えられる. それぞれのクエリについて, 頂点 ${h_i}$ から頂点 ${1}$ に移動するときの最小コストを求めよ.

解法

簡単な木DP.

${v_i}$ に移動するためには, 頂点 ${v_i}$ の深さを ${depth_i}$ とすると, ( ${depth_i - k_i}$ から ${depth_i - 1}$ の範囲の頂点のうちコストの最小) + ${w_i}$ のコストが必要である.

自分より深さが浅い頂点についてコストが計算できてれば良いので深さ優先っぽく計算しておけばよくて, 範囲の頂点のコストの最小はセグメント木を使えるので, ${O((N + M) \log N)}$ で求めることができる.

ソース

目がついていないので, 有向辺であることが見えてなくてヤバイ問題だと思っていた.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
const int64 INF = 1LL << 59;
 
struct SegmentTree
{
  vector< int64 > seg;
  int sz;
 
  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, INF);
  }
 
  int64 rmq(int l, int r)
  {
    int64 ret = INF;
    for(l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
      if(l & 1) ret = min(ret, seg[l++]);
      if(r & 1) ret = min(ret, seg[--r]);
    }
    return (ret);
  }
 
  void update(int k, int64 x)
  {
    for(seg[k += sz] = x; k > 1; k >>= 1) {
      seg[k >> 1] = min(seg[k], seg[k ^ 1]);
    }
  }
};
 
 
int N, M, Q;
vector< int > g[100000];
vector< pair< int, int > > ticket[100000];
SegmentTree tree(100000);
int64 dp[100000];
 
void dfs(int idx, int depth)
{
  if(idx != 0) {
    dp[idx] = INF;
    for(auto k : ticket[idx]) {
      dp[idx] = min(dp[idx], tree.rmq(depth - k.first, depth) + k.second);
    }
  }
  tree.update(depth, dp[idx]);
  for(int to : g[idx]) dfs(to, depth + 1);
}
 
int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N - 1; i++) {
    int A, B;
    scanf("%d %d", &A, &B);
    g[--B].push_back(--A);
  }
  for(int i = 0; i < M; i++) {
    int V, K, W;
    scanf("%d %d %d", &V, &K, &W);
    ticket[--V].emplace_back(K, W);
  }
  dfs(0, 0);
 
  scanf("%d", &Q);
  for(int i = 0; i < Q; i++) {
    int H;
    scanf("%d", &H);
    printf("%lld\n", dp[--H]);
  }
}

ei1333の日記

ぺこい

CodeChef September Challenge 2016

Chef and digits of a number

問題概要

解法

ソース

Faded Palindromes

問題概要

解法

ソース

Chef and calculation

問題概要

解法

ソース

Chef and Friends

問題概要

解法

ソース

Dividing Machine

解法

ソース

JosephLand

問題概要

解法

ソース