AHC020 お疲れさまでした！
ほぼ自分のためのメモ書きなので読みづらい部分もあるかと思いますが、せっかくなので記録として残したいと思います。
Python であまり競プロに参戦してないので、最適なコードではないかもしれませんが、ツッコまないでください。
問題概要
なるべく多くの人が生放送を見れるようにしつつ、コストを抑えてね。
やったこと
概要: Scikit-learn の KMeans でクラスタリングで思考ロックされてしまった...
まず First AC を狙う
いつものやつ。
入力を N, M だけ受け取って、出力形式に合うように全部 0 にしてみただけ。
int main() {
int n, m;
cin >> n >> m;
rep(i, n) cout << 0 << " ";
cout << endl;
rep(i, m) cout << 0 << " ";
cout << endl;
return 0;
}
(提出 #42184317 (新しいタブで開く)・スコア: 93,995)
0:45 で提出しましたが、残念ながら olphe さんに 12 秒差で負け、 2 位でした。 (なんの戦いですか)
クラスタリングしてみる
パッと見た感じ、クラスタリングすることで出力強度をいい感じにできそうな気がした。
講義でちょうど触っていたところだったので、クラスタリングをしてみることにしてみた。
ここで疑問。
「AtCoder って Scikit-learn 使えるっけ...？」
(https://atcoder.jp/contests/language-test-202001 (新しいタブで開く))
あるやん！！！コンテストのどの場面で使うねん！ (ありがとうございます)
というわけで、Scikit-learn を使ってクラスタリングしてみることにした。
C++ のほうが慣れてるし高速だけど、さすがに実装が面倒なので Python で書いた。
k-平均法で、ひとまず直感で k = 50 で分けてみることにした。
そして、クラスタリング結果をもとに、クラスタの中心に一番近い放送局を "中心" として選び、そのクラスタから最も遠い人への距離を "半径" として選ぶことにした。
# Clustering
model = cluster.KMeans(n_clusters=50).fit(people)
result = model.predict(people)
for i in range(50):
# クラスタの中心を求める
center = model.cluster_centers_[i]
# クラスタの中心から最も近い点を求める
minim = (0, 10 ** 9)
for j in range(n):
dst = distance(center, verticles[j])
if minim[1] > dst:
minim = (j, dst)
# 最も遠い人
farthest = 0
for j in range(k):
if result[j] == i:
dst = distance(people[j], verticles[minim[0]])
if farthest < dst:
farthest = dst
power[minim[0]] = farthest
used.append(minim[0])
最小全域木
クラスタリングの中心点を選んだら、まず最小全域木を構築したいよね～ということで実装。
not522/ac-library-python (新しいタブで開く) を利用させていただきました (ありがとうございます)
# Kruskal
dsu = DSU(n)
used_edges = []
edges = sorted(edges, key=lambda x: x[3])
for i in range(m):
if dsu.same(edges[i][1] - 1, edges[i][2] - 1):
continue
dsu.merge(edges[i][1] - 1, edges[i][2] - 1)
used_edges.append(edges[i][0])
あとは、使った辺を出力するだけ。
上のクラスタリングを併せて提出！
(提出 #42186701 (新しいタブで開く)・スコア: 327,697,127)
かなり増加した。
Python だからかなり遅いかなと思ったけど、何とか 1500 ms 以内には収まっているのでまあいいかんじ。
自分の実装ミスで、距離の 2 乗をそのまま出力して全部パワー 5000 になってしまっていたので、修正をして提出。
(提出 #42187025 (新しいタブで開く)・スコア: 304,422,174)
うーん...まあこれは誤差かなぁ
枝刈り
最小全域木を構築したら、どうせ葉のほうは使わないので枝刈りしてみることにした。
DFS をして、もし使われているのであれば残し、使われていないのであれば消すかんじ。
def dfs(v, visited, Graph, tobeused_v, use_edge):
visited[v] = True
ret = False
for (next_v, edge_id) in Graph[v]:
if visited[next_v]:
continue
if dfs(next_v, visited, Graph, tobeused_v, use_edge):
ret = True
use_edge.append(edge_id)
if ret:
return True
if v in tobeused_v:
return True
return False
# ...
# グラフは最小全域木の辺のみを隣接リストで持っている
# Filter with DFS
used_edges = []
visited = [False] * n
dfs(0, visited, Graph, used, used_edges)
これで提出！
(提出 #42187719 (新しいタブで開く)・スコア: 423,292,802)
結構上がった。100 位くらい。
ほかの範囲にいる人を除く
すでにほかの放送範囲内にいる人は、クラスタに含まれていても使わないようにすることで、出力を少しでも弱くできるのではないかと思った。
# Clustering
model = cluster.KMeans(n_clusters=50).fit(people)
result = model.predict(people)
nearest = np.array([-1] * k)
for i in range(50):
# ...
# 最も遠い人
farthest = 0
for j in range(k):
if result[j] == i and nearest[j] == -1:
# ...
# ...
# 範囲内にいる人を追加
for j in range(k):
if nearest[j] == -1 and distance(people[j], verticles[minim[0]]) <= farthest:
nearest[j] = minim[0]
(提出 #42188103 (新しいタブで開く)・スコア: 444,622,231)
30 位くらいまで上がりました。
これをさらに改善することにします。
具体的には、大きい円から見て行って、もし自分がほかの円に完全に重なっていれば、自分を消すことにします。
実装上では、大きい円から今の出力で収まる人を更新して、もし人がいなければ、その円の出力を 0 にする、ということにします。
何言ってるかわかりづらいですね。コードを見てください。
powers = [(i, power[i]) for i in range(n)]
powers = filter(lambda x: x[1] > 0, powers)
powers = sorted(powers, key=lambda x: x[1], reverse=True)
nearest = np.array([-1] * k)
for (i, p) in powers:
farthest = 0
for j in range(k):
if distance(people[j], verticles[i]) <= p and nearest[j] == -1:
nearest[j] = i
farthest = max(farthest, distance(people[j], verticles[i]))
power[i] = farthest
(提出 #42190533 (新しいタブで開く)・スコア: 441,849,838)
この記事を書き始めたので実装が遅れたため 100 位まで下がりましたが、そこから微妙にスコアも下がってしまいました...。
しかも実行時間も 1958 ms とギリギリ。
調べたら出てきたので KMeans ではなく MiniBatchKMeans を使うようにしました。
(提出 #42191375 (新しいタブで開く)・スコア: 230,581,892)
え、そんな下がる？？？
まあ実行時間は 1314 ms になったけど、さすがにこれはないでしょ...。
(後に実装ミスであることが判明する)
最小全域木の改善
枝刈りすると遠回りすることになってしまうので、使う点のみを考慮した最小全域木を構築することにしました。
networkx でリファクタリングして、最小全域木を構築するところをいい感じに (?) 書き換えました。
# 使う予定の頂点について MST
tmp_edges = []
for i in range(0, n):
if power[i] == 0:
continue
tmp_edges.append((nx.shortest_path_length(Graph, 0, i, weight="weight"), 0, i))
for j in range(i + 1, n):
if power[j] == 0:
continue
tmp_edges.append((nx.shortest_path_length(Graph, i, j, weight="weight"), i, j))
tmp_edges = sorted(tmp_edges, key=lambda x: x[0])
dsu = DSU(n)
used_edges = np.zeros(m)
for (c, u, v) in tmp_edges:
if not dsu.same(u, v):
dsu.merge(u, v)
path = nx.shortest_path(Graph, u, v, weight="weight")
for i in range(len(path) - 1):
used_edges[edges[(path[i], path[i + 1])]] = 1
(提出 #42193765 (新しいタブで開く)・スコア: 423,751,695)
あまり上がらず。
っていうか実行時間が 1999 ms だった、危なすぎ
さっきの実装ミスが「ほかの範囲にいる人を除く」部分で、これを消してしまったので、さすがに改めて実装してみた。
(提出 #42194117 (新しいタブで開く)・スコア: 445,357,606)
なんかうまくいかない。
赤丸、絶対いらないだろ！とか思ってもうまく実装できる予感がしない...。
消す部分は大きい順にソートするんじゃなくて、一番大きい丸を選んで次は一番遠い丸を選ぶ、というのがいいのか...？うーん、うまくいかない...。
ん、含んでいる人数が大きい順に丸を選べばいいのか...？だめ。
とりあえず残り 5 分だし、人数順にソートしたやつを提出してみる。
TLE した。かなしい。
ここでコンテスト終了。
お疲れさまでした～
振り返り
うん、もうこれです。
みんな焼きなましで解いていたので、 C++ のまま Scikit-learn を使わずに解くべきだったかなと反省...。
Python 遅すぎ！
最終結果は 302 位でした。
再来週の AHC021 は 200 位以内に入れるように頑張りたいですね...
後日記
混合ガウス分布を使う (2023-06-14)
単純に興味として、混合ガウス分布を使ってみました。
分散も考慮するので上がってほしいなーという感じ。
提出 #42249860 (新しいタブで開く)・スコア: 446,801,657
えー、本番 292 位相当でした。
さらに実行時間も減っていて、？？？になってました。
(内部実装を読む気はない)
