AHC017参加記~PyPyによる解法~

はじめまして、nadareと申します。

普段は機械学習エンジニアとして、レコメンドエンジンの製作や、kaggleやatmacupのような機械学習コンペティションへの参加をしています。

今回はTHIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017）に参加し、全体で126位になりました。 Python3での提出に限定した場合、pretestで3位の絶対スコア、finalで2位の相対スコアだったので、遅いPythonの中では健闘した方だと思います。

本ブログでは自身の解法についての解説と、参加した感想を書いていきます。

overview

除く辺の条件をいくつか設定し、その制約を満たす範囲で除く辺をDFSで伸ばしながら初期解を生成しました。 その後、除く辺の条件を満たしつつ、除く辺同士を繋げた大きさを最大化するように遷移し山登り法を行いました。 遷移後は、除いた辺の周囲から何個かの点のペアを作り最短距離の和を計算して、悪くなった場合は遷移を取り消しました。

table of contents

  • スコアとビジュアライズ結果
    • 入力別スコア
    • ビジュアライズ結果
  • solution
    • 設定した制約について
    • 初期解生成
    • 辺の遷移
    • 評価方法
  • technique
    • dijkstra -> A*による高速化
    • UnionFindの部分更新による高速化
  • うまくいかなかったこと
  • 感想

スコアとビジュアライズ結果

入力別スコア

wleiteさんのstatics(https://tc-wleite.github.io/ahc017)より

ビジュアライズ

solution

設定した制約について

除去する辺を選ぶ際に、以下の制約を設定しました。

  1. ある辺を除去する際、ある辺の二点を結ぶある辺を使わない最短経路が残っていること
  2. 次数が4以上の頂点においては、除去する辺同士が隣り合わないこと

この二つの制約を設けることで高速化と、限られた時間内でいい遷移を選びやすくなりました。

二番目に短い経路の確保

概要

全ての辺についてその辺を使わなかった際の最短経路(準最短経路とします)をA*の経路復元で求めておきました。 辺を除く際は以下の判定を行いました。

  • 除く辺に対して除去済みの辺が準最短経路に含まれていないか
  • 除去済みの辺に対して除く辺が準最短経路に含まれていないか

メリット

この条件を設定することにより、以下のメリットが生まれます。

  • ある辺を除いたときその二点間まで極端な遠回りをすることを避けられる
  • 必ず他のパスが活きているので、グラフの連結性の判定をしないですむ

この条件を満たすことは簡単で、初期解の作成の後少し遷移させるだけで秒もかからず達成できました。

アルゴリズム

除去済みの辺が最短経路に含まれているかは、事前に計算した準最短経路が除去済みの辺に含まれていないかの判定で簡単にできます。 後者の他の除去済みの辺の準最短経路に除く辺が含まれているかは、各日において準最短経路として使われた回数を配列として保持しておき、辺の追加や除去の度に更新することでO(1)で判定できます。

隣接辺を除かない

概要

いい点をとれた時のビジュアライザを確認した際、除去した辺が連結していてかつ適度に広がっている状態だといい点数をとれることに気づきました。 そこで、各頂点における辺を角度順に並べ、各辺について左右の辺を一緒に遷移してはいけないリストを作成しました。

アルゴリズム

各頂点の隣接辺についてatan2(y, x)を計算することで角度を求め、その順番で並びなおしました。

初期解生成

初期解は上記の制約を守りながら除去する辺をDFSで長く伸びるようにしながら作成しました。 この際一日ごとに一気に伸ばすのではなく、何サイクルかに分け1サイクル目では最大X個まで、2サイクル目では最大2X個までとすることで横に広がりすぎないようにしました。

辺の遷移

概要

辺の遷移は一つ除去する動かすか、除去する辺につながった除去する辺を全てまとめて動かすかの試行を毎回すべての日を対象に行っていました。 動かす日の決定は除去した辺同士がつながっている数が同じか増える遷移に限定しました。

アルゴリズム

辺の除去先では設定した制約を満たすかを毎回確認しました。 移動させる日は、除去した辺同士の連結数をUnionFindにより求め、元と同じかそれより大きくなる日を選びました。

評価方法

辺の移動先を決めた後は、除いた辺を使いそうな二点間の移動距離を何個か計算し、それがよくなるかどうかで遷移を確定するか決めました。

辺を一つ移動させる場合

辺uvを移動させる場合は、頂点vに近い点xからベクトルuvとvxのコサイン類似度が高い候補集合Xと、頂点uに近い点yからベクトルvuとuyのコサイン類似度が高い候補集合Yを選びました。 集合Xと集合Yのなかから、(x, y)の中点と(u, v)の中点のユークリッド距離が近くなるペアをいくつか選び、(x, y)間の最短距離をA*で計算し除去前後で比較しました。

辺を複数移動させる場合

全ての頂点に対して、どの辺ものぞかない状態での各頂点から最も最短経路が遠い点までの最短経路を事前計算しました。 辺ごとにどの頂点のペアで使われていたかを転置インデックスでもっておき、除去する辺の集合がよくつかわれているペアの最短距離を除去前後で比較しました。

technique

dijkstra -> A*による高速化

辺を一つも除去しない状態での全対最短経路をdijkstraを複数回繰り返すことで計算しておき、その距離をヒューリスティックな距離としてA*を計算しました。 これにより、各頂点から最も遠い辺までの距離を計算するときは5倍くらい早くなりました。

UnionFindの部分更新による高速化

繋いである辺をもう一回繋げないように注意してコードを書くことで、各連結集合が保持する辺を持っているUnionFindを書くことができました。コードは以下になります。

class EdgeUnionFind():
    def __init__(self, N):
        self.parent = list(range(N))
        self.edge_size = [0] * N
        self.edges = [[] for _ in range(N)]
    
    def find(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.find(self.parent[i])
            return self.parent[i]
    
    def unite(self, i, j, e):
        a = self.find(i)
        b = self.find(j)
        if a != b:
            if self.edge_size[a] < self.edge_size[b]:
                a, b = b, a
            self.edge_size[a] += self.edge_size[b]
            self.edges[a] += self.edges[b]
            self.edge_size[b] = 0
            self.edges[b] = []
            self.parent[b] = a
        self.edge_size[a] += 1
        self.edges[a].append(e)
 
    def match(self, i, j):
        return self.find(i) == self.find(j)

辺を繋げるときはそのままuniteします。 辺を除くときはその辺とつながる頂点の親を全て更新するのが大切で、self.subopt_uftがUnionFindとしたとき 頂点u, vをつなぐ辺iをUnionFindから消す場合は以下のようなコード

g = self.subopt_uft.find(u)
edges = [e for e in self.subopt_uft.edges[g] if e != i]
self.subopt_uft.parent[u] = u
self.subopt_uft.parent[v] = v
self.subopt_uft.edges[g] = []
self.subopt_uft.edge_size[g] = 0
for e in edges:
    eu, ev, _ = self.graph.edges[e]
    self.subopt_uft.parent[eu] = eu
    self.subopt_uft.parent[ev] = ev
for e in edges:
     eu, ev, _ = self.graph.edges[e]
     self.subopt_uft.unite(eu, ev, e)

辺をまとめて消す場合は以下のようなコードを書いていました。

g = self.subopt_uft.find(self.graph.edges[members[0]][0])
edge_members = self.subopt_uft.edges[g]
if check_difference:
    remain_members = list(set(edge_members) - set(members))
else:
    remain_members = []
self.subopt_uft.edges[g] = []
self.subopt_uft.edge_size[g] = 0
for m in members:
    u, v, w = self.graph.edges[m]
    self.subopt_uft.parent[u] = u
    self.subopt_uft.parent[v] = v
    self.remove_map[m] = False
    self.remove_edge_per_node[u] -= 1
    self.remove_edge_per_node[v] -= 1
    self.sub_path_cost -= (self.remove_edge_per_node[u] == 0)
    self.sub_path_cost -= (self.remove_edge_per_node[v] == 0)
    for sub_path in self.graph.subopt_roots[m]:
        self.subpath_used_count[sub_path] -= 1
self.removes.difference_update(members)

for m in remain_members:
    u, v, w = self.graph.edges[m]
    self.subopt_uft.parent[u] = u
    self.subopt_uft.parent[v] = v
for m in remain_members:
    u, v, w = self.graph.edges[m]
    self.subopt_uft.unite(u, v, m)

うまくいかなかったこと

  • 除去する辺のswap: 遷移の良さに対して計算時間がかかりすぎた
  • annealing: pythonの時間だと山登りでも時間が足りなかった
  • いくつかの代替指標: 辺を多くつなぎつつ頂点の数は増やすなどの制約を入れてみたがあまり効かなかった

感想

上位陣の解法を見ると今回は高速化がキモとなるコンテストで、Pythonは言語選択自体が悪かったように感じます。 ただその中では制約に工夫を入れたことで、遅い言語なりに頑張れたのかなと思います。

今回の問題はやりこむほどに色々見えてきて、一週間丸々破滅楽しむことができました。 ビジュアライザもデバッグから考察にまでいろいろ活躍して本当に良かったです。

THIRDさん、AtCoderさん、そしてライバルの皆さん、楽しい対戦本当にありがとうございました。