SnackDown 2017 Online Elimination Round (解いた問題まとめ)

チーム戦のログみたいなのも別にあって, 有意義そうなので別記事であげます.

こっちは自分がといた ADE の解説だけ.

Add or Multiply

https://www.codechef.com/SNCKEL17/problems/PLUSMUL

問題概要

長さ ${n(1 \le n \le 100000)}$ の正整数の数列が与えられる.

${n - 1}$ 箇所ある値と値との間に ${+}$ か ${\times}$ を書く.

${2^{n - 1}}$ 通りある全ての組み合わせの計算結果を足したものを ${10^9 + 7}$ で割った余りで求めよ.

解法

最初に比較的簡単な ${O(n^2)}$ のDPを気合いで考える.

${dp[idx] :=}$ ${[1, idx]}$ の数列を考えた時の計算結果の和とする.

これに ${idx + 1}$ 番目の値を追加することを考えと,

$dp[idx + 1] = \sum_{j=0}^{idx} (dp[j] + 2^j \prod_{k={j+1}}^{idx+1} a_k)$

という漸化式が立つことがわかる(微妙に係数が違うかも).

これでは間に合わないので漸化式をぐぐぐっと睨む.

$dp[idx + 1] = \sum_{j=0}^{idx} dp[j] + \sum_{j=0}^{idx} (2^j \prod_{k={j+1}}^{idx+1} a_k)$

となり, 左側のsumは ${0}$ から ${idx}$ までの dp の累積和を持っておけば良くてこれは ${O(1)}$ .

右側のsumについても ${O(1)}$ で求まりそうだけど(求まらなきゃ解けない)非自明なのでもう少し整理する.

$\sum_{j=0}^{idx} (2^j \prod_{k={j+1}}^{idx+1} a_k) = a_{idx+1} (\sum_{j=0}^{idx-1} (2^j \displaystyle \prod_{k={j+1}}^{idx} a_k) + 2^{idx})$ .

(前の計算結果 + ${2^{idx}}$ ) に ${a_{idx+1}}$ をかけている形だということが分かるので, ${O(1)}$ でできることがわかる.

遷移が ${O(1)}$ でできたので全体の計算量は ${O(n)}$ で行うことができる.

ソース

これ苦手.... ${1}$ 時間かかった.

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
const int mod = 1e9 + 7;
 
int main()
{
  int N, A[100005];
 
  int64 fact[100005];
  fact[0] = 1;
  for(int i = 1; i < 100001; i++) (fact[i] = fact[i - 1] * 2) %= mod;
 
  int T;
  cin >> T;
 
  while(T--) {
    cin >> N;
    for(int i = 1; i <= N; i++) {
      cin >> A[i];
    }
    int64 dp[100001] = {};
    int64 sum = 0LL, mul = A[1];
    for(int i = 1; i <= N; i++) {
      (dp[i] += mul) %= mod;
      (dp[i] += sum) %= mod;
      (sum += dp[i]) %= mod;
      (mul *= A[i + 1]) %= mod;
      (mul += A[i + 1] * fact[i - 1] % mod) %= mod;
    }
    cout << dp[N] << endl;
  }
}

Ancestors in Two Trees

https://www.codechef.com/SNCKEL17/problems/ANCESTOR/

問題概要

頂点 ${1}$ を根とする ${2}$ つの頂点数 ${n(2 \le n \le 500000)}$ の根付き木が与えられる.

それぞれの頂点について共通祖先の個数を求めよ.

解法

実家のような安心感

HL分解 + BIT + DFS.

一方の木をDFSする. 現在頂点 ${idx}$ を見ているとする.

頂点 ${idx}$ まで下っていくときに現れた頂点すべては一方の木の祖先であるので, これを保持しておく.

現在保持している頂点のうち, もう一方の木の祖先でもあるような頂点数が解.

もう一方の木の根から頂点 ${idx}$ のパス上で現れた頂点が祖先なので, もう一方の木をHL分解してBITで出現情報(下っていく時に現れている頂点に+1する) を管理しておけば ${O(\log n)}$ で求めることができる.

全体で ${O(n \log n)}$ .

ソース

コードは長いがほとんどライブラリのコピペなので, 実装はかなり軽い.

#include<bits/stdc++.h>
 
using namespace std;
 
 
template< class T >
struct BinaryIndexedTree
{
  vector< T > data;
 
  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }
 
  T sum(int k)
  {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }
 
  void add(int k, T x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
 
struct CentroidPathDecomposition
{
  vector< vector< int > > graph;
 
  struct Centroid
  {
    int ParIndex, ParDepth, Deep;
    vector< int > node;
 
    inline int size()
    {
      return (node.size());
    }
 
    inline int &operator[](int k)
    {
      return (node[k]);
    }
 
    inline pair< int, int > Up()
    {
      return (make_pair(ParIndex, ParDepth));
    }
  };
 
  vector< int > SubTreeSize, NextPath;
  vector< int > TreeIndex, TreeDepth;
  vector< Centroid > Centroids;
 
  void BuildSubTreeSize()
  {
    stack< pair< int, int > > s;
    s.push({0, -1});
    while(!s.empty()) {
      auto p = s.top();
      s.pop();
      if(~SubTreeSize[p.first]) {
        NextPath[p.first] = -1;
        for(auto &to : graph[p.first]) {
          if(p.second == to) continue;
          SubTreeSize[p.first] += SubTreeSize[to];
          if(NextPath[p.first] == -1 || SubTreeSize[NextPath[p.first]] < SubTreeSize[to]) {
            NextPath[p.first] = to;
          }
        }
      } else {
        s.push(p);
        SubTreeSize[p.first] = 1;
        for(auto &to : graph[p.first]) {
          if(p.second != to) s.push({to, p.first});
        }
      }
    }
  }
 
  void BuildPath()
  {
    stack< pair< int, int > > s;
    Centroids.push_back((Centroid) {-1, -1, 0});
    s.push({0, -1});
    TreeIndex[0] = 0;
    while(!s.empty()) {
      auto p = s.top();
      s.pop();
      TreeDepth[p.first] = Centroids[TreeIndex[p.first]].size();
      for(auto &to : graph[p.first]) {
        if(p.second != to) {
          if(to == NextPath[p.first]) { // Centroid-Path
            TreeIndex[to] = TreeIndex[p.first];
          } else {                  // Not Centroid-Path
            TreeIndex[to] = Centroids.size();
            Centroids.push_back((Centroid) {TreeIndex[p.first], TreeDepth[p.first], Centroids[TreeIndex[p.first]].Deep + 1});
          }
          s.push({to, p.first});
        }
      }
      Centroids[TreeIndex[p.first]].node.push_back(p.first);
    }
  }
 
  void AddEdge(int x, int y)
  {
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
 
  void Build()
  {
    BuildSubTreeSize();
    BuildPath();
  }
 
  inline int size()
  {
    return (Centroids.size());
  }
 
  inline pair< int, int > Information(int idx)
  {
    return (make_pair(TreeIndex[idx], TreeDepth[idx]));
  }
 
  inline Centroid &operator[](int k)
  {
    return (Centroids[k]);
  }
 
  inline int LCA(int a, int b)
  {
    int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB;
    tie(TreeIdxA, TreeDepthA) = Information(a);
    tie(TreeIdxB, TreeDepthB) = Information(b);
    while(TreeIdxA != TreeIdxB) {
      if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {
        tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();
      } else {
        tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();
      }
    }
    if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);
    return (Centroids[TreeIdxA][TreeDepthA]);
  }
 
  CentroidPathDecomposition(int SZ)
  {
    graph.resize(SZ);
    SubTreeSize.assign(SZ, -1);
    NextPath.resize(SZ);
    TreeIndex.resize(SZ);
    TreeDepth.resize(SZ);
  }
 
  int getPath(int K, vector< BinaryIndexedTree< int > > &segs)
  {
    int TreeIdxA, TreeDepthA;
    tie(TreeIdxA, TreeDepthA) = Information(K);
    int ret = 0;
    while(TreeIdxA > 0) {
      ret += segs[TreeIdxA].sum(TreeDepthA);
      tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();
    }
    ret += segs[TreeIdxA].sum(TreeDepthA);
    return (ret);
  }
};
 
 
int ans[500000];
 
int main()
{
  int T;
  scanf("%d", &T);
  while(T--) {
    int N;
    scanf("%d", &N);
    CentroidPathDecomposition tree(N);
    for(int i = 1; i < N; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      --a, --b;
      tree.AddEdge(a, b);
    }
    tree.Build();
    vector< BinaryIndexedTree< int > > segs;
    for(int i = 0; i < tree.size(); i++) {
      segs.emplace_back(BinaryIndexedTree< int >(tree[i].size() + 1));
    }
 
    vector< vector< int > > h(N);
    for(int i = 1; i < N; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      --a, --b;
      h[a].push_back(b);
      h[b].push_back(a);
    }
 
    function< void(int, int) > dfs = [&](int idx, int par)
    {
      ans[idx] = tree.getPath(idx, segs);
      int a, b;
      tie(a, b) = tree.Information(idx);
      segs[a].add(b, 1);
      for(auto &to : h[idx]) {
        if(to == par) continue;
        dfs(to, idx);
      }
      segs[a].add(b, -1);
    };
 
    dfs(0, -1);
    for(int i = 0; i < N; i++) {
      if(i > 0) putchar(' ');
      printf("%d", ans[i]);
    }
    puts("");
  }
}

Robots in a DAG

https://www.codechef.com/SNCKEL17/problems/ROBOTDAG

問題概要

${N(2 \le N \le 100)}$ 頂点 ${M(1 \le M \le 1000)}$ 辺のDAGが与えられる.

頂点 ${1}$ に ${K(1 \le K \le 100)}$ 個のロボットをおく.

${1}$ 回のステップで, すべてのロボットはいまいる頂点から辺を通って移動可能な好きな頂点に移動する.

すべてのロボットは頂点 ${N}$ に到達すればゴールである.

ゴールするまでにかかる最小ステップ数を求めよ.

解法

最大流 + 二分探索.

ステップ数(解) ${x}$ の二分探索をする.

時系列で管理したいので, それぞれの頂点を ${x}$ 個にわける. 頂点 ${i}$ の時刻 ${t}$ の頂点を ${(i, t)}$ とする.

辺 ${i \to j}$ があるとき, ${(i, t) \to (j, t + 1)}$ に容量 ${1}$ の辺をはる.

で, 頂点 ${(1, 0)}$ から頂点 ${(n, *)}$ への最大流が ${K}$ 以上かどうか判定すれば良い.

計算量がヤバそうだが, 頂点数が ${n^2}$ 個で辺の数が ${nm}$ 個. Dinic の計算量は ${O(v^2 e)}$ なので普通に考えるとア. しかし頂点容量がすべて実質 ${1}$ であるのできっと ${O(n^2m \log n)}$ (期待)みたいな感じになって間に合う気がする(実際間に合う.

ソース

Dinic ははやいね！(実装はバグって異常に遅かったが)

#include<bits/stdc++.h>
 
using namespace std;
 
const int INF = 1 << 30;
 
struct Dinic
{
  struct edge
  {
    int to, cap, rev;
  };
 
  vector< vector< edge > > graph;
  vector< int > min_cost, iter;
 
  Dinic(int n)
  {
    graph.resize(n);
  }
 
  void add_edge(int from, int to, int cap)
  {
    graph[from].push_back((edge) {to, cap, (int) graph[to].size()});
    graph[to].push_back((edge) {from, 0, (int) graph[from].size() - 1});
  }
 
  bool bfs(int s, int t)
  {
    min_cost.assign(graph.size(), -1);
    queue< int > que;
    min_cost[s] = 0;
    que.push(s);
    while(!que.empty()) {
      int p = que.front();
      que.pop();
      for(int i = 0; i < graph[p].size(); i++) {
        const edge &e = graph[p][i];
        if(e.cap > 0 && min_cost[e.to] == -1) {
          min_cost[e.to] = min_cost[p] + 1;
          que.push(e.to);
        }
      }
    }
    return (min_cost[t] != -1);
  }
 
  int dfs(int idx, const int t, int flow)
  {
    if(idx == t) return (flow);
    for(int &i = iter[idx]; i < graph[idx].size(); i++) {
      edge &e = graph[idx][i];
      if(e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
        int d = dfs(e.to, t, min(flow, e.cap));
        if(d > 0) {
          e.cap -= d;
          graph[e.to][e.rev].cap += d;
          return (d);
        }
      }
    }
    return (0);
  }
 
  int max_flow(int s, int t)
  {
    int flow = 0;
    while(bfs(s, t)) {
      iter.assign(graph.size(), 0);
      int f = 0;
      while((f = dfs(s, t, INF)) > 0) {
        flow += f;
      }
    }
    return (flow);
  }
};
 
int main()
{
  int T, N, M, K;
  int A[1000], B[1000];
 
  scanf("%d", &T);
  while(T--) {
    scanf("%d %d %d", &N, &M, &K);
    for(int i = 0; i < M; i++) {
      scanf("%d %d", &A[i], &B[i]);
      --A[i], --B[i];
    }
 
    int low = 0, high = N + 1;
    while(high - low > 0) {
      int mid = (low + high) >> 1;
      if([&]()
      {
        auto getVentex = [&](int idx, int t)
        {
          return (idx * (mid + 1) + t);
        };
        Dinic flow(N * (mid + 1) + 1);
        int t = N * (mid + 1);
        for(int i = 0; i < M; i++) {
          for(int j = 0; j < mid; j++) {
            flow.add_edge(getVentex(A[i], j), getVentex(B[i], j + 1), 1);
          }
        }
        for(int j = 0; j <= mid; j++) flow.add_edge(getVentex(N - 1, j), t, INF);
        return (flow.max_flow(getVentex(0, 0), t) >= K);
      }())
        high = mid;
      else low = mid + 1;
    }
    if(low >= N + 1) puts("-1");
    else printf("%d\n", low);
  }
}

ei1333の日記

ぺこい

SnackDown 2017 Online Elimination Round (解いた問題まとめ)

Add or Multiply

問題概要

解法

ソース

Ancestors in Two Trees

問題概要

解法

ソース

Robots in a DAG

問題概要

解法

ソース