LeetCode Weekly Contest 117 : 968. Binary Tree Cameras

LeetCodeは8ptぐらいでも典型問題結構あるなぁ…。
https://leetcode.com/contest/weekly-contest-117/problems/binary-tree-cameras/

問題

木を成すグラフが与えられる。
一部の頂点にカメラを置くことを考える。
各頂点は、自身か隣接点にカメラがなければならない。
全頂点を覆うのに必要なカメラの最小数を求めよ。

解法

典型的な木DP。
各子頂点にたいし、その頂点およびSubTreeに対して、その子頂点自身以外のSubTreeは条件を満たしている状態で以下の３つの状態における最小カメラ数を順次求めていく。

• • 子頂点にカメラがある
  • 子頂点にカメラがないが孫頂点にカメラがある(よって子頂点はすでに条件を満たす)
  • 子頂点にも孫頂点にカメラがない(よって子頂点が条件を満たすためには今の頂点にカメラがなければならない)

class Solution {
public:

	vector<int> dfs(TreeNode* root) {
		if(root->left==NULL) swap(root->right,root->left);
		// 0-camera 1-covered 2-not
		if(root->left==NULL) {
			return {1,101010,0};
		}
		else if(root->right==NULL) {
			auto a=dfs(root->left);
			
			return {min({a[0],a[1],a[2]})+1,a[0],a[1]};
		}
		else {
			auto a=dfs(root->left);
			auto b=dfs(root->right);
			
			return {
				min({a[0],a[1],a[2]})+min({b[0],b[1],b[2]})+1,
				min({a[0]+b[0],a[0]+b[1],a[1]+b[0]}),
				a[1]+b[1]
			};
			
		}
		
		
	}
    int minCameraCover(TreeNode* root) {
        auto a=dfs(root);
        return min(a[0],a[1]);
    }
};

まとめ

今のところLeetCodeで新しい知見を得たことないし、実行環境の関係で早解きも楽しみにくいし、モチベーション上がらないな…。