前半パートの時点でダメでした。
https://community.topcoder.com/stat?c=problem_statement&pm=17307&rd=18982
問題
根付きの二分木が与えられるので、これの最大独立点集合を求める問題である。
ただし、独自の言語を用いて解く必要がある。
木の各頂点は、26個のbool型変数を取る。
このうち4つは役割が決まっており、
- p: 根以外の頂点は初期値がTrue
- l: 左の子を持つなら初期値がTrue
- r: 右の子を持つなら初期値がTrue
- s: 最大独立点集合に含めるなら、最終的にsをTrueにすること
この言語は、オートマトン上の状態と、各点の変数の値を参照し、次の行き先を決める。
そのため、以下で指定される命令を複数持つ。
- 現在の状態:変数の真偽値の条件:遷移先の状態:遷移前にTF切り替える変数名:行き先の頂点
条件を満たす命令列のうち、最も上にあるものに従い遷移する。
解法
まずアルゴリズムを考える。
これは貪欲に「子頂点に最大独立点集合に含まれる点がなければ、その点を最大独立点集合に含める」でよい。
あとはこれを上記言語を用いてDFSを実装しよう。
以下を組み合わせる。
- 頂点に初到達したら、とりあえずsをTにする。
- その後、左子頂点訪問済みのフラグを立てて(存在するなら)左子頂点に遷移する。
- 左子頂点から戻ってきたとき、sをFにするような状態に遷移していたらsをFにする。
- その後、右子頂点訪問済みのフラグを立てて(存在するなら)右子頂点に遷移する。
- 右子頂点から戻ってきたとき、sをFにするような状態に遷移していたらsをFにする。
- 親頂点に戻るわけだが、その際自身にsがTであるならば、親頂点に遷移するさい「sをFにするような状態」に遷移する。
class BinaryTreeAutomaton { public: vector <string> construct(int N) { vector<string> R = { "dfs", "clear:s:dfs:s:", "clear:S:dfs::", "dfs:bps:clear::p", "dfs:bPs:end::", "dfs:bp:dfs::p", "dfs:bP:end::", "dfs:ar:dfs:br:r", "dfs:aR:dfs:b:", "dfs:l:dfs:lsa:l", "dfs:L:dfs:sa:", }; return R; } }
まとめ
前半パートが思いつかない時点で、独自言語は関係なかった。
