筆者はレート800前後の茶～緑コーダ
ABC414のD問題を解いていく
実装コード
基地局の配置と電波強度の問題を
→ 家の位置を M 個の区間に分割したときの
各区間における最大値と最小値の差の総和を最小化する問題
→ 隣り合う家同士の距離のうち、大きいものから M-1 個 を除外した総和を求める問題
と言い換えることができる。
そのため、家の位置を昇順にソートし、
隣り合う家との距離を配列として求める。
この距離配列をさらにソートし、
大きい方から M-1 個 を除外した残りの総和を答えればよい。
→ 差分に着目した貪欲法で解くことができた。
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N, M = rLI()
X = list(sorted(rLI()))
D = [X[i]-X[i-1]for i in range(1,N)]
D.sort()
print(sum(D[:N-M]))
if __name__ == '__main__':
main()
感想
問題をそのまま解こうとするのではなく、
言い換えを重ねて構造を単純化するタイプの問題だった。
一次元上の距離という視点に切り替えることで、
貪欲法として素直に解ける形に落とし込めたのが印象的。
このように視点を変えて本質を捉える発想は、
今後も積極的に身につけていきたい。