新米機械学習エンジニアのブログ

AI系ベンチャー企業で機械学習・ディープラーニングを使った仕事をしているリサーチエンジニアのブログです。これからデータサイエンティストやAIエンジニアになりたい人向けに情報を書いていきます。

Streamline AtCoder Python3

SPONSORED LINK

AtCoderのabc117で行われたStreamlineという問題をPythonで解いてみました。 atcoder.jp

N, M = list(map(int, input().split()))
X = list(map(int, input().split()))

X = sorted(X)
diffs = [X[i] - X[i-1] for i in range(1, len(X))]
diffs = sorted(diffs, reverse=True)

# 一番遠い距離から、2点間の距離の中から大きい順に引いていくだけ
res = X[-1] - X[0]
for i in range(min(len(diffs), N-1)):
  res -= diffs[i]

print(res)

一応github上にも載せておきました。良ければスターを押してもらえると嬉しいです。 github.com

詳しい解説はけんちょんさんのブログ drken1215.hatenablog.com に書かれています。