Pythonで解く二分木ぬり絵ゲーム ― 後手の勝利判定アルゴリズム

問題概要

二人のプレイヤーが二分木の上でターン制のゲームを行います。二分木の根(root)と、木のノード数nが与えられます。ここでnは奇数であり、各ノードは1からnまでの互いに異なる値を持っています。

まず先手のプレイヤーが1 ≤ x ≤ nを満たす値xを選び、続いて後手のプレイヤーがy ≠ xを満たす値yを選びます。先手は値xのノードを赤色に塗り、後手は値yのノードを青色に塗ります。

その後、先手から始めて交互に手番が進みます。各ターンで、プレイヤーは自分の色(先手なら赤、後手なら青)のノードを1つ選び、その隣接する未着色ノード(左の子・右の子・親のいずれか)を自分の色で塗ります。このような操作ができない場合のみ、プレイヤーはパスとなります。両者がパスした時点でゲームは終了し、より多くのノードを塗ったプレイヤーが勝者となります。

私たちは後手の立場です。勝利を確実にできるようなyが存在する場合はtrueを、存在しない場合はfalseを返してください。

入力例

例えば、下図のような二分木に対してn = 11、x = 3が与えられたとします。

この場合の出力はtrueです。後手が値2のノードを選ぶことで、勝利を確定できるためです。

解法のアプローチ

この問題の鍵は、先手が最初に塗るノードxを基準に、木を3つの領域へ分割して考えることです。

• xの左部分木に含まれるノード数(leftVal)
• xの右部分木に含まれるノード数(rightVal)
• x自身とその親側にあたる残りの領域のノード数(nodeToX)

後手はこれら3つの領域のいずれかに拠点を置くことになります。nが奇数であるため、最大の領域が他の全領域の合計よりも大きければ、後手はその領域を独占して必ず勝てます。逆に、どの領域も過半数に届かない場合は、先手が勝ち筋を塞ぐことができるためfalseを返します。

具体的な手順は以下の通りです。

• solve()メソッドを定義します。引数はnode、x、l、rで、lとrは初期値Falseです。
• nodeが存在しない場合は、そのままreturnします。
• lがTrueならleftValを1増やし、rがTrueならrightValを1増やします。
• nodeの値がxと一致する場合、solve(node.left, x, True, False)とsolve(node.right, x, False, True)を呼び出します。
• それ以外の場合は、solve(node.left, x, l, r)とsolve(node.right, x, l, r)を呼び出します。
• メイン処理では、nodeToX、leftVal、rightValを0で初期化し、solve(root, x, False, False)を実行します。
• nodeToX = n − leftVal − rightVal − 1 を計算します。
• temp = max(rightVal, nodeToX, leftVal) を求めます。
• (nodeToX + leftVal + rightVal − 2×temp ≥ 0) ならfalseを返し、それ以外はtrueを返します。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

def insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        self.nodeToX = 0
        self.leftVal = 0
        self.rightVal = 0
        self.solve(root,x)
        self.nodeToX = n - self.leftVal - self.rightVal - 1
        temp = max(self.rightVal,max(self.nodeToX,self.leftVal))
        return not (self.nodeToX + self.leftVal + self.rightVal - (2*temp)>=0)
    def solve(self,node,x,l= False,r = False):
        if not node:
            return
        if l:
            self.leftVal+=1
        elif r:
            self.rightVal+=1
        if node.data == x:
            self.solve(node.left,x,True,False)
            self.solve(node.right,x,False,True)
        else:
            self.solve(node.left,x,l,r)
            self.solve(node.right,x,l,r)

ob = Solution()
root = make_tree([1,2,3,4,5,6,7,8,9,10,11])
print(ob.btreeGameWinningMove(root, 11, 3))

入力

[1,2,3,4,5,6,7,8,9,10,11]
11
3

出力

true