• 1000頂点までの木が与えられる。頂点0から順に辺で行けるとこを何回でも移動できる。
• 頂点 i を最初に訪れたときスコアに pleasure[i] in [-10^6, 10^6] が足される。スコアが負になったら自動的に0まで回復する。
• スコアの最大値を求めよ。

• 木DPぽい
• (頂点, そこにくる直前のスコア) → 最良スコア は無理
• (頂点, 直前のスコアが0 or 十分大きい) → スコア(?) みたいな感じでいけないか
• なんかだめだ

• おわり

(あとで)

medは得点が負にならない能力のかわりに得点を1回だけ0点にできる能力をもってると考えてもよくて、木を「能力発動前に到達」「能力発動後に到達」「行かず」の3色に塗り分けることを考えて、木DP

— ちゃっくに300円 (@yosupot) 2017年8月15日

これ見たときは「は？？」という感想だったが、よーく考えてみると分かった。

必要な考察

• 問題のルールに従うと、頂点 v0 → v1 → v2 → ... と辿ったときスコアの計算は以下のようになる。

(あ) v0 → 操作A → v1 → 操作A → v2 → 操作A → v3 ... → 操作A

操作A : スコアが負なら 0 にする

• この値は、以下の計算方法で求まるスコアの最大値と同じになる。

(い) 操作B → v0 → 操作B → v1 → 操作B → v2 → 操作B → v3 ... → 操作B

操作B : スコアを 0 にリセットすることができる

• 理由: 操作Bのとき、スコアが負ならリセット、正ならリセットしなければ (あ) と一致する

• さらにこれは以下の最大値と等しい。

(う) 操作B → v0 → 操作B → v1 → 操作B → v2 → 操作B → v3 ... → 操作B ※ただしリセットは高々 1 回だけ

• 理由: もしあれば、(う) のリセットポイントを (い) の最後のリセットポイントと同じにすれば、最後以外はリセットしなくても同じなので (い) と一致する

ということで

• 全頂点は「最初に訪れた時リセット前」「最初に訪れた時リセット後」「訪れない」に分類できる。
• それぞれ BR, AR, NONE と書く。
• リセットしない場合は最初にリセットすると考えて全頂点が AR or NONE である状態に対応する。
• 最後にリセットする場合は全頂点が BR or NONE である状態に対応する。

• あとは、以下を求めていけば max ( f(0, BR), f(0, AR) ) が答えとなる。

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]);
	}
};

ツイートする

• [1, N] の permutation が与えられる。
• Σ^{N}_{1} |rotate_right(p, j)[i]-i| の最小値とそのときの j を求めよ。
• 2≦N≦10^6

• すごく規則性がありそう
• N^2 で実装して実験くん
• N=10で適当な例を試したら広義単調増加→減少となめらかに変わってそうなので三分探索
• 三分探索初めて書くので非常に怪しい
• WA

(あとで)

• N = 1000 くらいでランダムケースを見てみたら全然なめらかに変わってなかった...
• ちょっとずつずらしたときに某値とその変化量がどれくらい変わるかを最初に O(N) で求めておいて O(N) でちょっとずつずらしていくやり方があるようだ。
• 書いてみるが超絶ムズい...
• なんとか通ったけど +1 -1 とか不等号に等号が付くかとか場合分けとか無限にバグる要素ある。

(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

*/

ツイートする

• 頂点 0〜N-1 の無向連結グラフを作りたい。頂点0〜頂点iの最短距離はdist0[i], 頂点1〜頂点iの最短距離はdist1[i]でないといけない。
• 各辺の距離は 1. 作れるならその一例、作れなければ空を返せ。
• 2≦N≦50

• (TCO出忘れたのであとで)

• 考察
• 連結なので頂点0からの距離が1の頂点は必ずある。
• 同じく頂点0からの距離が M なものがあったら dist0 には 1〜M が含まれる。

• 頂点0 から距離 1 の頂点は頂点0と必ず繋がっている必要がある。(頂点0は1個なので)
• 頂点0 から距離 2 の頂点は頂点0 から距離 1 の頂点のどれかと繋がっている必要がある。
• 頂点1からの距離制約があるので、全部繋げてよいとは限らない。
• 繋げていいやつだけ繋げてどれかと繋がったか判定すればよさそう
• 繋げていいかどうかは、繋げたとき頂点1の距離制約を破らなければよい。
• u, v を繋げるとして、u, v の頂点1 からの距離の差の絶対値が2以上のときに繋げると頂点1からの距離の差が1になってしまうのでだめ
• 元々 1 以下のときはOKなので実際に繋げる
• 最後にできたグラフをWFしてdist0, dist1と矛盾ないかチェック (これやってなくてWA)

• Accepted in practice

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;
	}
};

ツイートする

• 木が与えられる。先手は白、後手は黒で塗られてない頂点を順番に塗っていく。塗れなくなったら黒頂点に隣接する頂点を全部黒にする。
• 白が残ってたら先手の勝ち。最適にプレイしたらどっちが勝つか求めよ。
• 2≦頂点数≦10^5

• 葉とその親がどちらも白になったら白が勝つ。
• という状態を作り出すには、葉である子が 2 個以上ある頂点を最初に白に塗ればいい。
• 最初にそういうのがなかったら? う〜む
• 葉である子が 1 個だけの頂点を白に塗ったら、次はその葉を黒にするしかない。
• ? - 親 - 葉 の親と葉を消していくといい?
• それ以外のとこに白を塗ることで勝てることはあるんじゃないかとかいろいろもやっとして終わり

• (あとで)
• 公式解説 → https://atcoder.jp/img/agc014/editorial.pdf

• 帰納法で完全マッチングあり←→後手勝ちが証明できるようだ。
• ? - 親 - 葉 の親と葉を消せるだけ消して、1頂点になった or 葉である子が 2 個以上ある頂点があったら First, なければまた繰り返し、消えなくなったら Second でよかった

• solve1 で remove_if は計算量的にやばいかなと思ったが時間は solve2 と同じくらいだった。
• solve1 は実装だけならできていたかもしれないので、証明がいまいちできない時はそれっぽい実装を進めてしまうというのもありだなぁ特に何回でも試せるコンテストでは。
• solve2 は実際にはノードを消さないちょい賢い方法。あまり思いつく気はしない。

• Accepted in practice

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;
}

ツイートする