| 
class PeriodicJumping { public: int minimalTime(int x, vector <int> L) { if(x==0) return 0; int N=L.size(); double lo=0, hi=0; ll ans = 0; REP(loop, 100000) { double start=-1; if(lo==0) start=hi; REP(i, N) { double lolo = lo-L[i]; double lohi = lo+L[i]; double hilo = hi-L[i]; double hihi = hi+L[i]; lo = min(abs(lolo), abs(hilo)); hi = max(abs(hilo), abs(hihi)); if(lolo * hilo < 0 || lohi * hihi < 0) lo=0; ans++; // cout<<lo<<" "<<hi<<endl; if(lo-1e-9<=abs(x) && abs(x)<=hi+1e-9) return ans; } if(start >= 0) { double d = hi - start; ll loop = floor((abs(x) - hi) / d); if(loop > 10000) { loop-=4; // 特急に乗る. ただしちょい手前で減速! (安全第一 // cout<<" d "<<d<<" "<<loop<<" "<<ans<<endl; ans += loop*N; hi += d * loop; } } } return -1; } };
| 
(あとで)
class CatsOnTheLineDiv1 { public: int getNumber(vector <int> P, vector <int> C, int T) { int N=P.size(); vector<pair<int, int> > w(N); REP(i, N) w[i] = MP(P[i], C[i]); sort(ALL(w)); REP(i, N) P[i]=w[i].first, C[i]=w[i].second; int ans = 0; ll next = -(1LL<<60); ll m = -(1LL<<60); REP(i, N) { ll hl = P[i]-T; ll hr = P[i]-C[i]+1+T; if(P[i]-T<=m && m<=P[i]+T) continue; // これを最初にチェックすべき if(hr<next || C[i]/2 > T) { ans++; m = P[i]+T; } else { next = max(next, hl) + C[i]; } } return ans; } };
| 
g(node, i, なし) は g(node, i-1, なし) × --- g(i番目の子, all, なし) ... OK + g(node, i-1, なし) × -|- g(i番目の子, all, なし) ... だめ(i番目の子以下が黒なしで確定しちゃう + g(node, i-1, なし) × --- g(i番目の子, all, あり) ... だめ + g(node, i-1, なし) × -|- g(i番目の子, all, あり) ... OK + g(node, i-1, あり) × --- g(i番目の子, all, なし) ... だめ + g(node, i-1, あり) × -|- g(i番目の子, all, なし) ... だめ(i番目の子以下が黒なしで確定しちゃう + g(node, i-1, あり) × --- g(i番目の子, all, あり) ... だめ + g(node, i-1, あり) × -|- g(i番目の子, all, あり) ... だめ g(node, i, あり) は g(node, i-1, なし) × --- g(i番目の子, all, なし) ... だめ + g(node, i-1, なし) × -|- g(i番目の子, all, なし) ... だめ + g(node, i-1, なし) × --- g(i番目の子, all, あり) ... OK + g(node, i-1, なし) × -|- g(i番目の子, all, あり) ... だめ + g(node, i-1, あり) × --- g(i番目の子, all, なし) ... OK + g(node, i-1, あり) × -|- g(i番目の子, all, なし) ... だめ + g(node, i-1, あり) × --- g(i番目の子, all, あり) ... だめ + g(node, i-1, あり) × -|- g(i番目の子, all, あり) ... OK
VVI g; VVI memo; vector<bool> black; // g(idx, all, b) ll dfs(int prev, int idx, int b) { if(memo[b][idx]>=0) return memo[b][idx]; // このノードと子ノード[0-i]以下からなる subtree を条件を満たすように区切ったとき, node を含む領域に含まれる黒の数 -> 何通り modll dp[2]; dp[0] = (modll)!black[idx]; dp[1] = (modll)black[idx]; REP(i, g[idx].size()) { int ni = g[idx][i]; if(prev==ni) continue; modll ndp[2] = {0, 0}; modll ch[2] = {dfs(idx, ni, 0), dfs(idx, ni, 1)}; REP(pi, 2) REP(ci, 2) REP(cut, 2) { int obi = pi + (cut ? 0 : ci); if(cut && ci==0) continue; // 切断して子以下に黒がなかったらだめ if(obi < 2) ndp[obi] += dp[pi] * ch[ci]; } dp[0] = ndp[0]; dp[1] = ndp[1]; } return memo[b][idx] = dp[b]; } int main() { ll N,p,v; while(cin>>N) { g = VVI(N); memo = VVI(2, VI(N, -1)); black = vector<bool>(N); REP(i, N-1) { cin>>p; g[i+1].PB(p); g[p].PB(i+1); } REP(i, N) { cin>>v; black[i] = v; } ll ans = dfs(-1, 0, 1); cout<<ans<<endl; } return 0; }
| 
i番目の子と node を含む領域をつなぐなら ---, 切るなら -|- として、 g(node, i, なし) は g(node, i-1, なし) × --- g(i番目の子, all, なし) ... OK + g(node, i-1, なし) × -|- g(i番目の子, all, なし) ... だめ(i番目の子以下が黒なしで確定しちゃう + g(node, i-1, なし) × --- g(i番目の子, all, あり) ... だめ + g(node, i-1, なし) × -|- g(i番目の子, all, あり) ... OK + g(node, i-1, あり) × --- g(i番目の子, all, なし) ... だめ + g(node, i-1, あり) × -|- g(i番目の子, all, なし) ... だめ(i番目の子以下が黒なしで確定しちゃう + g(node, i-1, あり) × --- g(i番目の子, all, あり) ... だめ + g(node, i-1, あり) × -|- g(i番目の子, all, あり) ... だめ g(node, i, あり) は g(node, i-1, なし) × --- g(i番目の子, all, なし) ... だめ + g(node, i-1, なし) × -|- g(i番目の子, all, なし) ... だめ + g(node, i-1, なし) × --- g(i番目の子, all, あり) ... OK + g(node, i-1, なし) × -|- g(i番目の子, all, あり) ... だめ + g(node, i-1, あり) × --- g(i番目の子, all, なし) ... OK + g(node, i-1, あり) × -|- g(i番目の子, all, なし) ... だめ + g(node, i-1, あり) × --- g(i番目の子, all, あり) ... だめ + g(node, i-1, あり) × -|- g(i番目の子, all, あり) ... OK なので c0 = g(i番目の子, all, なし) c1 = g(i番目の子, all, あり) と置くと g(node, i, なし) = g(node, i-1, なし) * (c0+c1) g(node, i, あり) = g(node, i-1, なし) * c1 + g(node, i-1, あり) * (c0+c1) となる. 初期条件は g(node, 0, なし) = nodeが白 ? 1 : 0 g(node, 0, あり) = nodeが黒 ? 1 : 0 知りたい答えは g(root, all, あり)
VVI g; VVI memo; vector<bool> black; // g(idx, all, b) ll dfs(int prev, int idx, int b) { if(memo[b][idx]>=0) return memo[b][idx]; // このノードと子ノード[0-i]以下からなる subtree を条件を満たすように区切ったとき, node を含む領域に含まれる黒の数 -> 何通り modll dp[2] = {1, 0}; // modll 略 dp[0] = (modll)!black[idx]; dp[1] = (modll)black[idx]; REP(i, g[idx].size()) { int ni = g[idx][i]; if(prev==ni) continue; ll c0 = dfs(idx, ni, 0); ll c1 = dfs(idx, ni, 1); modll n0 = dp[0] * (c0+c1); modll n1 = dp[0] * c1 + dp[1] * (c0+c1); dp[0] = n0; dp[1] = n1; } return memo[b][idx] = dp[b]; } int main() { ll N,p,v; while(cin>>N) { g = VVI(N); memo = VVI(2, VI(N, -1)); black = vector<bool>(N); REP(i, N-1) { cin>>p; g[i+1].PB(p); g[p].PB(i+1); } REP(i, N) { cin>>v; black[i] = v; } ll ans = dfs(-1, 0, 1); cout<<ans<<endl; } return 0; }
| 
class Egalitarianism3 { public: int maxCities(int n, vector <int> a, vector <int> b, vector <int> len) { if(n<=2) return n; VVI g = VVI(n, VI(n, 1<<30)); REP(i, n-1) { g[a[i]-1][b[i]-1] = len[i]; g[b[i]-1][a[i]-1] = len[i]; } REP(i, n) g[i][i]=0; REP(k, n) REP(i, n) REP(j, n) g[i][j] = min(g[i][j], g[i][k]+g[k][j]); ll ans = 2; REP(i, n) { map<int, VI> hi; // hi[r] ... i を中心とした距離 r かつ全点間について距離が 2r のノード集合 REP(j, n) { auto& vs = hi[g[i][j]]; ll r = g[i][j]; // check if we can add j to hi[r] bool ok = true; for(auto v : vs) if(g[v][j] != 2*r) ok=false; if(ok) { hi[r].PB(j); ans = max(ans, (ll)hi[r].size()); } } } return ans; } };
