| 
(あとで)
medは得点が負にならない能力のかわりに得点を1回だけ0点にできる能力をもってると考えてもよくて、木を「能力発動前に到達」「能力発動後に到達」「行かず」の3色に塗り分けることを考えて、木DP
— ちゃっくに300円 (@yosupot) 2017年8月15日
これ見たときは「は？？」という感想だったが、よーく考えてみると分かった。
(あ) v0 → 操作A → v1 → 操作A → v2 → 操作A → v3 ... → 操作A
操作A : スコアが負なら 0 にする
(い) 操作B → v0 → 操作B → v1 → 操作B → v2 → 操作B → v3 ... → 操作B
操作B : スコアを 0 にリセットすることができる
(う) 操作B → v0 → 操作B → v1 → 操作B → v2 → 操作B → v3 ... → 操作B ※ただしリセットは高々 1 回だけ
f(頂点 v, v の状態) = v 以下のサブツリーのスコアの最大値
(v, AR) = v でリセット後ということはその子ノードは訪れないかリセット後じゃないといけないので pleasure[v] + Σ f(子ノード, AR|NONE)
(v, NONE) = 子ノードも全部 NONE なので 0
(v, BR) = pleasure[v] はどうせリセットされるのでカウントしない。各子ノードは AR でも BR でも NONE でもよいので Σ f(子ノード, BR|AR|NONE)
ほう〜 こんなすっきりとなるのか〜
(accepted in practice)
class OwaskiAndTree { public: int maximalScore(vector <int> pa, vector <int> pl) { int N = pa.size()+1; VI br(N); VI ar(N); // 葉から順に配ると簡潔に書ける ... lhic さんの実装を参考にした for(int i=N-1; i>=0; i--) { ar[i] += pl[i]; ar[i] = max(ar[i], 0LL); if(i) { int pi = pa[i-1]; ar[pi] += ar[i]; br[pi] += max(br[i], ar[i]); } } return max(br[0], ar[0]); } };
| 
(あとで)
(accepted in practice)
void solve(ll N, const VI& w, ll& minVar, ll& ans) { VI varDiff(N+10), deltaDiff(N+10); ll var = 0; REP(i, N) { VI& dd = deltaDiff; // 無限にバグるパート if(w[i]>i+1) { // 最初 -1 で idx1 のときに +1 になる. また idx3 で -1 になる dd[0] += -1; int idx1 = w[i]-(i+1); dd[idx1] += +2; int idx3 = N-(i+1)+1; dd[idx3] += -2; } else { // 最初 +1 で idx1 のときに -1 になる. また idx3 で +1 になる dd[0] += +1; int idx1 = N-((i+1)-w[i]); dd[idx1] += +2; int idx3 = N-(i+1)+1; dd[idx3] += -2; } { // 回転した瞬間に var が調整される int idx = N-(i+1)+1; ll v = -(N-(w[i]-1)) + (w[i]-1); varDiff[idx] += v; } var += abs(w[i]-(i+1)); } minVar = var; ans = 0; ll delta = deltaDiff[0]; RANGE(i, 1, N) { var += varDiff[i] + delta; delta += deltaDiff[i]; if(var<minVar) { minVar = var; ans = i; } } } int main() { ios::sync_with_stdio(false); ll N; while(cin>>N) { VI w(N); REP(i, N) cin>>w[i]; ll minVar, ans; solve(N, w, minVar, ans); cout<<minVar<<" "<<ans<<endl; } return 0; }
おまけ: メモ
/* 方針: 変化量 = 0 varDiff[i]: i 回目の始めに var が変化する分. deltaDiff[i]: i 回目の始めに変化量が変化する分 var = rot0でのスコア loop var += 変化量 + varDiff[i] 変化量 += deltaDiff[i] 5 5 4 3 2 1 での想定動作 0 -1 -1 -1 -1 1 deltaDiff -1 0 0 0 1 1 -1 -1 1 1 -1 deltaDiff -1 0 2 0 -2 2 1 1 1 -1 -1 deltaDiff 1 0 0 -2 0 3 1 1 -1 1 1 deltaDiff 1 0 -2 2 0 4 1 1 1 1 1 deltaDiff 1 0 0 0 0 sum 1 1 1 1 1 12 8 12 += -5 +1 6 8 += -3 +1 6 6 += -1 +1 8 6 += +1 +1 0 p o p o p o p o p delta 0 -1 1 -1 2 1 3 1 4 1 sum 1 1 p o po op o p p delta 0 -1 1 -1 2 1 3 1 4 1 sum 1 2 p o p o p po op delta 0 -1 1 1 2 1 3 -1 4 1 sum 1 3 po op p o p o p delta 0 -1 1 1 2 -1 3 1 4 1 sum 1 4 p p o po op o p delta 0 1 1 -1 2 -1 3 1 4 1 sum 1 */
| 
void add(vector<string>& w, int n0, int n1) { w[n0][n1] = w[n1][n0] = 'Y'; } class DistanceZeroAndOne { public: vector <string> construct(vector <int> d0, vector <int> d1) { ll N = d0.size(); if(!(d0[0]==0 && d0[1]==d1[0] && d1[1]==0)) return {}; vector<string> g(N, string(N, 'N')); VVI n0(N), n1(N); REP(i, N) n0[d0[i]].PB(i); REP(i, N) n1[d1[i]].PB(i); RANGE(i, 1, N) { ll pi = i-1; for(int v2 : n0[i]) { bool any=false; for(int v1 : n0[pi]) { if(abs(d1[v1]-d1[v2]) < 2) { any=true; add(g, v1, v2); } } if(!any) return {}; } for(int v2 : n1[i]) { bool any=false; for(int v1 : n1[pi]) { if(abs(d0[v1]-d0[v2]) < 2) { any=true; add(g, v1, v2); } } if(!any) return {}; } } VVI w(N, VI(N, 1LL<<60)); REP(i, N) REP(j, N) if(g[i][j]=='Y') w[i][j]=1; REP(i, N) w[i][i]=0; REP(k, N) REP(i, N) REP(j, N) w[i][j] = min(w[i][j], w[i][k]+w[k][j]); REP(i, N) if(d0[i]!=w[0][i]) return {}; REP(i, N) if(d1[i]!=w[1][i]) return {}; return g; } };
| 
ll N; // ノードを実際に消していく版 // ? - A - B があったとき A, B を消しまくる。葉である子が 2 個以上ある頂点がでてきたら First // 頂点が 1 個になっても First // なければまた繰り返し // 消えなくなったら Second string solve1(VVI& g) { while(1) { ll edges = 0; REP(i, N) { int cnt=0; edges += g[i].size(); for(int j : g[i]) { if(g[j].size()==1) cnt++; } if(cnt>=2) { return "First"; } } edges/=2; if(edges==0) return "First"; // i - adj - X =... -> X =... bool ch=false; REP(i, N) { if(g[i].size()==1) { int adj = g[i][0]; if(g[adj].size()==2) { int X = g[adj][0]==i ? g[adj][1] : g[adj][0]; { auto en = remove_if(ALL(g[X]), [=](int a) { return adj==a; }); g[X].erase(en, g[X].end()); } g[adj].clear(); g[i].clear(); ch=true; } } } if(!ch) break; } return "Second"; } // return: このノード以下で完全マッチの相手を探しているノードの個数 ll dfs(int u, int p, VVI& g) { ll x = 0; for(int v: g[u]) if(v!=p) x += dfs(v, u, g); if(x==0) return 1; // need to match ... 子が全部マッチしてるので if(x==1) return 0; // matched return INF; // 余りが確定したので無理 } // ノードを消さないスマート版 string solve2(VVI& g) { // rest==0 ←→ 完全マッチしている ll rest = dfs(0, -1, g); string ans = rest ? "First" : "Second"; return ans; } int main() { ios::sync_with_stdio(false); string s; while(cin>>N) { VVI g(N); REP(i, N-1) { ll A, B; cin>>A>>B; A--;B--; g[A].PB(B); g[B].PB(A); } // string ans = solve1(g); string ans = solve2(g); cout<<ans<<endl; } return 0; }
| 
// dp[i][j][k][l] // = 最初の割当が i (0:A 1:B), j+1分終わった時点, A の割当時間が k 分, 最後の割当が l (0:A 1:B) な状態での, 日をまたぐ切り替えを考慮しない最小切り替え回数 int dp[2][1440][721][2]; int INF = 1<<30; int main() { int test_cases; cin>>test_cases; ll A,B, s, e; REP(ttt, test_cases) { cin>>A>>B; VI tl(1440, -1); // 0: A 1: B -1: none REP(i, A) { cin>>s>>e; RANGE(i, s, e) tl[i] = 0; } REP(i, B) { cin>>s>>e; RANGE(i, s, e) tl[i] = 1; } REP(bi, 2) REP(mi, 1440) REP(ai, 721) REP(ei, 2) dp[bi][mi][ai][ei] = INF; REP(bi, 2) REP(ei, 2) dp[bi][0][ei==0][ei] = bi!=ei; REP(bi, 2) REP(mi, 1440) REP(ai, 721) REP(ei, 2) REP(nei, 2) { int old = dp[bi][mi][ai][ei]; int nbi = bi; int nmi = mi+1; int nai = ai + (nei==0); int cost = ei!=nei; if(nmi<1440 && tl[nmi]!=nei && nai<=720) { dp[nbi][nmi][nai][nei] = min(dp[nbi][nmi][nai][nei], old + cost); } } int ans = INF; REP(bi, 2) REP(ei, 2) { // 日をまたぐ切り替えの考慮 int lans = dp[bi][1439][720][ei]+(bi!=ei); ans = min(ans, lans); } cout<<"Case #"<<ttt+1<<": "<<ans<<endl; } return 0; }
