ei1333の日記

ぺこい

Codeforces Round #362 (Div. 1)

こういう回ねー.
The 数学という感じでやられてしまった.
AとBは通した. Cを通せる頭がなかった.
1924 -> 1910(-14).

A. Lorenzo Von Matterhorn

問題概要

頂点 1 を根とする根付き木がある.
任意の頂点  {i} は, 頂点  {2i, 2i+1} に双方向に行き来できる道を持つ.
最初, 任意の道の通行料は無料である.
このとき,  {q (1 \le q \le 1000)} 個の, 次のイベントを処理せよ.

  •  {v, u, w} : 頂点  {v, u} を結ぶパス上の道の通行料を  {w} 上昇させる.
  •  {u, v} : 頂点  {v, u} を結ぶパス上の道の通行料の和を出力する.

与えられる  {u, v} は,  {(1 \le u, v \le 10^{18})} を満たす.

解法

まず,  {q} が小さい.
また,  {u, v} の経路長の最大は  {O(\log(uv) )}. この経路は, 貪欲に遡る(深さが深い方がその親へ移動することを繰り返す)ことでそのオーダーで求まる.
関与する頂点は高々  {O(q \log(uv) )} なので, 普通に保存できそう.

具体的には, 関与した頂点を map で管理しておけばよい.
結局  {O(q \log(q\log(uv)) )} となる.

ソース

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

int main()
{
  int64 Q;
  map< pair< int64, int64 >, int64 > data;
  
  cin >> Q;
  while(Q--) {
    int64 type, v, u, w;
    cin >> type;
    if(type == 1) {
      cin >> v >> u >> w;
      while(v != u) {
        if(u > v) {
          data[{u, u / 2}] += w;
          u /= 2;
        } else {
          data[{v, v / 2}] += w;
          v /= 2;
        }
      }
    } else {
      cin >> v >> u;
      int64 ret = 0;
      while(v != u) {
        if(u > v) {
          ret += data[{u, u / 2}];
          u /= 2;
        } else {
          ret += data[{v, v / 2}];
          v /= 2;
        }
      }
      cout << ret << endl;
    }
  } 
}

B. Puzzles

問題概要

頂点の数が  {n(1 \le n \le 10^{5})} の根付き木がある. 頂点 1 から DFS することを考える.
ある頂点から子に移動するとき, 一様にランダムな順序に移動する.
各頂点について, 何番目に, はじめてその頂点に移動されるか, その期待値を求めよ.

解法

まず前計算として, 任意の頂点  {i} を根とする部分木の頂点数  {subtree_{i}}を求めておく. 言い換えると,  {subtree_{i}} は 頂点  {i} に訪問したとき, 親に戻るまでに訪れる頂点の個数である. これはDFSで.  {O(n)}.

任意の頂点  {u} から, その子のある頂点  {v} に移動することを考える.
 {v} の期待値は,  {v} 以外の子  {u_{c_k}} に依存する.
 {u_{c_k}} について  {v} との関係をみると, それぞれ  {v} を訪れる前に訪問するか, 訪れた後に訪問するかのどちらかである. よって,  {u_{c_k}} の訪問を終えるまでの期待値は  {subtree_{u_{c_k}} / 2} である. これはそれぞれに対して独立であるため,  {v} の期待値は  {\sum({subtree_{u_{c_k}} / 2}) + 1.0 + u} の期待値である.

ソース

組み合わせだつらいと一瞬なってしまった.

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

int N;
vector< int > tree[100000];
int subtree[100000];
double F[100000];

int rec(int idx)
{
  subtree[idx] = 1;
  for(int to : tree[idx]) subtree[idx] += rec(to);
  return(subtree[idx]);
}
void calc(int idx, int par = -1)
{
  for(int to : tree[idx]) {
    F[to] = (subtree[idx] - subtree[to] - 1) * 0.5;
    F[to] += F[idx] + 1.0;
    calc(to);
  }
}
int main()
{
  scanf("%d", &N);
  for(int i = 1; i < N; i++) {
    int R;
    scanf("%d", &R);
    tree[--R].push_back(i);
  }
  rec(0);
  F[0] = 1.0;
  calc(0);
  for(int i = 0; i < N; i++) {
    printf("%.10lf ", F[i]);
  }
}