http://arc078.contest.atcoder.jp/tasks/arc078_b
解法自体は簡単だけど、バグらせたので。
こういう境界でバグらせやすい問題は[a b)の区間で考えるのがよさそう。
[a (a+b)/2)にすると半分、またはそれより1小さくなり、
[a (a+b+1)/2)にすると半分、またはそれより1大きくなる。
またwhileはカッコ内をループ内で主に注目する変数の存在条件にして、1進む処理をwhile文の一番下でやるのが良いだろう。
こうすればfor文と全く同じ形になる。
nextとnowを持って何かをするときはnextについて処理を行うことに注意しよう。dp的に考えたら当たり前のことだが。
vector<int> dep, tz; vector<vector<int>> G; vector<vector<int>> child; vector<int> par; int dfs(int v, int de = 0, int p = -1) { par[v] = p; dep[v] = de; ll res = 1; rep(i, 0, sz(G[v])) { int u = G[v][i]; if(p == u) continue; child[v].push_back(u); res += dfs(u, de + 1, v); } return tz[v] = res; } void solve() { int N; cin >> N; dep.resize(N); tz.resize(N); G.resize(N); child.resize(N); par.resize(N); rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } dfs(0); int v = N - 1; int f = (dep[N - 1] + 2) / 2, g = (dep[N - 1] + 1) / 2; rep(i, 0, sz(child[N - 1])) { int u = child[N - 1][i]; g += tz[u]; } while(par[v] != -1) { int uv = par[v]; ll tmp = 0; rep(i, 0, sz(child[uv])) { int u = child[uv][i]; if(u == v) continue; tmp += tz[u]; } if(dep[uv] > (dep[N - 1] + 2) / 2 - 1) g += tmp; else f += tmp; v = uv; } /* rep(i, 0, N) debug(child[i]); debug(dep); debug(tz); debug(f, g); */ if(f > g) cout << "Fennec" << "\n"; else cout << "Snuke" << "\n"; }