Google code jam 2016 round 1BのC問題technobabbleに挑戦する.
問題設定は以下の通りである.
以上の設定のもと,問題の入力と出力は
である.
例えば,
である. 特に,3つ目の例でわかる通り,1つ目の単語と2つ目の単語は明確に区別されているので注意されたい.
Small datasetの場合は,$N \le 16$である.
Large datasetの場合は,$N \le 1000$である.
$N$個のトピックのうちどれが偽物のトピックかを一旦仮定すれば,偽物と本物の集合が問題設定の条件を満たしているか否かを判定するのは簡単である. よって,small datasetならば部分集合列挙でも十分短時間で解ける.
しかし,large datasetの場合は部分集合の数が多すぎるため,部分集合列挙では時間がかかりすぎる.
トピックの1つ目の単語として出現する単語の集合を$A$とし,トピックの2つ目の単語として出現する単語の集合を$B$とする. このとき,それぞれのトピックは2部グラフの枝に対応付けられる.
問題設定から,どの単語も少なくとも1回は『本物の」トピックに現れなければいけない. よって,本物のトピックの集合は「2部グラフの枝部分集合のうち,どの単語も枝の端点に含むもの」になっていなければならない. 一般に,グラフの枝部分集合のうち,その端点の集合が頂点集合と一致するものを「枝被覆(edge cover)」という.
Technobabbleは偽物のトピックの最大数を求める問題なので,言い換えると「2部グラフの最小枝被覆問題」あるいは「2部グラフの枝被覆に含まれない枝数を最大化する問題」と言える.
2部グラフの枝被覆に含まれない枝数の最大化問題は,そのまま最大流問題に変形できる.
与えられた2部グラフを$G$とし,その頂点集合$V(G)$を$A \cup B$,枝集合を$E(G) \subset A \times B$とする.
このとき新たに有向グラフ$H$を,
となるものとして用意する.
そして,有向グラフ$H$の枝容量$C \colon E(H) \to \mathbb{N}$を \begin{align*} C((v, w)) = \begin{cases} \delta^+(w) - 1 & (v = s, \ w \in A) \\ 1 & (v \in A, \ w \in B) \\ \delta^-(v) - 1 & (v \in B, \ w = t) \end{cases} \end{align*} とする. ここで,$\delta^+(v)$は頂点$v$から出る枝の数,$\delta^-(v)$は頂点$v$に入る枝の数である.
こうすれば,2部グラフ$G$の最小枝被覆問題の最適値は,有向グラフ$H$,枝容量$C$,始点$s$,終点$t$を入力とする最大流問題の最適値と一致することは明らかである.
一般に,プログラミングコンテストではNetworkXは使えない. しかしここでは簡単のためにまず,NetworkXを用いたコード例を示す.
import networkx as nx
def solve(N, topic):
H = nx.DiGraph()
for i in range(N):
a, b = topic[i]
H.add_edge('a'+a, 'b'+b, capacity=1)
H.add_node('source')
H.add_node('target')
for i in range(N):
a, b = topic[i]
H.add_edge('source', 'a'+a, capacity=H.out_degree('a'+a)-1)
H.add_edge('b'+b, 'target', capacity=H.in_degree('b'+b)-1)
flow_value, flow_dict = nx.maximum_flow(H, 'source', 'target')
return flow_value
では早速解いてみる.
topic = [('HYDROCARBON', 'COMBUSTION'), ('QUAIL', 'BEHAVIOR'), ('QUAIL', 'COMBUSTION')]
solve(len(topic), topic)
1
topic = [('CODE', 'JAM'), ('SPACE', 'JAM'), ('PEARL', 'JAM')]
solve(len(topic), topic)
0
topic = [('INTERGALACTIC', 'PLANETARY'), ('PLANETARY', 'INTERGALACTIC')]
solve(len(topic), topic)
0
良さそうである.
次に,入力をファイルから読み込んで,出力をファイルに書き出す関数も定義する.
def answer(input_file_name, output_file_name):
input_file = open(input_file_name)
output_file = open(output_file_name, 'w')
T = int(input_file.readline())
for case_number in range(1, T + 1):
N = int(input_file.readline())
topic = []
for n in range(N):
topic.append(input_file.readline().strip().split())
output_file.write('Case #{0}: {1}\n'.format(case_number, solve(N, topic)))
input_file.close()
output_file.close()
return
まずはsmall datasetで試してみる.
入力ファイル名をC-small-practice.in,出力ファイル名をC-small-practice.outとする.
answer('C-small-practice.in', 'C-small-practice.out')
正しく出力できたようだ.
次にlarge datasetで試してみる.
answer('C-large-practice.in', 'C-large-practice.out')
今度も,正しく出力できたようだ.
一般に,プログラミングコンテストではNetworkXは使えない.
よって,NetowrkXを用いないコード例を以下に示す. 最大流問題を解くためのEdmonds-Karpアルゴリズムを実装する. また,そのコードが煩雑にならないように,有向グラフ(および枝容量)をクラスで実現する.
class DiGraph:
'''NetworkxのDiGraphを真似たお手製のクラス.
self-loopには対応しているが,parallel edgesには対応してない.
Attributes: node(グラフの頂点集合)
edge(グラフの枝集合)
pred(グラフの逆枝集合)
'''
def __init__(self):
'''クラス生成関数.
頂点集合nodeと枝集合edge(とpred)を空の辞書として作っているだけである.
Parameters: なし
Returns: なし
'''
self.node = {}
self.edge = {}
self.pred = {}
return
def add_node(self, node_name, node_attributes={}):
'''グラフに頂点を追加する関数.
頂点集合は,頂点名をkey,属性を値とする辞書である.
Parameters: node_name(頂点名,辞書のkeyになれるもの)
node_attributes(頂点の属性,辞書)
Returns: なし
'''
self.node[node_name] = node_attributes
if node_name not in self.edge:
self.edge[node_name] = {}
self.pred[node_name] = {}
return
def add_edge(self, tail_name, head_name, edge_attributes={}):
'''グラフに枝を追加する関数.
枝集合は,tail名をkey,辞書を値とする辞書である.
さらに,各tailの値は,headをkey,枝属性を値とする辞書である.
さらに,枝属性も辞書である.
Parameters: tail_name(tail頂点名,辞書のkeyになれるもの)
head_name(head頂点名,辞書のkeyになれるもの)
edge_attributes(枝の属性,辞書)
Returns: なし
'''
if tail_name not in self.edge:
self.edge[tail_name] = {}
self.pred[tail_name] = {}
if head_name not in self.edge:
self.edge[head_name] = {}
self.pred[head_name] = {}
self.edge[tail_name][head_name] = edge_attributes
self.pred[head_name][tail_name] = edge_attributes
if tail_name not in self.node:
self.node[tail_name] = {}
if head_name not in self.node:
self.node[head_name] = {}
return
def edges(self):
'''グラフの枝のリストを返す.
Parameters: なし
Returns: set_of_edges(有向枝集合)
Return Type: list
'''
edge_list = []
for tail in self.edge:
for head in self.edge[tail]:
edge_list.append((tail, head))
return edge_list
def in_degree(self, node_name):
'''指定された頂点の入次数を返す.
Parameters: node_name(指定された頂点)
Returns: in_degree(頂点の入次数)
Return Type: int
'''
return len(self.pred[node_name])
def nodes(self):
'''グラフの頂点のリストを返す.
Parameters: なし
Returns: set_of_nodes(頂点集合)
Return Type: list
'''
return self.node.keys()
def out_degree(self, node_name):
'''指定された頂点の出次数を返す.
Parameters: node_name(指定された頂点)
Returns: out_degree(頂点の出次数)
Return Type: int
'''
return len(self.edge[node_name])
def predecessors(self, node_name):
'''指定された頂点のpredecessorのリストを返す関数.
Parameters: node_name(指定された頂点)
Returns: predecessors(指定された頂点のpredecessors)
Return Type: list
'''
return self.pred[node_name].keys()
def successors(self, node_name):
'''指定された頂点のsuccessorのリストを返す関数.
Parameters: node_name(指定された頂点)
Returns: successors(指定された頂点のsuccessors)
Return Type: list
'''
return self.edge[node_name].keys()
import math
def shortest_distance_on_graph(G, source):
'''グラフGにおける頂点sourceからのグラフ上の距離を返す関数.
Parameters:
G 有向グラフ
source 始点
Returns:
始点からの,それぞれの頂点へのグラフ上の距離
Return Type: dict
'''
shortest_distance = {v: math.inf for v in G.nodes()}
shortest_distance[source] = 0
visited = set([source])
queue = [source]
while len(queue) > 0:
v = queue.pop(0)
for w in G.successors(v):
if w not in visited:
visited |= set([w])
queue.append(w)
shortest_distance[w] = shortest_distance[v] + 1
return shortest_distance
def residual_network(G, flow):
'''最大流問題Gと実行可能フローflowからresidual networkを作る関数.
Parameters:
G (最大流問題の問題例)
flow (最大流問題の実行可能フロー)
Returns:
Residual network
Return type:
DiGraph
'''
residual_net = DiGraph()
for v in G.nodes():
residual_net.add_node(v)
for tail, head in G.edges():
amount = flow.edge[tail][head]['flow']
capacity = G.edge[tail][head]['capacity']
if amount < capacity:
residual_net.add_edge(tail, head, {'capacity': capacity-amount})
if amount > 0:
residual_net.add_edge(head, tail, {'capacity': amount})
return residual_net
def shortest_path_on_graph(G, source, target):
'''グラフ上の最短路を返す関数.
Parameters:
G(DiGraph)
source 始点
target 終点
Returns:
shortest_path 始点から終点への,グラフ上の,最短路
Return type: DiGraph
'''
shortest_dist = shortest_distance_on_graph(G, source)
shortest_path = DiGraph()
if shortest_dist[target] == math.inf:
return shortest_path
v = target
while v != source:
for p in G.predecessors(v):
if shortest_dist[p] + 1 == shortest_dist[v]:
break
shortest_path.add_edge(p, v)
v = p
return shortest_path
def augmenting_path(residual_net, source, target):
'''Residual networkとsourceとtargetからaugmenting pathを返す関数.
Edmonds-Karpアルゴリズム用に,枝数最小のaugmenting pathを返す.
Parameters:
residual_net (残余ネットワーク)
source (始点)
target (終点)
Returns:
augmenting path
augmenting path上の最小枝容量
Return type:
DiGraph
int
'''
aug_path = shortest_path_on_graph(residual_net, source, target)
if len(aug_path.edges()) == 0:
return (aug_path, 0)
minimum_capacity = math.inf
for tail, head in aug_path.edges():
minimum_capacity = min(minimum_capacity, residual_net.edge[tail][head]['capacity'])
return (aug_path, minimum_capacity)
def edmonds_karp(G, source, target):
'''最大流問題の最適解を返す関数.
Edmonds-Karpアルゴリズムを採用している.
Parameters:
G (有向グラフ,各枝にはキーが'capacity'の値が付随)
source 始点
target 終点
Returns:
最大流が'flow'として格納されたDiGraph
Return type:
DiGraph
'''
flow = DiGraph()
for tail, head in G.edges():
flow.add_edge(tail, head, {'flow': 0})
while True:
residual_net = residual_network(G, flow)
aug_path, min_capa = augmenting_path(residual_net, source, target)
if min_capa == 0:
break
for tail, head in aug_path.edges():
if head in flow.edge[tail]:
flow.edge[tail][head]['flow'] += min_capa
else:
flow.edge[head][tail]['flow'] -= min_capa
return flow
def solve(N, topic):
H = DiGraph()
for i in range(N):
a, b = topic[i]
H.add_edge('a'+a, 'b'+b, {'capacity': 1})
H.add_node('source')
H.add_node('target')
for i in range(N):
a, b = topic[i]
H.add_edge('source', 'a'+a, {'capacity': H.out_degree('a'+a)-1})
H.add_edge('b'+b, 'target', {'capacity': H.in_degree('b'+b)-1})
max_flow = edmonds_karp(H, 'source', 'target')
opt_val = 0
for head in H.successors('source'):
opt_val += max_flow.edge['source'][head]['flow']
return opt_val
topic = [('HYDROCARBON', 'COMBUSTION'), ('QUAIL', 'BEHAVIOR'), ('QUAIL', 'COMBUSTION')]
solve(len(topic), topic)
1
def answer(input_file_name, output_file_name):
input_file = open(input_file_name)
output_file = open(output_file_name, 'w')
T = int(input_file.readline())
for case_number in range(1, T + 1):
N = int(input_file.readline())
topic = []
for n in range(N):
topic.append(input_file.readline().strip().split())
output_file.write('Case #{0}: {1}\n'.format(case_number, solve(N, topic)))
input_file.close()
output_file.close()
return
answer('C-small-practice.in', 'C-small-practice.out')
answer('C-large-practice.in', 'C-large-practice.out')