https://codeforces.com/contest/1292
A
点を共有するおじゃまマスが存在してはいけません。隣接している箇所の個数のみを保持すればいいです。
B
まずどっかの点に行ってから上or下に順番に取っていくのが最適です。点を全列挙する際にオーバーフロー
に注意しなければならないですが、僕はx > sx + t || y > sy + tでbreakしました。
C
ある辺に0を書き込んでから両端に1,2,3...とpathを延長していくのが最適です。するとコストは、
s(k) = (0を通るpathの本数)+(0,1を通るpathの本数)+...+(0,1,2,...,kを通るpathの本数)とすれば、s(N-1)となります。
ここでdp[u][v]:=uからvのpath上に0~dist(u,v)-1を書き込んだ時のs(dist(u,v)-1)の最大値
とします。path上にあってuと隣接している点をpとすれば、chmin(dp[u][v],dp[p][v]+cost[u][v])で更新できます。
vも同様にやります。ここでcostはuからvのpathを丸々含むpathの本数となるので、これを前計算で求めておきます。
これが結構難しかったです。根付き木でu,vのsubtreeの頂点数を足し引きするみたいな方針でやったんですが、適当にやったら
lca(u,v)=uの時に破滅しました。このときはcost[u][v]=(N-|subtree(p)|)*|subtree(v)|としなければならず、pをいちいち求めていると
3乗になってTLEします。なのでN=3000であることを活かしてまず最初にlca(u,v)=uとなるような頂点のpairについて頂点の親を順番にみていきながら
求め、残りのpairは|subtree(u)|*|subtree(v)|となることを利用して求めました。最初lcaが必要かなと思ったんですが結局いらずにO(N^2)でした。
上記の嘘で1WA、オーバーフローで1WAしました。絶妙にオーバーフローするんだよね…
あと更新の際pを見つけるのにdeg(u)=O(N)かかる場合があるからO(N^3)になりそうな気がするんですが、
あるuを固定するとdeg(u)かかるのがvの数、つまりN個かかるので、N deg(u)となり、uを全て見てもN 2*(N-1)にしかならずO(N^2)です。
これはかなり非直感的なので勉強になりました。
int N; vi G[MAX_N]; int cost[3010][3010]; int dist[3010][3010]; int par[3010]; ll dp[3010][3010]; int sub[3010]; void pre(int v, int p) { sub[v] = 1; par[v] = p; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(n == p) continue; pre(n, v); sub[v] += sub[n]; } } void qre(int root, int v, int p, int c) { dist[root][v] = c; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(n == p) continue; qre(root, n, v, c + 1); } } ll loop(int v, int u) { if(v == u) return 0; else if(v > u) return loop(u, v); else if(dp[v][u] != -1) return dp[v][u]; else { ll res = 0; int d = dist[v][u]; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(dist[n][u] < d) { MAX(res, loop(n, u) + cost[v][u]); } } rep(i, 0, sz(G[u])) { int n = G[u][i]; if(dist[v][n] < d) { MAX(res, loop(v, n) + cost[v][u]); } } return dp[v][u] = res; } } void solve() { cin >> N; rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } pre(0, -1); rep(i, 0, N) { qre(i, i, -1, 0); } rep(i, 0, N) { int at = i; while(at != 0) { int nat = par[at]; cost[i][nat] = (N - sub[at]) * sub[i]; cost[nat][i] = cost[i][nat]; at = nat; } } rep(i, 0, N) { rep(j, 0, N) { if(i == j) continue; if(!cost[i][j]) { cost[i][j] = sub[i] * sub[j]; } } } memset(dp, -1, sizeof(dp)); ll res = 0; rep(i, 0, N) { rep(j, i + 1, N) { MAX(res, loop(i, j)); } } cout << res << "\n"; }
