2019-04-26

ABC 123

Editorialが丁寧に書かれていてよかった。

A

アンテナeとアンテナaが最も離れているのでe-aだけ調べる

#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  if (e - a > k)
    cout << ":(" << endl;
  else
    cout << "Yay!" << endl;
}

Submission #5124500 - AtCoder Beginner Contest 123

B

B - Five Dishes

10で割った余りが一番小さいものを最後に注文するのが最短。
解説のコードが綺麗だった

#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int f(int n) { return (n % 10 == 0 ? n : n / 10 * 10 + 10); }
int main() {
  int A, B, C, D, E;
  cin >> A >> B >> C >> D >> E;
  int ans = numeric_limits<int>::max();
  ans = min(ans, f(A) + f(B) + f(C) + f(D) + E);
  ans = min(ans, f(A) + f(B) + f(C) + f(E) + D);
  ans = min(ans, f(A) + f(B) + f(D) + f(E) + C);
  ans = min(ans, f(A) + f(C) + f(D) + f(E) + B);
  ans = min(ans, f(B) + f(C) + f(D) + f(E) + A);
  cout << ans << endl;
}

Submission #5124543 - AtCoder Beginner Contest 123

C

C - Five Transportations

一番運搬人数が少ないところを通るのにかかる時間+4が答え
C++11以降ではstd::maxの引数にinitializer_listが使えることを知らなかったのでこういう書き方をした。

#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
ll f(ll n, ll p) { return (n % p == 0 ? n / p : n / p + 1); }
int main() {
  ll N, A, B, C, D, E;
  cin >> N >> A >> B >> C >> D >> E;
  ll ans = max(f(N, A), f(N, B));
  ans = max(ans, f(N, C));
  ans = max(ans, f(N, D));
  ans = max(ans, f(N, E));
  cout << ans + 4 << endl;
}

Submission #5124621 - AtCoder Beginner Contest 123

D

D - Cake 123

解けなかったので解説を見た。
A, B, Cを大きい順にソートして(i+1)*(j+1)*(k+1) <= Kを満たすi, j, kについてA[i]+B[j]+C[k]を求めて大きい順にソートすれば上位K個が必ず求まる。
言われればそうなんだけど気が付かないものだなぁ
解説にはpriority-queueを使ったより高速な解法など4通りの解法が解説されていて良い。

#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
ll A[1001], B[1001], C[1001];
int main() {
  int X, Y, Z, K;
  cin >> X >> Y >> Z >> K;
  REP(i, X) cin >> A[i];
  REP(i, Y) cin >> B[i];
  REP(i, Z) cin >> C[i];
 
  sort(A, A + X, greater<ll>());
  sort(B, B + Y, greater<ll>());
  sort(C, C + Z, greater<ll>());
 
  vector<ll> s;
  REP(i, X) {
    REP(j, Y) {
      REP(k, Z) {
        if ((i + 1) * (j + 1) * (k + 1) <= K) s.push_back(A[i] + B[j] + C[k]);
      }
    }
  }
  sort(s.begin(), s.end(), greater<ll>());
  REP(i, K) cout << s[i] << endl;
}

Submission #5125010 - AtCoder Beginner Contest 123

追記: priority-queueを使ったバージョン（参考: AtCoder ABC 123 D - Cake 123 (400 点) - けんちょんの競プロ精進記録）

#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;

using namespace std;
using Data = pair<long long, tuple<ll, ll, ll>>;

ll A[1001], B[1001], C[1001];
int main() {
  int X, Y, Z, K;
  cin >> X >> Y >> Z >> K;
  REP(i, X) cin >> A[i];
  REP(i, Y) cin >> B[i];
  REP(i, Z) cin >> C[i];

  sort(A, A + X, greater<ll>());
  sort(B, B + Y, greater<ll>());
  sort(C, C + Z, greater<ll>());

  priority_queue<Data> que;
  set<tuple<int, int, int>> se;

  que.push(Data(A[0] + B[0] + C[0], make_tuple(0, 0, 0)));
  REP(i, K) {
    auto e = que.top();
    que.pop();
    cout << e.first << endl;
    ll idxA = std::get<0>(e.second);
    ll idxB = std::get<1>(e.second);
    ll idxC = std::get<2>(e.second);
    if (idxA + 1 < X) {
      ll sum = e.first - A[idxA] + A[idxA + 1];
      tuple<int, int, int> t = make_tuple(idxA + 1, idxB, idxC);
      Data d = Data(sum, t);
      if (!se.count(t)) {
        se.insert(t);
        que.push(d);
      }
    }
    if (idxB + 1 < Y) {
      ll sum = e.first - B[idxB] + B[idxB + 1];
      tuple<int, int, int> t = make_tuple(idxA, idxB + 1, idxC);
      Data d = Data(sum, t);
      if (!se.count(t)) {
        se.insert(t);
        que.push(d);
      }
    }
    if (idxC + 1 < Z) {
      ll sum = e.first - C[idxC] + C[idxC + 1];
      tuple<int, int, int> t = make_tuple(idxA, idxB, idxC + 1);
      Data d = Data(sum, t);
      if (!se.count(t)) {
        se.insert(t);
        que.push(d);
      }
    }
  }
}

Submission #5125525 - AtCoder Beginner Contest 123

gcc 5と6以降でタプルの仕様が違うことを知らなかったので手元でコンパイル通るコードがジャッジシステム上ではコンパイルエラーになった。 std::tuple::tuple - cppreference.com によるとC++11に対してDefect Reportが出ていて、仕様が変更されたらしい。 make_tupleを常に使うようにしたほうが安全だろう。

2019-04-25

ABC 124

競技プログラミングは申請書からの逃避に役立つ。

A

A - Buttons

1回目はAとBの大きい方の枚数のコインが手に入る
2回目は縮小したボタンと押さなかった方のボタンの大きい方の枚数のコインが手に入る

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  int ans = max(A, B) + ((A > B) ? max(A-1, B) : max(A, B-1));
  cout << ans << endl;
}

Submission #5114332 - AtCoder Beginner Contest 124

B

B - Great Ocean View

i 番目までの旅館で最も高い旅館の高さを持っておき、それ以上の高さだったら眺められる旅館の数を1増やす

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int N, H;
  cin >> N;
  int ans = 0;
  int highest = numeric_limits<int>::min();
  REP(i, N) {
    cin >> H;
    if(H >= highest) {
      highest = H;
      ans++;
    }
  }
  cout << ans << endl;
}

Submission #5114368 - AtCoder Beginner Contest 124

C

C - Coloring Colorfully

0101010.... または 1010101... のどちらかにしかならないので、両方とのハミング距離を計算して小さい方

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int ans01 = 0;
  char c = '0';
  REP(i, S.size()) {
    if(S[i] != c) ans01++;
    c = (c == '0' ? '1' : '0');
  }
  c = '1';
  int ans10 = 0;
  REP(i, S.size()) {
    if(S[i] != c) ans10++;
    c = (c == '0' ? '1' : '0');
  }
  cout << min(ans01, ans10) << endl;
}

Submission #5114399 - AtCoder Beginner Contest 124

D

D - Handstand

自力でやったらTLEだったので解説を見た
0 と 1 が切り替わるところの位置を持っておいて、そこだけ調べる
その位置の文字が0なら2K個先の切り替わり位置、1なら2K+1個先の切り替わり位置との差を取ればその位置からスタートした最も長い連続逆立ち人数がO(1)で求まるからO(N)
これに気が付かなくていちいち数えていたのでO(N^2)になった
N <= 10^5 のときはO(N^2)だと間に合わないという認識をちゃんと持つ必要がある
解説が1-indexedなので0-indexedにするために1を足したり引いたりしている

#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;

using namespace std;

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  vector<int> I({1});
  FOR(i, 1, N) {
    if (S[i] != S[i - 1]) I.push_back(i + 1);
  }

  int ans = 0;
  int r = I.size();
  REP(k, r) {
    int cnt;
    if (S[I[k] - 1] == '0') {
      cnt = (k + 2 * K >= r ? N + 1 : I[k + 2 * K]) - I[k];
    } else {
      cnt = (k + 2 * K + 1 >= r ? N + 1 : I[k + 2 * K + 1]) - I[k];
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;
}

Submission #5115219 - AtCoder Beginner Contest 124

計算量オーダーの求め方を総整理！〜どこから log が出て来るか〜 - Qiita によればループの回数を10^8〜10^9回に抑えるようにする必要があるとのこと。以後意識する。

2019-02-17

ABC 118

コンテストが終了してから参加した。

A問題

書いてあるとおりにやる。

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  if(B % A == 0) cout << A+B << endl;
  else cout << B-A << endl;
}

Submission #4292453 - AtCoder Beginner Contest 118

B問題

各食べ物についてそれを好んでいる人数を数えて、好んでいる人数がNである食べ物の種類数を出力する。

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int N, M;
  int cnt[31];
 
  cin >> N >> M;
 
  for(int i=0; i<M; ++i) cnt[i] = 0;
 
  for(int i=0; i<N; ++i) {
    int K;
    cin >> K;
    for(int j=0; j<K; ++j) {
      int A;
      cin >> A;
      cnt[A-1] += 1;
    }
  }
 
  int ans = 0;
  for(int i=0; i<M; ++i) {
    if(cnt[i] == N) ans++;
  }
  cout << ans << endl;
}

Submission #4292700 - AtCoder Beginner Contest 118

C問題

各モンスターの体力の最大公約数が答え。最終的な体力が最小になるように減らし合う操作はユークリッドの互除法と一致する。

#include <bits/stdc++.h>
 
using namespace std;
 
int gcd(int a, int b) {
  if(a < b) swap(a, b);
  if(b == 0) return a;
  return gcd(b, a%b);
}
 
int main() {
  int N;
  int A[100001];
  cin >> N;
  for(int i=0; i<N; ++i) {
    cin >> A[i];
  }
  int ans = gcd(A[0], A[1]);
  for(int i=2; i<N; ++i) {
      ans = gcd(ans, A[i]);
  }
  cout << ans << endl;
}

Submission #4292977 - AtCoder Beginner Contest 118

D問題

n本ちょうどのマッチ棒を使って作れる最大の数をdp[n]として動的計画法。 long long intに収まらないので数はstringで表現した。大小比較が面倒だが、桁数が違うなら桁数が大きい方・桁数が同じなら辞書順が大きい方が数として大きいことを利用した。

#include <bits/stdc++.h>
 
using namespace std;
 
int N, M;
int A[10];
int num[] = {-1, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string dp[10010];
 
 
int main() {
  cin >> N >> M;
  for(int i=0; i<M; ++i) {
    cin >> A[i];
  }
 
  for(int i=0; i<=N; ++i) {
    for(int j=0; j<M; ++j) {
      int n = num[A[j]];
      string tmp;
      stringstream ss;
 
      if(i < n) continue;
      if(i == n) ss << A[j];
      else if(dp[i-n] != "") ss << A[j] << dp[i-n];
      else continue;
      ss >> tmp;
      if(tmp.size() > dp[i].size() || (tmp.size() == dp[i].size() && tmp > dp[i])) {
        dp[i] = tmp;
      }
    }
  }
  cout << dp[N] << endl;
}

Submission #4293711 - AtCoder Beginner Contest 118

2018-12-23

AOJ GRL_6_A: Network Flow - Maximum Flow

最大流 | グラフ | Aizu Online Judge

Ford-Fulkerson版。ほぼ蟻本の写経。

#include <bits/stdc++.h>

using namespace std;

struct edge {
  int to, cap, rev;
};

vector<vector<edge>> G(101);
vector<bool> used(1001);

void add_edge(int from, int to, int cap) {
  G[from].push_back((edge){to, cap, (int)G[to].size()});
  G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
}

int dfs(int v, int t, int f) {
  if (v == t) return f;
  used[v] = true;
  for (size_t i = 0; i < G[v].size(); i++) {
    edge &e = G[v][i];
    if (!used[e.to] && e.cap > 0) {
      int d = dfs(e.to, t, min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s, int t) {
  int flow = 0;
  for (;;) {
    fill(used.begin(), used.end(), false);
    int f = dfs(s, t, numeric_limits<int>::max());
    if (f == 0) return flow;
    flow += f;
  }
}

int main() {
  int V, E;
  cin >> V >> E;
  vector<int> c(E);
  for (int i = 0; i < E; ++i) {
    int from, to, cap;
    cin >> from >> to >> cap;
    add_edge(from, to, cap);
  }
  cout << max_flow(0, V - 1) << endl;
}

Dinic版。これも蟻本の写経。

#include <bits/stdc++.h>

using namespace std;

struct edge {
  int to, cap, rev;
};

const int MAX_V = 101;

vector<vector<edge>> G(MAX_V);
vector<int> level(MAX_V), iter(MAX_V);

void add_edge(int from, int to, int cap) {
  G[from].push_back((edge){to, cap, (int)G[to].size()});
  G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
}

void bfs(int s) {
  fill(level.begin(), level.end(), -1);
  queue<int> que;
  level[s] = 0;
  que.push(s);
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    for (size_t i = 0; i < G[v].size(); i++) {
      edge &e = G[v][i];
      if (e.cap > 0 && level[e.to] < 0) {
        level[e.to] = level[v] + 1;
        que.push(e.to);
      }
    }
  }
}

int dfs(int v, int t, int f) {
  if (v == t) return f;
  for (int &i = iter[v]; i < (int)G[v].size(); i++) {
    edge &e = G[v][i];
    if (e.cap > 0 && level[v] < level[e.to]) {
      int d = dfs(e.to, t, min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s, int t) {
  int flow = 0;
  for (;;) {
    bfs(s);
    if (level[t] < 0) return flow;
    fill(iter.begin(), iter.end(), 0);
    int f;
    while ((f = dfs(s, t, numeric_limits<int>::max())) > 0) {
      flow += f;
    }
  }
}

int main() {
  int V, E;
  cin >> V >> E;
  vector<int> c(E);
  for (int i = 0; i < E; ++i) {
    int from, to, cap;
    cin >> from >> to >> cap;
    add_edge(from, to, cap);
  }
  cout << max_flow(0, V - 1) << endl;
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3307521#1

2017-12-23

ARC 088

C

何回2倍できるかを数える

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    ll X, Y;
    cin >> X >> Y;
    int ans = 0;
    while(X <= Y) {
        X *= 2;
        ans++;
    }
    cout << ans << endl;
}

Submission #1895699 - AtCoder Regular Contest 088

D

文字列長をn、0と1が切り替わるところをk(1-indexed)としたとき、max(k, n-k)の最大値が答え。全ての文字が同じ場合はnが答え。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    string S;
    cin >> S;
    int n = S.size();
    int ans = n;
    for(int k=0; k<n; ++k) {
        if(S[k] != S[k+1]) {
            ans = min(ans, max(k+1, n-k-1));
        }
    }
    cout << ans << endl;
}

Submission #1902173 - AtCoder Regular Contest 088

2017-12-23

ARC 087

C

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    map<int, int> m;
    cin >> N;
    REP(i, N) {
        int j;
        cin >> j;
        m[j]++;
    }
    int ans = 0;
    for(auto k : m) {
        if (k.second >= k.first) {
            ans += k.second - k.first;
        } else {
            ans += k.second;
        }
 
    } 
    cout << ans << endl;
}

Submission #1874632 - AtCoder Regular Contest 087

D

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int dx3[16010];
int dy3[16010];
int *dx = dx3+8005;
int *dy = dy3+8005;
 
int dx4[16010];
int dy4[16010];
int *dx2 = dx4+8005;
int *dy2 = dy4+8005;
 
int main(void) {
    string s;
    cin >> s;
    int gx, gy;
    cin >> gx >> gy;
 
    bool isX = true;
    int t = 0;
    vector<int> X, Y;
    for(int i=0; i<s.size(); ++i) {
        if(s[i] == 'F') t++;
        if(s[i] == 'T' || i==s.size()-1) {
            if(isX) {
                X.push_back(t);
            } else {
                Y.push_back(t);
            }
            t = 0;
            isX = !isX;
        }
    }
    dx[X[0]] = 1;
    for(int i=1; i<X.size(); ++i) {
        int mx = X[i];
        if(i%2==1) {
            for(int j=-8000; j<=8000; ++j) {
                if(dx[j] == 1) {
                    dx2[j+mx] = 1;
                    dx2[j-mx] = 1;
                    dx[j] = 0;
                }
            }
        } else {
            for(int j=-8000; j<=8000; ++j) {
                if(dx2[j] == 1) {
                    dx[j+mx] = 1;
                    dx[j-mx] = 1;
                    dx2[j] = 0;
                }
            }
        }
    }
 
    if(Y.size() > 0) {
        dy[Y[0]] = 1;
        dy[-Y[0]] = 1;
    } else {
        dy2[0] = 1;
    }
    for(int i=1; i<Y.size(); ++i) {
        if(i%2==1) {
            for(int j=-8000; j<=8000; ++j) {
                if(dy[j] == 1) {
                    dy2[j+Y[i]] = 1;
                    dy2[j-Y[i]] = 1;
                    dy[j] = 0;
                }
            }
        } else {
            for(int j=-8000; j<=8000; ++j) {
                if(dy2[j] == 1) {
                    dy[j+Y[i]] = 1;
                    dy[j-Y[i]] = 1;
                    dy2[j] = 0;
                }
            }
        }
    }
 
    bool okX = false;
    if(X.size()%2 == 0) {
        if(dx2[gx] == 1) okX = true;
    } else {
        if(dx[gx] == 1) okX = true;
    }
    bool okY = false;
    if(Y.size()%2 == 0) {
        if(dy2[gy] == 1) okY = true;
    } else {
        if(dy[gy] == 1) okY = true;
    }
 
    if(okX && okY) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Submission #1878861 - AtCoder Regular Contest 087

2017-12-17

ARC 086

arc086.contest.atcoder.jp

C - Not so Diverse

mapで各数字がいくつあるかカウント
数字の個数を降順にソートして、大きい方から(K+1)番目以降の数字の和が答え

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N, K;
    cin >> N >> K;
    map<int, int> A;
    REP(i, N) {
        int t;
        cin >> t;
        A[t]++;
    }
    vector<int> v;
    for(auto x : A) {
        v.push_back(x.second);
    }
    sort(v.rbegin(), v.rend());
    int ans = 0;
    for(int i=K; i<=v.size(); ++i) {
        ans += v[i];
    }
    cout << ans << endl;
}

Submission #1858429 - AtCoder Regular Contest 086 | AtCoder

D - Non-decreasing

前から順に最大の正の数を足していくか、後ろから順に最小の負の数を足していけば非減少列が作れる
最大値の絶対値と最小値の絶対値の大小関係によって取れる方針が決まることに注意する（max>0 かつ min>0なら前者、max>0 かつ min<0 かつ |max|<|min| なら後者……のように場合分けして考えると絶対値のみ比較すればよいことが分かる）

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N) {
        cin >> a[i];
    }
    int Max = a[0];
    int Max_idx = 0;か
    int Min = a[0];
    int Min_idx = 0;
    FOR(i, 1, N) {
        if(a[i] > Max) {
            Max = a[i];
            Max_idx = i;
        }
        if(a[i] < Min) {
            Min = a[i];
            Min_idx = i;
        }
    }
    if(Max == Min) {
        cout << 0 << endl;
        return 0;
    }
    vector<pair<int, int>> ans;
    if(abs(Max) > abs(Min)) {
        for(int i=1; i<N; ++i) {
            a[i] += Max*2;
            ans.push_back({Max_idx+1, i+1});
            ans.push_back({Max_idx+1, i+1});
            Max = a[i];
            Max_idx = i;
        }
    } else {
        for(int i=N-2; i>=0; --i) {
            a[i] += Min*2;
            ans.push_back({Min_idx+1, i+1});
            ans.push_back({Min_idx+1, i+1});
            Min = a[i];
            Min_idx = i;
        }
    }
    cout << ans.size() << endl;
    for(auto x : ans) {
        cout << x.first << " " << x.second << endl;
    }
}

Submission #1861515 - AtCoder Regular Contest 086 | AtCoder

E - Smuggling Marbles （400点解法）

根からの深さごとに木DPで数え上げる
各頂点は「その頂点に来たときにビー玉が0個になるその頂点を根とする部分木のビー玉配置の場合の数」と「その頂点に来たときにビー玉が1個になるその頂点を根とする部分木のビー玉配置の場合の数」の2つの数(x, y)=(dp[v][0], dp[v][1])を持っている（ビー玉が0個になるとは、その頂点に来たときに2個以上になって取り上げられる場合を含む）
根からの深さがdの頂点を(1, 1)で初期化する
根からの深さがk (k < d)の頂点では、
- xは深さk+1の子のどれか1つからビー玉が1個来て、残りの全ての子から0個来る場合の数
- yは自分を頂点とする部分木の全ての置き方の場合の数からxを引いた場合の数
これを繰り返すとdp[0][1]が深さdの頂点のみに注目したとき、根までビー玉が来る場合の数になる。それ以外の頂点の置き方は自由なので、2を「深さd以外の頂点数」乗した数のビー玉が根まで到達する
取りうる全てのdについて上のDPを行う

maze1230さんのコードを参考に解きました。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

ll dp[2010][2];
ll nb_depth[2010];

vector<int> G[2010];
const ll MOD = 1e9+7;
 
void count_depth(int v, int depth){
    nb_depth[depth]++;
    REP(i, G[v].size()){
        count_depth(G[v][i], depth+1);
    }
}


ll mpow(ll a, ll b){
    if(b == 0) return 1;
    if(b < 0) return 0;
    if(b%2) return (a*mpow(a, b-1)) % MOD;
    ll ret = mpow(a, b/2);
    return (ret*ret)%MOD;
}

void dfs(int v, int d) {
    if(d == 0) {
        dp[v][0] = dp[v][1] = 1;
        return;
    }
    ll x = 1, y = 1;
    for(auto c: G[v]) {
        dfs(c, d-1);
        x = (x * dp[c][0]) % MOD;
        y = (y * (dp[c][0]+dp[c][1])) % MOD;
    }
    for(auto c: G[v]) {
        // n^{-1} mod p = n^{p-2} mod p
        dp[v][1] += ((x * mpow(dp[c][0], MOD-2)) % MOD * dp[c][1]) % MOD;
        dp[v][1] %= MOD;
    }
    dp[v][0] = (y - dp[v][1] + MOD) % MOD;
}


int main(void) {
    int N;
    cin >> N;
    if(N>2000) return 0;
    REP(i, N) {
        int p;
        cin >> p;
        G[p].push_back(i+1);
    （}
    count_depth(0, 0);
    ll ans = 0;
    REP(d, N+1) {
        REP(j, 2010) {
            REP(k, 2) {
                dp[j][k] = 0;
            }
        }
        dfs(0, d);
        ans = (ans + dp[0][1] * mpow(2, N-nb_depth[d]+1)) % MOD;
    }
    cout << ans << endl;
}

Submission #1883114 - AtCoder Regular Contest 086 | AtCoder

満点解法は解説が理解できないのでパス。