kojingharangの日記

SRM 719 Div1 500 OwaskiAndTree

20:02 |

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

ツイートする